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).
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).
Dans cette thèse, nous étudions la cryptographie classique et quantique dans des modèles quantiques idéalisés. Des travaux antérieurs ont montré que les ressources quantiques peuvent être utilisées pour réaliser des tâches cryptographiques qui sont prouvées ou supposées impossibles dans le paradigme classique. Dans cette thèse, nous prouvons tout d'abord des bornes inférieures sur l'efficacité de n'importe quel algorithme quantique cherchant une couverture par sous-ensembles d'une fonction aléatoire, un problème conjecturé difficile et utilisé pour évaluer la sécurité du schéma de signature post-quantique SPHINCS+. Ensuite, nous étendons les résultats d'impossibilité existants concernant la construction de schémas de chiffrement à clé publique dans le modèle quantique de l'oracle aléatoire, en montrant qu'un type plus général de chiffrement à clé publique n'existe pas dans ce modèle. Nous étudions ensuite des hypothèses quantiques pour la cryptographie qui semblent plus faibles que les fonctions à sens unique, à savoir les générateurs d'états quantique pseudoaléatoires, ainsi que leur relation avec les schémas quantiques de chiffrement à clé publique et de signature, en clarifiant et en améliorant les constructions et les preuves d'impossibilité déjà existantes. Enfin, nous établissons l'importance de la taille des états quantique pseudoaléatoires en prouvant qu'un état quantique pseudoaléatoire ne peut pas être compressé, et nous progressons vers la démonstration qu'il ne peut pas non plus être amplifié.
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.
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.
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.
The 2-Forrelation problem provides an optimal separation between classical and quantum query complexity and is also the problem used for separating BQP and PH relative to an oracle. A natural question is therefore to ask what are the minimal quantum resources needed to solve this problem. We show that 2-Forrelation can be solved using Instantaneous Quantum Polynomial-time (IQP) circuits, a restricted model of quantum computation in which all gates commute. Concretely, signed 2-Forrelation can be solved by a classical random choice between two one-query IQP circuits, while the absolute-value variant uses two independent executions of this randomized procedure. This answers a recent open question of Girish (STOC 2026) on the power of commuting quantum computations. For the Raz-Tal distribution, this randomization is unnecessary. We use this to show that there is an oracle O such that IQPO⊆PHO, strengthening the result of Raz and Tal (STOC 2019). It also yields an oracle separation between IQP and DQC1. We prove Fourier growth bounds for multi-query IQP circuits, including bounds in terms of the size of their accepting set. Our results suggest a possible route toward decision-based quantum advantage within the restricted IQP model. The key ingredient is an algebraic identity of the quadratic function Q(x)=∑i<jxixj that allows extracting inner-product phases within an IQP circuit.
To predict what a quantum computer will output you have to work out an astronomical sum, and almost every term in it cancels to nothing. This work counts how many actually survive, and shows that number is out of reach of the standard tools: not the Tutte polynomial, not the usual weight counts, not the usual recursions. A binary linear code is a set of bit strings closed under bitwise addition — the object behind error-correcting codes. This paper studies a counting quantity attached to such a code, its survivor count. Where it comes from. Take a quantum circuit built from Clifford gates and T gates and ask for the expected value of its output. That expectation is a signed sum of exponentially many terms — quadratic Gauss sums over the two-element field — indexed by the codewords of a binary linear code. What that sum comes to is a well-studied quantity. This paper asks a different question about the same sum: not what it adds up to, but how many of its terms are really there. The number that survive is the survivor count of the code. What was already known, and what is taken up here. Whether one individual term survives is classical: a quadratic Gauss sum vanishes unless its form is trivial on the radical of its polar form, and is otherwise a power of two carrying the Arf sign. The weight attached to a single support is published as well, as the local isotropic-nullity weight of Bouchet's isotropic systems and of the restricted Tutte–Martin polynomial; the paper treats it as background rather than as a result of its own. What the paper takes up is the whole family at once. The census runs over all 2k codewords of a code, and the questions asked are what determines that total, what exact evaluation costs, which parameters and moduli buy an algorithm, and how far into the planar case each side reaches. What the paper proves. An exact criterion, and a closed form. The class sum at a support vanishes unless a certain half-weight form vanishes on a radical; where it does not vanish, the survivors are counted exactly by a power of two read off the dimensions of the code. One parity obstruction can remove them all. Consequently the survivor count depends only on the code's binary matroid. Separations. It is determined by none of the following: the Tutte polynomial; the cycle and cut weight enumerators taken together on planar graphs; the local marginals. It is not invariant under duality, and it obeys no constant-coefficient deletion–contraction recursion. The standard machinery that classifies graph and matroid invariants therefore does not reach it, and every line drawn below between easy and hard is drawn from the definition instead. A complexity map. Exact evaluation is #P-complete under deterministic polynomial-time Turing reductions, both on explicit generators and on graph cycle codes, and stays hard on four restricted graph families, on linear complementary dual codes, and at each fixed hull dimension. It is polynomial at bounded pathwidth, at bounded treewidth by a proved but unimplemented join step, on several code classes, and modulo 2, 3 and 6. Planar graphs. An exact algorithm running in time 2O(√n log n), conditional on three imported constructors, together with a #P-hardness statement conditional on one named planar Tutte evaluation being #P-hard. A bridge to quantum circuits, in both directions. Every Clifford+T circuit compiles to a single code and a single integer h whose output expectation is exactly (A + B√2)/2h+1, an identity holding exactly in the ring Z[√2], where (A,B) is that code's mod-8 weight census. Separately, a reverse construction makes the sign of such a bias hard for PromiseBQP at an exponentially small threshold, while at inverse-polynomial thresholds the same sign is decided classically with bounded error. Scope, and what is not claimed. Every statement carries exactly the status its proof supports and never a stronger one. Results resting on an unproved hypothesis carry that hypothesis at the head of their own statement, and no hypothesis is discharged anywhere in the paper. Nothing here claims, implies or denies any equality or separation of complexity classes. Where a comparison with the literature was not made, the paper says so at the statement it touches; nothing here asserts priority. Supplementary material. The consolidated record, and the proof files named in the paper's appendix, are deposited separately at doi:10.5281/zenodo.22804078. Abstract, as printed in the paper A Clifford+T circuit's output expectation is a signed sum of quadratic Gauss sums over the codewords of a binary linear code; counted here is how many survive. For C in F_2^m, let K_F be the dual subcode supported in a codeword F and R_F its radical: the survivor count S(C) counts, over all F, the cosets of K_F in the even-weight subspace on F with nonzero Gauss sum. An exact criterion is proved: the class sum at F vanishes unless the half-weight form twisted by the class representative s vanishes on R_F, and survivors at nonzero F number 2^(|F|-1-dim K_F-dim R_F+[F in the dual]), or none under a parity obstruction. So S is a binary-matroid invariant determined by none of the Tutte polynomial, the cycle and cut weight enumerators together on planar graphs, or the local marginals, not duality-invariant, and obeying no constant-coefficient deletion-contraction recursion. Exact evaluation is #P-complete under polynomial-time Turing reductions, and stays hard on four restricted graph families, on linear complementary dual codes and at each fixed hull dimension; it is polynomial at bounded pathwidth, at bounded treewidth by a proved but unimplemented join step, on several code classes and modulo 2, 3, 6. For planar graphs an exact 2^(O(sqrt(n) log n)) algorithm is given, conditional on three imported constructors, with hardness conditional on one named planar Tutte evaluation being #P-hard. Every such circuit compiles to one code and an integer h with output expectation exactly (A+B sqrt 2)/2^(h+1) in Z[sqrt 2], for (A,B) that code's mod-8 weight census; a reverse construction makes that sign PromiseBQP-hard at an exponentially small threshold, while inverse-polynomial ones are decided classically with bounded error. No complexity-class equality or separation is claimed or denied.