Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Forrelation de-oracleization: three barriers, Kloosterman atoms, and the low-degree instantiations (manuscripts, Lean formalization, certificates)

Hikaru Wakaura

Published Oct 22, 2026• 0 citations
Publisher

Abstract

Two manuscripts on the de-oracleization of Forrelation, with the complete supporting material: the Lean 4 formalization (Mathlib), the exact computational certificates with their recorded outputs, and the records of the adversarial reviews. Paper 1 — Three Barriers to De-oracleizing Forrelation: Truth Tables, Seeds, and Restricted Models (barriers.pdf, source barriers-source.tar.gz). Forrelation separates quantum from classical query complexity maximally. The paper studies the ladder of intermediate goals between the oracle separation and an unconditional separation of uniform decision classes and shows that three natural formalizations of its rungs are either trivial (truth-table collapse: quasi-linear time by the fast Walsh–Hadamard transform), false for every family (seed-compression barrier: any family generated from fewer seed bits than queries is distinguished from random by a fixed query set, and the computational variant is equivalent to one-way functions), or a restatement of a classical question (restricted-model trap: an explicit universal family whose label is any prescribed function of the seed, with exact Forrelation atoms and a proof of invariance). In the equal-footing model, where the restricted class evaluates the family itself, the trap dissolves for the whole orbit of the quadratic base pair under linear changes of variables and twists, by a derivative attack; a Kloosterman-sum family outside that orbit is constructed with provable atoms for every n ≥ 7 (fourth-moment identity, translation Parseval), on which the same-seed attacks of the paper are at chance; a uniform choice of the NO translation is open and stated as a conjecture supported by exact computation up to n = 25. Paper 2 — Low-Degree Instantiations of Forrelation Are Easy: Hidden Subspaces from Queries, Block Structure from Coefficients (whitebox.pdf, source whitebox-source.tar.gz). For the hidden Maiorana–McFarland family of Girish and Servedio with a polynomial h of constant degree whose top-degree form has trivial radical, O(4^d n^2) queries to f recover the hidden subspace as the radical of the top-degree form of f, after which the dual is evaluated by linear algebra; the low-degree instantiation is therefore easy already in the black-box model, and for d = 3 the radical hypothesis can be dropped. For the self-Forrelation proposal of Gheorghiu, Bravyi and Temme (as described in Gheorghiu's talk), the block decomposition of a sum of non-degenerate cubic blocks scrambled by an orthogonal matrix is recovered from the coefficient list by linear algebra through the symmetry algebra of the cubic form; degenerate blocks, a constant fraction of the self-dual bent cubics the proposal uses, defeat this algorithm, and the obstruction and the failure rate are given. Reproducibility archive (forrelation-barriers.tar.gz): the Lean 4 project (41 files in Forrelation/ plus a vendored subset of the OpenAI Math Release library for constant-depth circuits, Apache 2.0), every theorem depending only on the standard axioms; 35 certificate scripts with run_all.sh and the recorded results; the review records (several rounds of adversarial panel review per paper, three reviewers per round, syntheses, and an evidence audit of the citations against primary sources); and the project report. The analysis, code, Lean proofs, reviews and text were produced with large language models operated by the author, who checked every statement and certificate (see the AI disclosure sections of the papers).

DOI
10.5281/zenodo.23557490

Related papers

Collective charge response is not determined by the few-particle sectors

M.J. Baek

Preprint and reproducibility archive; not peer reviewed. What this record contains. The full text of the manuscript "Identical Few-Particle Gauge Hamiltonians, Programmable Collective Charge Response" (M. J. Baek), its Supplementary Information with complete proofs, and the archive that certifies every closed-form value the paper states. The result. Few-particle dynamics are routinely used to infer collective response in paired quantum matter. This work constructs finite-range interacting response twins that defeat that inference exactly. For any prescribed finite p, two positive finite-range parents have complete static gauge Hamiltonians that coincide at every Peierls link phase on every sector N ≤ p and first separate at N = p+1; their zero-twist finite-density ground rays are the same Dicke condensate, yet their collective charge curvatures differ extensively. The obstruction has no universal depth, and the paper locates it exactly: the blind depth equals the spectator body order, the algebraic bound is independent of geometric range, and bounded range still bounds depth only through the number of sites a ball can hold — so no arbitrary-depth family of uniformly fixed range is claimed. Conversely, a structurally closed exact-pair tower closes at depth two. What is hidden is designable: with d(d+1)/2 displacement families the whole symmetric response-tensor difference is locally realizable at interior filling, and a triangular-lattice twin pair differs only in shear while both diagonal responses stay equal. A 4×4 hard-core-qubit discriminator gives an exact factor-of-two contrast with an internal null control and a state-preparation certificate in 17 equal-time settings. What is certified, and what is not. Results proved in closed form are stated as theorems and proved in full in the Supplementary Information; results established by exact rational or symbolic computation are labelled computer-assisted and carry the script that produces them; the 16-qubit discriminator is a blueprint with an end-to-end noise simulation, not a hardware demonstration, which is not claimed anywhere. Scope limits, open proof lines and one refuted conjecture are recorded explicitly rather than omitted. The archive. response_twins_unified_v1.0.zip contains the manuscript and Supplementary sources, the proof notes, the complete fail-closed verification harness (31 executed stages in release mode — 27 claim-bearing certificate stages, 1 non-claim diagnostic stage and three fail-closed gates — and 24 in quick mode) with one frozen log per stage, independent reimplementations of the load-bearing calculations, negative controls that must fail, the exact-arithmetic certificates behind every closed-form value in the paper, the figure-generation scripts, the scientific claim and provenance record (79 rows with status and scope notes, 50 of them naming the in-archive script or certificate that checks them, the rest saying in words why not), and a per-file SHA-256 manifest of all 209 payload files. Verifying it. Extract the archive and run python3 REPRODUCIBILITY/run_all.py --mode quick for the fast subset or --mode release for all 31 stages; bash BUILD.sh rebuilds both PDFs from source. The three gates check journal-format limits, the release payload against its manifest, and every number the documentation states about the artefacts. Running the harness does not modify the archive: all runtime output is written outside the immutable tree, so verification cannot invalidate the manifest. README.md separates reproducing the content (TeX Live 2023 or newer) from reproducing the archived PDF bytes, which needs the exact producing build recorded inside the PDFs. Licences. Manuscript, Supplementary Information and documentation CC BY 4.0; source code MIT; certificate data CC0 1.0. LICENSE.md is the authoritative per-file mapping and is included both in the archive and as a separate file on this record.

•Aug 7, 2026•0 citations

Mind the Bad Norms: Revisiting Compressed Oracle-Based Quantum Indistinguishability Proofs

Ritam Bhaumik, Benoît Cogliati, Jordan Ethan +1 more

Lecture notes in computer science•Dec 7, 2024•7 citations

Lattice-based cryptography in a quantum setting : security proofs and attacks

Pouria Fallahpour

Cryptographie fondée sur les réseaux euclidiens dans une contexte quantique : preuves de sécurité et attaques L'émergence des machines quantiques crée des défis et des opportunités pour la cryptographie. En particulier, les preuves de sécurité doivent être révisées en raison des capacités quantiques des adversaires. Cette thèse propose deux contributions à cet égard : un résultat positif et un résultat négatif. La transformation de Fiat-Shamir avec des rejets est l’un des principaux paradigmes pour concevoir des schémas de signature post-quantiques. Une partie de cette thèse consiste en une analyse détaillée de cette transformation dans le modèle de l’oracle aléatoire quantique. Tous les travaux précédents proposant une analyse de sécurité de cette transformation ont négligé des détails subtils, compromettant la correction des preuves. Par conséquent, notre preuve de sécurité est la première de son genre à être correcte. De plus, nous analysons le temps d'exécution et la correction des signatures obtenues à partir de cette transformation. Le problème learning with errors (LWE) a été largement utilisé pour construire des schémas cryptographiques sécurisés contre les adversaires quantiques. Une hypothèse liée à LWE stipule que la génération d'une instance LWE sans connaître son secret est difficile pour tous les algorithmes polynomiaux. On peut utiliser cette hypothèse pour prouver la sécurité de certains arguments de connaissance succints. Bien que cela semble être une tâche difficile pour les algorithmes classiques, nous présentons un algorithme quantique polynomial qui génère des instances LWE sans connaître le secret. Notre algorithme invalide ainsi les analyses de sécurité de ces arguments de connaissance succints dans le contexte quantique.

•Jul 5, 2024•1 citation

The Cohomology of Copying

The Institute for Applied Ontological Mathematics

Whether a quantum proof outperforms a classical one — both checked by the same efficient quantum verifier — is a question answered, so far, only relative to oracles. Beneath that answer is a structure with no quantum content at all: the difference between a resource one can copy and one one cannot. We show that this difference is cohomological. A witness that carries a copy map collapses every verifier to a memoryless sampler, so its distinguishing power is a functional of k-wise marginals alone; the obstruction to copying is a Čech class on a cover of a state by its measurement bases, and the Forrelation function of Aaronson and Ambainis is exactly the transition cocycle of that cover. The separation holds precisely when the class is nonzero: invisible from inside any single copyable chart, where it is a coboundary, and visible to the linear witness that reads the whole cover at once. Four familiar facts turn out to be four faces of the same class. Its non-vanishing is the no-cloning theorem; the dimension of its kernel is the Landauer erasure cost of the witness register; its representative on the standard/Hadamard cover is Forrelation; and the collapse of the copyable verifier onto one chart is why a classical witness, for these problems, cannot win. We make each face a finite, exactly computed certificate: on a corpus of distinguishing tasks built from Heisenberg–Weyl orbits, every depth-two adaptive sampler has advantage exactly zero — a total quantification over the strategy space, not a sampled estimate — while the linear witness reads a squared-Forrelation gap the kernel computes from truth tables through the Hadamard transform. Two independent exact computations agree on every verdict, and the engine that results either returns a gap two exact paths both certify, or refuses — and a refusal carries its own evidence, a certificate of exactly the obstruction that stopped it. The asymptotic separation of the underlying family is not ours; we cite it. What is ours is the identification — that a separation of complexity classes is, at bottom, a hole. All results below are machine-checked in Lean 4; the formal record and its axiom footprint are described in Section 8. The paper is legible in mathematics alone. Published by The Institute for Applied Ontological Mathematics.

•Oct 11, 2026•0 citations

Uniform Rényi Privacy Amplification by Shuffling

Alex B. Shvets

We study independent one-message shuffling through a common channel with replacement adjacency and arbitrary deterministic backgrounds. Under one local Rényi budget, without a pointwise likelihood-ratio cap, the optimal uniform same-order rate is $n^{-\min\{1,\alpha-1\}}$ for fixed $\alpha>1$; a local KL budget alone gives no uniform amplification. We determine the exact asymptotic worst-case approximate-DP envelope at each fixed positive privacy parameter and the leading inverse calibration at failure probability $d/n$ for all fixed $\alpha>1$. Matching upper bounds are uniform over channels and alphabets varying with $n$. At and above order three, the calibration coefficient is the square root of an attained local triple-variance frontier, realizable on at most nine output symbols. At order three we evaluate this frontier on a certified budget interval and identify the unique extremal ratio law. The same frontier determines the limiting central-window profile for $\alpha>2$ and the logarithmic moderate-window exponent. Under local $\chi^2$ diameter $C$, the exact asymptotic neighboring coefficient is $2C(C+5)/(C+4)$; we also give explicit finite amplification bounds and a fixed-channel background reduction. Formal verification. All statements of the paper have been formalized in Lean 4 (version 4.35.0) with Mathlib (release v4.35.0), including the computer-assisted order-three theorem, for which all certificate computations are checked by the Lean kernel. The formal proofs contain no sorry and use only the standard axioms propext, Classical.choice and Quot.sound. The project builds from scratch, every module passes a replay by the Lean kernel (leanchecker), and all theorems of the interface file Statements.lean, together with everything they depend on (69 078 declarations in total), were rechecked by the independent type checker nanoda. ChatGPT was used to write the Lean code and Claude to audit it; the author takes full responsibility for all results. Files. The PDF is the paper (24 pages). The ZIP archive Uniform_Renyi_arXiv_source_2026-11-09.zip is the LaTeX source. Its folder anc/ contains the exact rational polynomial certificate for the computer-assisted order-three theorem (verify_order_three_frontier.py, needs only the Python standard library) and further exact checks. The ZIP archive UniformRenyiShuffle-Lean-1.0.0-2026-11-09.zip is the Lean project UniformRenyiShuffle 1.0.0; its file MAP.md gives the Lean name of every statement of the paper. Changes from version 1. The Lean formalization is added. The paper and its LaTeX source are unchanged.

•Nov 9, 2026•0 citations

Vérification interactive efficace de calculs quantiques délégués pour des problèmes à oracle

Samuel Ducharme

Dans cette thèse, nous étudions la vérifiabilité des calculs quantiques dans un contexte oraculaire. D'une part, nous connaissons plusieurs problèmes à oracle offrant démontrablement une séparation entre BPP et BQP. De l'autre, plusieurs techniques de preuves interactives ont été développées dans les vingt dernières années pour rendre les calculs quantiques faits par une machine BQP vérifiables par une machine BPP. Malheureusement, aucune de ces techniques ne relativise trivialement aux problèmes à oracles. Ceci nous mène à la question suivante : est-ce que ces problèmes à oracles admettent eux aussi des preuves interactives entre un prouveur BQP et un vérificateur BPP, ou est-ce qu'il serait démontrablement impossible d'en trouver une? Nous passerons en revue les principales techniques de preuves interactives dans le monde non relativisé, ainsi que les principaux problèmes à oracles séparant BQP de BPP. Puis, nous nous attarderons sur le problème de Simon et le problème Forrelation, pour lesquels nous introduisons dans cette thèse les premières preuves interactives avec prouveur BQP et vérificateur BPP mais légèrement quantique (et nous laissons ouverte la question à savoir s'il existe une telle preuve interactive avec un vérificateur BPP purement classique).

•Aug 1, 2026•0 citations
Two manuscripts on the de-oracleization of Forrelation, with the complete supporting material: the Lean 4 formalization (Mathlib), the exact computational certificates with their recorded outputs, and the records of the adversarial reviews. Paper 1 — Three Barriers to De-oracleizing Forrelation: Truth Tables, Seeds, and Restricted Models (barriers.pdf, source barriers-source.tar.gz). Forrelation separates quantum from classical query complexity maximally. The paper studies the ladder of intermediate goals between the oracle separation and an unconditional separation of uniform decision classes and shows that three natural formalizations of its rungs are either trivial (truth-table collapse: quasi-linear time by the fast Walsh–Hadamard transform), false for every family (seed-compression barrier: any family generated from fewer seed bits than queries is distinguished from random by a fixed query set, and the computational variant is equivalent to one-way functions), or a restatement of a classical question (restricted-model trap: an explicit universal family whose label is any prescribed function of the seed, with exact Forrelation atoms and a proof of invariance). In the equal-footing model, where the restricted class evaluates the family itself, the trap dissolves for the whole orbit of the quadratic base pair under linear changes of variables and twists, by a derivative attack; a Kloosterman-sum family outside that orbit is constructed with provable atoms for every n ≥ 7 (fourth-moment identity, translation Parseval), on which the same-seed attacks of the paper are at chance; a uniform choice of the NO translation is open and stated as a conjecture supported by exact computation up to n = 25. Paper 2 — Low-Degree Instantiations of Forrelation Are Easy: Hidden Subspaces from Queries, Block Structure from Coefficients (whitebox.pdf, source whitebox-source.tar.gz). For the hidden Maiorana–McFarland family of Girish and Servedio with a polynomial h of constant degree whose top-degree form has trivial radical, O(4^d n^2) queries to f recover the hidden subspace as the radical of the top-degree form of f, after which the dual is evaluated by linear algebra; the low-degree instantiation is therefore easy already in the black-box model, and for d = 3 the radical hypothesis can be dropped. For the self-Forrelation proposal of Gheorghiu, Bravyi and Temme (as described in Gheorghiu's talk), the block decomposition of a sum of non-degenerate cubic blocks scrambled by an orthogonal matrix is recovered from the coefficient list by linear algebra through the symmetry algebra of the cubic form; degenerate blocks, a constant fraction of the self-dual bent cubics the proposal uses, defeat this algorithm, and the obstruction and the failure rate are given. Reproducibility archive (forrelation-barriers.tar.gz): the Lean 4 project (41 files in Forrelation/ plus a vendored subset of the OpenAI Math Release library for constant-depth circuits, Apache 2.0), every theorem depending only on the standard axioms; 35 certificate scripts with run_all.sh and the recorded results; the review records (several rounds of adversarial panel review per paper, three reviewers per round, syntheses, and an evidence audit of the citations against primary sources); and the project report. The analysis, code, Lean proofs, reviews and text were produced with large language models operated by the author, who checked every statement and certificate (see the AI disclosure sections of the papers).
Preprint and reproducibility archive; not peer reviewed. What this record contains. The full text of the manuscript "Identical Few-Particle Gauge Hamiltonians, Programmable Collective Charge Response" (M. J. Baek), its Supplementary Information with complete proofs, and the archive that certifies every closed-form value the paper states. The result. Few-particle dynamics are routinely used to infer collective response in paired quantum matter. This work constructs finite-range interacting response twins that defeat that inference exactly. For any prescribed finite p, two positive finite-range parents have complete static gauge Hamiltonians that coincide at every Peierls link phase on every sector N ≤ p and first separate at N = p+1; their zero-twist finite-density ground rays are the same Dicke condensate, yet their collective charge curvatures differ extensively. The obstruction has no universal depth, and the paper locates it exactly: the blind depth equals the spectator body order, the algebraic bound is independent of geometric range, and bounded range still bounds depth only through the number of sites a ball can hold — so no arbitrary-depth family of uniformly fixed range is claimed. Conversely, a structurally closed exact-pair tower closes at depth two. What is hidden is designable: with d(d+1)/2 displacement families the whole symmetric response-tensor difference is locally realizable at interior filling, and a triangular-lattice twin pair differs only in shear while both diagonal responses stay equal. A 4×4 hard-core-qubit discriminator gives an exact factor-of-two contrast with an internal null control and a state-preparation certificate in 17 equal-time settings. What is certified, and what is not. Results proved in closed form are stated as theorems and proved in full in the Supplementary Information; results established by exact rational or symbolic computation are labelled computer-assisted and carry the script that produces them; the 16-qubit discriminator is a blueprint with an end-to-end noise simulation, not a hardware demonstration, which is not claimed anywhere. Scope limits, open proof lines and one refuted conjecture are recorded explicitly rather than omitted. The archive. response_twins_unified_v1.0.zip contains the manuscript and Supplementary sources, the proof notes, the complete fail-closed verification harness (31 executed stages in release mode — 27 claim-bearing certificate stages, 1 non-claim diagnostic stage and three fail-closed gates — and 24 in quick mode) with one frozen log per stage, independent reimplementations of the load-bearing calculations, negative controls that must fail, the exact-arithmetic certificates behind every closed-form value in the paper, the figure-generation scripts, the scientific claim and provenance record (79 rows with status and scope notes, 50 of them naming the in-archive script or certificate that checks them, the rest saying in words why not), and a per-file SHA-256 manifest of all 209 payload files. Verifying it. Extract the archive and run python3 REPRODUCIBILITY/run_all.py --mode quick for the fast subset or --mode release for all 31 stages; bash BUILD.sh rebuilds both PDFs from source. The three gates check journal-format limits, the release payload against its manifest, and every number the documentation states about the artefacts. Running the harness does not modify the archive: all runtime output is written outside the immutable tree, so verification cannot invalidate the manifest. README.md separates reproducing the content (TeX Live 2023 or newer) from reproducing the archived PDF bytes, which needs the exact producing build recorded inside the PDFs. Licences. Manuscript, Supplementary Information and documentation CC BY 4.0; source code MIT; certificate data CC0 1.0. LICENSE.md is the authoritative per-file mapping and is included both in the archive and as a separate file on this record.
Cryptographie fondée sur les réseaux euclidiens dans une contexte quantique : preuves de sécurité et attaques L'émergence des machines quantiques crée des défis et des opportunités pour la cryptographie. En particulier, les preuves de sécurité doivent être révisées en raison des capacités quantiques des adversaires. Cette thèse propose deux contributions à cet égard : un résultat positif et un résultat négatif. La transformation de Fiat-Shamir avec des rejets est l’un des principaux paradigmes pour concevoir des schémas de signature post-quantiques. Une partie de cette thèse consiste en une analyse détaillée de cette transformation dans le modèle de l’oracle aléatoire quantique. Tous les travaux précédents proposant une analyse de sécurité de cette transformation ont négligé des détails subtils, compromettant la correction des preuves. Par conséquent, notre preuve de sécurité est la première de son genre à être correcte. De plus, nous analysons le temps d'exécution et la correction des signatures obtenues à partir de cette transformation. Le problème learning with errors (LWE) a été largement utilisé pour construire des schémas cryptographiques sécurisés contre les adversaires quantiques. Une hypothèse liée à LWE stipule que la génération d'une instance LWE sans connaître son secret est difficile pour tous les algorithmes polynomiaux. On peut utiliser cette hypothèse pour prouver la sécurité de certains arguments de connaissance succints. Bien que cela semble être une tâche difficile pour les algorithmes classiques, nous présentons un algorithme quantique polynomial qui génère des instances LWE sans connaître le secret. Notre algorithme invalide ainsi les analyses de sécurité de ces arguments de connaissance succints dans le contexte quantique.
Whether a quantum proof outperforms a classical one — both checked by the same efficient quantum verifier — is a question answered, so far, only relative to oracles. Beneath that answer is a structure with no quantum content at all: the difference between a resource one can copy and one one cannot. We show that this difference is cohomological. A witness that carries a copy map collapses every verifier to a memoryless sampler, so its distinguishing power is a functional of k-wise marginals alone; the obstruction to copying is a Čech class on a cover of a state by its measurement bases, and the Forrelation function of Aaronson and Ambainis is exactly the transition cocycle of that cover. The separation holds precisely when the class is nonzero: invisible from inside any single copyable chart, where it is a coboundary, and visible to the linear witness that reads the whole cover at once. Four familiar facts turn out to be four faces of the same class. Its non-vanishing is the no-cloning theorem; the dimension of its kernel is the Landauer erasure cost of the witness register; its representative on the standard/Hadamard cover is Forrelation; and the collapse of the copyable verifier onto one chart is why a classical witness, for these problems, cannot win. We make each face a finite, exactly computed certificate: on a corpus of distinguishing tasks built from Heisenberg–Weyl orbits, every depth-two adaptive sampler has advantage exactly zero — a total quantification over the strategy space, not a sampled estimate — while the linear witness reads a squared-Forrelation gap the kernel computes from truth tables through the Hadamard transform. Two independent exact computations agree on every verdict, and the engine that results either returns a gap two exact paths both certify, or refuses — and a refusal carries its own evidence, a certificate of exactly the obstruction that stopped it. The asymptotic separation of the underlying family is not ours; we cite it. What is ours is the identification — that a separation of complexity classes is, at bottom, a hole. All results below are machine-checked in Lean 4; the formal record and its axiom footprint are described in Section 8. The paper is legible in mathematics alone. Published by The Institute for Applied Ontological Mathematics.
We study independent one-message shuffling through a common channel with replacement adjacency and arbitrary deterministic backgrounds. Under one local Rényi budget, without a pointwise likelihood-ratio cap, the optimal uniform same-order rate is n−min⁡{1,α−1}n^{-\min\{1,\alpha-1\}}n−min{1,α−1} for fixed α>1\alpha>1α>1; a local KL budget alone gives no uniform amplification. We determine the exact asymptotic worst-case approximate-DP envelope at each fixed positive privacy parameter and the leading inverse calibration at failure probability d/nd/nd/n for all fixed α>1\alpha>1α>1. Matching upper bounds are uniform over channels and alphabets varying with nnn. At and above order three, the calibration coefficient is the square root of an attained local triple-variance frontier, realizable on at most nine output symbols. At order three we evaluate this frontier on a certified budget interval and identify the unique extremal ratio law. The same frontier determines the limiting central-window profile for α>2\alpha>2α>2 and the logarithmic moderate-window exponent. Under local χ2\chi^2χ2 diameter CCC, the exact asymptotic neighboring coefficient is 2C(C+5)/(C+4)2C(C+5)/(C+4)2C(C+5)/(C+4); we also give explicit finite amplification bounds and a fixed-channel background reduction. Formal verification. All statements of the paper have been formalized in Lean 4 (version 4.35.0) with Mathlib (release v4.35.0), including the computer-assisted order-three theorem, for which all certificate computations are checked by the Lean kernel. The formal proofs contain no sorry and use only the standard axioms propext, Classical.choice and Quot.sound. The project builds from scratch, every module passes a replay by the Lean kernel (leanchecker), and all theorems of the interface file Statements.lean, together with everything they depend on (69 078 declarations in total), were rechecked by the independent type checker nanoda. ChatGPT was used to write the Lean code and Claude to audit it; the author takes full responsibility for all results. Files. The PDF is the paper (24 pages). The ZIP archive Uniform_Renyi_arXiv_source_2026-11-09.zip is the LaTeX source. Its folder anc/ contains the exact rational polynomial certificate for the computer-assisted order-three theorem (verify_order_three_frontier.py, needs only the Python standard library) and further exact checks. The ZIP archive UniformRenyiShuffle-Lean-1.0.0-2026-11-09.zip is the Lean project UniformRenyiShuffle 1.0.0; its file MAP.md gives the Lean name of every statement of the paper. Changes from version 1. The Lean formalization is added. The paper and its LaTeX source are unchanged.
Dans cette thèse, nous étudions la vérifiabilité des calculs quantiques dans un contexte oraculaire. D'une part, nous connaissons plusieurs problèmes à oracle offrant démontrablement une séparation entre BPP et BQP. De l'autre, plusieurs techniques de preuves interactives ont été développées dans les vingt dernières années pour rendre les calculs quantiques faits par une machine BQP vérifiables par une machine BPP. Malheureusement, aucune de ces techniques ne relativise trivialement aux problèmes à oracles. Ceci nous mène à la question suivante : est-ce que ces problèmes à oracles admettent eux aussi des preuves interactives entre un prouveur BQP et un vérificateur BPP, ou est-ce qu'il serait démontrablement impossible d'en trouver une? Nous passerons en revue les principales techniques de preuves interactives dans le monde non relativisé, ainsi que les principaux problèmes à oracles séparant BQP de BPP. Puis, nous nous attarderons sur le problème de Simon et le problème Forrelation, pour lesquels nous introduisons dans cette thèse les premières preuves interactives avec prouveur BQP et vérificateur BPP mais légèrement quantique (et nous laissons ouverte la question à savoir s'il existe une telle preuve interactive avec un vérificateur BPP purement classique).