Forrelation de-oracleization: three barriers, Kloosterman atoms, and the low-degree instantiations (manuscripts, Lean formalization, certificates)
Hikaru Wakaura
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).