Oracle Separations in the Fourier Hierarchy

1 Introduction

• Between Hadamard layers, basis-preserving operations permute computational basis states and attach phases without creating superpositions.The number of Hadamard layers is the computation’s Fourier depth.Source: §1 · p. 3
• FH0 = P and FH1 = BPP, while two Hadamard layers suffice for Simon’s algorithm and, through phase estimation, factoring.The cited works are [Shi05].Source: §1 · p. 3
• Shi conjectured strictness at every level and asked for oracle separations; to the authors’ knowledge, no separation for k ≥ 2 had been proved.Without an oracle, the conjecture already entails P ≠ BPP at k = 0.Source: §1 · p. 3

1.1 Main results

• Forrelation is suited to the hierarchy because its alternating chain of functions and Fourier transforms matches the pattern of Hadamard layers and oracle calls.The K-fold version asks how strongly one Boolean function is correlated with the Fourier transform of another across a chain of K functions.Source: §1.1 · p. 3
• For every constant k ≥ 2, an oracle separates phase-query depth k from k + 1 using an OR of (2k −1)-fold Forrelation instances.Depth k + 1 decides the promise with O_k(1) queries, while depth k fails on some promised instance even with up to 2^n/(16k^2) queries.Source: §1.1 · p. 4
• For every constant k ≥ 2, an oracle separates standard-query depth k from k + 1 using an OR of (2k + 1)-fold Forrelation instances.Depth k + 1 decides with O_k(1) queries; depth k fails on some promised instance up to N^ηk queries, with ηk = 1/[2(2k −1)(2k +1)].Source: §1.1 · pp. 4–5
• Every phase-query FHk circuit is simulated exactly by a (k −1)-round parallel-query algorithm, while standard-query lower bounds use decision-tree factorization.The standard-query argument factors each basis-preserving block through decision-tree leaves, where the entire queried path is determined.Source: §1.1 · pp. 4–5
• At fixed depth k, phase access decides (2k −2)-fold Forrelation but not (2k −1)-fold Forrelation, whereas standard access decides the latter.The two oracle models therefore differ at a fixed Fourier depth, not only in where each hierarchy separates.Source: §1.1 · p. 4
• For odd order K = 2k −1, splitting at the middle oracle yields two states prepared with k Hadamard layers; a control-qubit interference test estimates Forrelation using one further Hadamard layer, the (k + 1)st.The order 2k −1 is the smallest Forrelation order separating depth k from k + 1; the next lower order, 2k −2, is decided at Fourier depth k.Source: §1.1 · pp. 5–6
• The paper’s new contributions include the adaptivity simulation, the odd-Forrelation connection, and a direct standard-query growth bound.The imported round-based growth bound is proved with a constant singly exponential in the number of rounds and Fourier level, enabling growing-depth results; the standard-query growth bound has such a constant from the outset.Source: §1.1 · pp. 5–6

1.2 Technical overview

• The technical overview proves the adjacent-level result by matching a depth-(k+1) decision with a depth-k lower bound using Forrelation.The same order parameter controls the upper-bound circuit’s depth and the Fourier-weight lower bound.Source: §1.2 · p. 6

1.2.1 The Forrelation problem

• Forrelation’s alternating oracle and Hadamard pattern makes its order directly relevant to Fourier depth and supplies the low-Fourier-weight hardness used in the lower bound.For the two-function case, a quantum algorithm estimates the correlation with one query to each function, whereas classical algorithms require 2^Ω(n) queries to distinguish near-unit from near-zero correlation.Source: §1.2.1 · p. 7

1.2.2 Fourier depth as query adaptivity

• A phase-query FHk circuit is reproduced exactly by k−1 rounds of parallel queries, connecting Fourier depth to round-based Fourier-growth lower bounds.Queries before the first Hadamard layer contribute only a global phase, and those after the last commute with measurement.Source: §1.2.2 · pp. 7–8

1.2.4 From a distributional gap to an oracle

• An OR amplifies the distributional gap; a hybrid argument isolates a hard copy, and diagonalization combines hard instances into an oracle.The growth bound remains valid after fixing the other copies, enabling the hybrid step.Source: §1.2.4 · p. 9

1.2.3 Odd Forrelation and the interference test

• At odd order K = 2k−1, depth k+1 decides Forrelation, while depth-k circuits have only o_k(1) distinguishing advantage in the stated query range.The depth-(k+1) decision has error 2^-n.Source: §1.2.3 · p. 8, §1.2.4 · p. 9

1.2.5 The standard-query separation

• For standard queries, the lower bound factors each basis-preserving block through decision-tree leaves and uses a larger Forrelation order, K = 2k+1.The direct Fourier-growth bound is restriction-stable; the larger order accommodates its weaker exponent.Source: §1.2.5 · pp. 9–10

1.2.6 Further results and connections

• Forrelation of order Θ(log n) is solvable in BQP with polynomially many queries but at no Fourier depth up to 1 relative to an oracle.Tuning the order yields BQP problems of any prescribed Fourier depth up to c log n; these results also hold in the standard-query model.Source: §1.2.6 · p. 10
• The oracle separations use correlated-Gaussian structured distributions that lack known promise-certified sampling; the proposed explicit second-level candidate remains a program rather than a theorem.Its conjectured coefficient decay is proved in one parameter range with a weaker prefactor and conjectured in the other; the main-text separations do not depend on it.Source: §1.2.6 · pp. 10–11

Prior Fourier-hierarchy work

• Shi introduced the hierarchy and posed the adjacent-level oracle question; prior work established the first-level separation and the power of low levels, but the paper reports no earlier adjacent-level separation beyond FH1 versus FH2.Shi also observed that FH2 contains factoring via phase estimation, and later work studied verification, Merlin–Arthur protocols, and IQP-type circuits.Source: §1.3 · p. 11

Rounds of adaptivity and parallel queries

• Round-based lower bounds for Forrelation and Fourier-growth bounds provide tools for relating parallel-query algorithms to Fourier depth.Girish, Sinha, Tal, and Wu give round-based bounds; the paper uses their result for phase queries and a separate coherent-decision-tree argument for standard queries.Source: §1.3 · pp. 11–12

Forrelation and its lower bounds

• Forrelation is a recurring separation problem, and Bansal and Sinha [BS21] prove an optimal randomized query lower bound for k-Forrelation using a Fourier-weight criterion.The paper imports that criterion; it also uses classical lower bounds for extremal Forrelation as black boxes.Source: §1.3 · p. 12

Hierarchies of hybrid quantum depth

• Hybrid quantum-depth models and the Fourier hierarchy measure different resources: quantum-classical alternations versus layers of coherent interference.The models are described as incomparable to bounded-round parallel-query algorithms and to each other.Source: §1.3 · p. 12

Restricted quantum models and pseudorandomness

• Work on noisy quantum models uses Forrelation and Fourier-growth arguments, but the resource being restricted there is mixedness rather than Fourier depth.The cited results do not establish containment between those models and a fixed Fourier level; the paper also frames bounded-depth oracle distinguishers as a pseudorandomness setting distinct from arbitrary efficient quantum distinguishers.Source: §1.3 · p. 13

Paper organization

• Section 2 sets up the model, analytic tools, and prior results used in the proofs.The overview identifies Sections 3 and 4 as the locations of the main theorem proofs.Source: §1.4 · p. 13
• Section 3 proves Theorem A, Section 4 proves Theorems B and C, and Section 5 locates the hierarchy relative to PH and BQP and addresses relativization.Theorem A is proved in Sections 3.1–3.4, and Theorems B and C in Sections 4.1–4.4.Source: §1.4 · p. 13
• Appendix A proposes a candidate hard distribution, Appendix B proves a Fourier-growth bound, and Appendix C gives a self-contained proof of a non-adaptive Fourier-growth bound.Sections 3.5, 3.6, and 4.5 are not used in the main proofs and can be skipped on a first reading.Source: §1.4 · p. 13

2.1 The Fourier hierarchy

• For k ≥ 1, phase queries can be implemented with standard queries at the same depth, but standard-query blocks can adapt later queries to earlier answers.Converting phase access into a written answer bit requires target interference and increases Fourier depth.Source: §2.1 · p. 14
• The paper formalizes FH_k circuits as fixed global Hadamard layers separated by basis-preserving blocks, with indexed, length-preserving phase or standard oracle access.The indexed oracle family permits coherent selection of a function index; the distinguished index carries the constant-zero function.Source: §2.1 · pp. 14–15
• For every oracle, standard-query FH0 equals P^O and FH1 equals BPP^O, while phase-query FH1 acceptance is independent of the oracle.At depth zero, standard queries allow deterministic classical adaptive oracle computation; one Hadamard layer yields the relativized BPP characterization.Source: §2.1 · pp. 16–17

2.2 The SWAP test

• The SWAP-test lemma gives the acceptance probability for comparing two pure states of equal dimension using a controlled-SWAP and a final Hadamard.The test accepts when the control measurement is 0.Source: §2.2 · p. 17

2.3 Fourier weight and concentration inequalities

• The preliminaries define level-ℓ and biased Fourier weights, restrictions, and Hoeffding tail bounds, including concentration bounds for empirical Bernoulli frequencies.A restriction fixes some coordinates and leaves the others free.Source: §2.3 · p. 18

2.4 Fourier growth of bounded-round algorithms

• The phase-query lower bounds use bounded-round Fourier growth, whose bound is stable under restrictions, has a singly exponential constant in rℓ, and admits a sharper non-adaptive form.The non-adaptive result improves the dependence on parallel queries and the constant’s dependence on ℓ.Source: §2.4 · pp. 18–19
• Acceptance probabilities of non-adaptive quantum algorithms making t parallel queries have the stated form and obey the Fourier-growth bound.The passage identifies B as U†1ΠU1 for the acceptance projector Π.Source: §2.4 · p. 19
• Theorem 2.15 gives the sharpened threshold at the second level.The passage points to Remark 3.12 for this consequence.Source: §2.4 · p. 20
• Theorem 2.15’s growth bound is used in Appendix A.Its proof is self-contained and appears in Appendix C.Source: §2.4 · p. 20

3 An oracle separation at every level

• For every fixed k ≥ 2, an explicit promise problem is decidable by depth k+1 with constantly many queries but not decidable by depth k.The proof combines bounds on depth-k circuits with input distributions and an advantage criterion that apply to odd and even Forrelation orders.Source: §3 · p. 20

3.2 Simulation of Fourier depth by bounded adaptivity

• In the standard-query model, earlier oracle answers can affect later query addresses, so the phase-query round simulation does not apply and a separate lower-bound argument is needed.Within a block, replacing that adaptivity by parallelism can require exponentially many queries; the standard-query proof instead uses a decision-tree growth bound.Source: §3 · p. 20, §3.2 · pp. 25–26

3.1 Odd Forrelation at depth k + 1

• A depth-(k+1) circuit using k phase queries estimates the (2k−1)-fold Forrelation value itself, using an odd-order split into two depth-k states and a control-qubit interference test.The circuit's acceptance probability is 1 + Φ_{2k−1}; the earlier SWAP-test construction uses 2k−1 phase queries and returns 1 + Φ_{2k−1}^2.Source: §3.1 · pp. 21–22

3.2 Simulation of Fourier depth by bounded adaptivity

• Every FH_k phase-query circuit making q queries is simulated exactly by a quantum algorithm with k−1 rounds of at most q parallel queries.In particular, polynomial-query FH_2 computations have a non-adaptive parallel-query simulation, while FH_1 acceptance probabilities are oracle-independent.Source: §3.2 · pp. 24–25
• The round simulation is one-way: its arbitrary inter-round unitaries are more general than the single global Hadamard layers allowed in FH_k.Thus round-model weight bounds apply to FH_k, but the simulation does not characterize the phase-query class exactly.Source: §3.2 · p. 25

(The weaker bound with da

• A standard-query FHk circuit can be simulated after classical preprocessing with 3k −2 rounds of parallel phase queries, each of width at most 2q+1.Each interior block uses three rounds; standard-query blocks can branch on answers, so the one-round simulation used for phase-query blocks does not directly extend to them.Source: (The weaker bound with da · pp. 26–28
• The Fourier-growth corollary bounds the level-ℓ weight of FHk acceptance probabilities and all their restrictions, providing the Fourier control used in the lower bound.At k = 2, a separate corollary gives a sharper growth bound; the direct quadratic-form weight bound would not suffice.Source: (The weaker bound with da · p. 28

3.3 A promise problem separating depth k from depth k + 1

• The OR of Forrelation instances amplifies the structured distribution of Bansal and Sinha [BS21], whose large Forrelation value occurs only with probability of order δ.The construction uses m = δ−1 independent copies so the resulting distributions are concentrated sufficiently on the two sides of the promise.Source: §3.3 · pp. 29–30
• For every fixed k ≥2, a uniform polynomial-size FHk+1 family decides the promise problem with O_k(1) phase queries and error 1/3.Using O_k(n) phase queries improves the error bound to 2^-n.Source: §3.3 · p. 30
• For every fixed k ≥2, any FHk circuit making at most N^ck phase queries fails to decide ORFK,n, even with arbitrary size and without a uniformity requirement.The theorem sets ck = 1/(4(2k−1)(2k−2)) and applies for sufficiently large n.Source: §3.3 · p. 31
• At depth k, every circuit making q≤N^ck phase queries has o_k(1) distinguishing advantage between the structured and uniform ensembles.The corresponding promise problem has no depth-k solver with worst-case error below 1−e^-6/2, while the depth-(k+1) circuit fails with probability 2^-n.Source: §3.3 · p. 32
• For 2≤k≤c n^(1/3), depth k+1 decides ORF_{2k−1,n} using 2^O(k) phase queries, whereas depth k fails on some promised instance with 2^{c′n/k^2} queries.For nondecreasing polynomial-time computable k(n)≤c log n, the construction yields a uniform polynomial-size deciding family; when k(n)=o(log n), its query count is n^o(1).Source: §3.3 · pp. 33–34

3.4 The separation theorem

• For every constant k≥2, an oracle separates FH_k from FH_{k+1}; a single oracle can make every adjacent level strict simultaneously.The separation diagonalizes against uniform depth-k families, while the depth-(k+1) circuit decides the constructed language.Source: §3.4 · pp. 34–35
• A fixed oracle with a deterministic polynomial-time evaluator cannot yield a relativized separation unless the corresponding unrelativized Fourier levels already differ.The section leaves efficiently computable hard instances open; its hard distributions do not have the local structure needed for the discussed succinct-oracle approach.Source: §3.4 · pp. 35–36
• The depth-2 versus depth-3 instance uses the OR of 2^15 threefold Forrelation instances: depth 3 decides it, while depth 2 with at most 2^(n/6) phase queries fails on some promised instance.Depth-2 computations are simulated exactly by non-adaptive quantum query algorithms, while the third Hadamard layer supplies the additional round.Source: §3.4 · p. 36

3.5 Even Forrelation at Fourier depth k

• For every fixed k≥2, a uniform polynomial-size depth-k circuit using 2k−2 phase queries decides (2k−2)-fold Forrelation, so this even-order problem cannot separate depth k from depth k+1.The circuit uses two registers, a coupling between them, and accepts when the parity of their measured outcomes is zero.Source: §3.5 · pp. 36–37
• At even order, an inner-product parity couples the two interfering copies as the SWAP test does, saving one layer; the symmetric construction uses 2(k−1) oracles and does not extend to order 2k−1.For k=2, the construction is closely related to Buzet and Chailloux [BC26] and extends their quadratic-identity approach to every even order.Source: §3.5 · pp. 37–38
• The (2k−1)-fold Forrelation problem is the smallest-order ORFK,n separator of FHk from FHk+1, but no fixed-order ORFK,n separates FHk from its (k−1)-round parallel-query model.Orders K≤2k−2 are decidable by both models, while orders K≥2k−1 remain hard for both under the stated width bound; whether mixed, planted, or length-varying constructions separate them remains open.Source: §3.5 · p. 38

3.6 Classical simulation at the second level

• An FH2 circuit’s acceptance probability can be estimated classically to additive error ε with high probability, using query access to the oracle and a description of the circuit.The estimator uses a quadratic form in an oracle-dependent unit-modulus vector and an oracle-free contraction; its query bound depends on the number of Fourier wires, D=2^w, and it allows arbitrary ancillas.Source: §3.6 · pp. 38, 40
• The quadratic-form estimator applies to FH2 but fails for Fourier depth k ≥3: acceptance becomes a degree 2(k−1) form in d, and the corresponding higher-level parallel-query simulation case remains open.Source: §3.6 · p. 40
• For w=n and constant q and ε, the second-level simulation is tight up to polylogarithmic factors on sign-decision 2-Forrelation, whose classical randomized query complexity is eΘ(N).Buzet and Chailloux [BC26] realize sign-decision 2-Forrelation at Fourier depth two; the result also establishes the non-adaptive r=1 case of the simulation conjecture under the stated wire-count restriction.Source: §3.6 · p. 40

4 The standard-query hierarchy

• At fixed Fourier depth, standard queries are strictly more powerful than phase queries; no constant number of Hadamard layers or classical preprocessing recovers the difference.Source: §4 · p. 40
• Standard-query FH_k cannot decide (2k+1)-fold Forrelation, while standard-query FH_{k+1} decides it, yielding an adjacent-level separation.Theorem 4.5 bounds level-ℓ Fourier weight so its exponent falls below the Bansal–Sinha criterion’s threshold at K = 2k + 1.Source: §4 · pp. 40–41

4.1 A decision-tree factorization

• Retaining each decision-tree branch in an auxiliary leaf label factors an adaptive block into an isometry and a contraction, restoring norm control for the product argument.The shared leaf label makes adjacent factors agree on the branch, replacing the unavailable round simulation.Source: §4.1 · p. 41

4.2 Fourier growth along the operator product

• The Fourier growth proof converts factor-incidence profiles to certificate profiles, then cuts the operator product to balance ambient-dimension costs against query-path lengths.Certificates wholly on one side of the cut contribute a power of the ambient dimension, while certificates crossing it lie on a query path of length at most q.Source: §4.2 · pp. 43–44
• The split-based norm count in the Fourier-growth proof keeps the exponent at E_r ≤ ℓ rather than 2ℓ by separating row-side and column-side choices.Certificates created or erased at the split are unrestricted on only one side, while those passing through it are unrestricted on neither.Source: §4.2 · p. 49

4.3 Application to standard-query Fourier depth

• Theorem 4.5 bounds restricted Fourier growth for standard-query FH_k circuits, using a product of 2k−1 decision-tree factors and query counts q_0 and q* with q_0 + q* ≤ q.The initial block contributes q_0; each other query block has depth at most q*, the maximum block query count.Source: §4.3 · pp. 49–50
• For every fixed s ≥ 2, a uniform standard-query FH_s circuit makes s queries to compute the (2s−1)-fold Forrelation test.For odd-fold Forrelation, the middle query writes its answer into an ancilla, allowing the final comparison without another Hadamard layer.Source: §4.3 · p. 50

4.4 The adjacent-level separation

• For all sufficiently large n, ORF_{K,n} is decidable in standard-query FH_{k+1} with O_k(1) queries, while FH_k circuits with at most N^η_k queries fail on some promised input.The upper bound uses the standard-query Forrelation test; the lower bound follows by applying the Fourier-growth bound to restrictions.Source: §4.4 · pp. 51–52
• For 2 ≤ k ≤ c n^(1/3), the growing-depth promise problem has a standard-query FH_{k+1} solver with 2^O(k) queries, while FH_k circuits fail below the stated exponential query threshold.For nondecreasing, polynomial-time computable k(n) ≤ c log n, the corollary also gives a polynomial-size oracle separation; when k(n) = o(log n), the deciding circuit uses n^o(1) queries.Source: §4.4 · p. 52
• For every constant k ≥ 2, an oracle separates standard-query FH_k from FH_{k+1}.The diagonalized language is not decided by any bounded-error standard-query FH_k family, but is decided by a uniform standard-query FH_{k+1} family.Source: §4.4 · p. 53
• Even after at most N^ck adaptive classical queries, followed by at most N^ck phase queries, no depth-k algorithm decides ORF_(2k−1),n with error at most 1/3 for sufficiently large n.The resulting oracle separation persists when the phase model is given an adaptive classical preprocessing stage.Source: §4.4 · p. 54
• At depth k, standard access solves (2k −1)-fold Forrelation while phase access does not, separating their depth-k classes via its OR.Phase access solves (2k −2)-fold Forrelation, whereas standard access solves (2k −1)-fold Forrelation.Source: §4.4 · pp. 53–54

4.5 Standard queries versus bounded Fourier depth

• The standard-query advantage is not bounded by any constant phase depth: pointer chasing separates the models, because standard queries permit adaptive classical preprocessing while phase queries do not.A phase circuit's initial query block contributes only a global phase; a standard query writes its answer into a register, enabling classical adaptivity.Source: §4.5 · pp. 54–56
• With probability 1 over random oracle functions, every r-round quantum family with poly(n) parallel queries per round and r + 1 ≤ d(n) fails to decide L_O at all but finitely many lengths.L_O is in P^O for every oracle O.Source: §4.5 · pp. 55–56
• For every constant j ≥1, some oracle has FH0,std not contained in FHj,phase; an oracle also has P not contained in the union of all phase levels.The latter separation uses a pointer-chasing schedule d(n) = max{1, ⌈log2 n⌉}.Source: §4.5 · p. 56

5.1 The second level and the polynomial hierarchy

• FH1 is contained in PH relative to every oracle, but some oracle places FH2 outside PH in both the phase- and standard-query models.The phase-query separation is already achieved non-adaptively, with one round of parallel quantum queries.Source: §5.1 · p. 58
• Relative to one oracle, the phase-query hierarchy is incomparable with P: P is outside every level, while its second level is outside PH.The same oracle can witness both statements by interleaving the constructions on disjoint input lengths.Source: §5.1 · pp. 58–59

5.2 Bounded Fourier depth versus BQP

• An oracle has a BQP language outside every Fourier-depth schedule d(n) ≤ 1/4 log2 n, and thus outside every constant Fourier level.The hard problem uses Forrelation of order K(n)=⌈log2 n⌉; the BQP algorithm uses polynomially many queries.Source: §5.2 · pp. 59–60
• For each admissible schedule 2 ≤ d(n) ≤ c log n, an oracle gives a BQP language of Forrelation order 2d(n)-1 outside FH_d.It is decidable with poly(n) queries, or n^o(1) queries when d(n)=o(log n); if d(n)→∞, FH_d is strictly contained in BQP relative to that oracle.Source: §5.2 · pp. 60–61

5.3 A collapsing oracle: the adjacent-level question does not relativize

• A PSPACE-complete oracle makes every standard-query level and every phase-query level from FH2 onward equal PSPACE, so adjacent-level separations do not relativize.The first phase level is degenerate; whether it also equals the second level for this oracle is the unaddressed question FH1=PSPACE.Source: §5.3 · pp. 61–62
• Relative to a PSPACE-complete oracle, FH_2, every FH_k for k ≥2, and BQP^O all equal PSPACE as language classes.The phase model decides PSPACE at Fourier depth two, and the upper inclusions place the classes within PSPACE.Source: §5.3 · pp. 62, 64
• A single oracle separates every adjacent pair at every level k ≥2 in both the phase and standard query models.The separating languages are decided at depth k + 1, while every depth-k machine fails on them at infinitely many lengths.Source: §5.3 · pp. 62–63
• Randomly planting blocks at designated lengths makes each clocked level-k machine fail at infinitely many lengths, almost surely, for every model and k.At designated lengths, the single-block advantage bound applies uniformly after conditioning on earlier blocks.Source: §5.3 · p. 63
• Consequently, no relativizing argument resolves Shi’s conjecture in either direction or either query model.The two oracles exhibit opposite behaviors: one separates all adjacent levels, while the PSPACE-complete oracle collapses them.Source: §5.3 · pp. 63–64

• The optimal query-threshold exponent remains open in both access models; the current separation has c_k = Θ(1/k^2).Source: §6 · p. 64
• Whether one additional Hadamard layer suffices to separate the access models remains open, even though their fixed-depth separation survives adaptive classical preprocessing.Source: §6 · p. 64
• Proving Conjecture A.10 would make the proposed sign ensemble an explicitly defined hard distribution for FH2 ⊊ FH3.Source: §6 · p. 64
• An intrinsic characterization of Fourier depth is open, including whether FHk differs from the (k −1)-round parallel-query model.Source: §6 · p. 64
• NP containment in standard-query levels depends on the oracle, and the paper’s separations plus a collapse oracle show that relativizing arguments cannot resolve Shi’s conjecture.Source: §6 · p. 64

• The appendix proposes an explicit instance toward FH2 ⊊ FH3 because the existing unconditional separation uses a rounded correlated-Gaussian distribution that is not known to be samplable with a promise certificate.Source: A Toward an explicit hard instance · p. 70
• Its analysis reduces to one Fourier coefficient, proves the conjectured exponent with a weaker prefactor in one parameter range, and states Conjecture A.10 for the general case.Source: A Toward an explicit hard instance · p. 70
• The authors motivate explicit instances as a step toward evaluating hard instances without an oracle, since the adjacent-level question does not relativize.Source: A Toward an explicit hard instance · p. 70

• The structured Yes ensemble is (A, U · V, B), while the No ensemble consists of three independent uniform sign functions; U and V are tie-broken signs associated with A and B.Source: §A.1 · p. 70
• The middle oracle is a phase correction making every structured-instance term nonnegative, with Φ3’s mean tending to 2/π while the No-case value concentrates near zero.Source: §A.1 · p. 71
• Under the promise, the Yes case has constant mass with Φ3 ≥ 1/4, while the No case has Pr[|Φ3| > 1/12] ≤ 144/N.Source: §A.1 · p. 71
• A uniform polynomial-size FH3 circuit decides the sign Forrelation promise problem using O(n) phase queries and error at most 2^-n.Source: §A.1 · p. 71
• The ensemble would yield an oracle separation FH2 ⊊ FH3 only under Conjecture A.10, via direct-product amplification and a hybrid argument.Source: §A.1 · p. 72

A.2 One Fourier coefficient of a product of threshold functions

• The ensemble analysis reduces to low-degree Fourier coefficients of gY, a product of |Y| threshold functions that takes values in {−1, 0, 1}.The defining linear forms are orthogonal and regular, with each coefficient having modulus N^-1/2.Source: §A.2 · pp. 72–73
• Γ(X, Y) vanishes when |X| + |Y| is odd, and translation symmetries impose sign identities that force further coefficients to vanish.If X is invariant under a translation x0 with x0 · ΣY = 1, then Γ(X, Y) = 0, with a dual condition in Y.Source: §A.2 · p. 73
• Signs of two distinct Fourier coefficients are exactly uncorrelated, not merely nearly so.This follows from the symmetry-based vanishing result applied at X = ∅.Source: §A.2 · p. 73
• The unconditional bound conditions on coset sums, uses the conditional second moment of the product over X, then applies Cauchy–Schwarz across cosets.The signs depend only on coset sums and independent tie-breaking signs; conditioned on those sums, restrictions of A to distinct cosets are independent.Source: §A.2 · p. 74
• When |X| ≥ |Y|, the section proves unconditional decay for Γ(X, Y), while the bound does not capture decay in |Y| when |X| < |Y|.At X = ∅, Theorem A.8 gives only a vacuous bound; the coefficients E[gY] in the complementary range remain open.Source: §A.2 · p. 75

A.3 The conjectured decay rate and its consequences

• The lower-bound advantage reduces to correlations Γ(X, Y) with Y nonempty, and the conjecture addresses their decay in |X| and |Y|.The moments under the structured ensemble factor as Γ(X, Y)Γ(Z, Y), while every nonconstant moment under Non is zero.Source: §A.3 · p. 75
• For |X| ≥ |Y|, Corollary A.9 proves the conjectured exponent unconditionally, though with a 2^O(d^2) prefactor rather than the conjectured d^C d.For q = o(n), this unconditional result suffices in that range, leaving the conjecture needed only when |X| < |Y|.Source: §A.3 · pp. 76–77
• Conjecture A.10 predicts an additional N^-1/4 factor for each further element of Y, making the decay compound rather than accumulate.The section identifies the exponent as new in the range |X| < |Y|; the conjectured prefactor remains unproved in both ranges.Source: §A.3 · p. 76
• Assuming Conjecture A.10, every FH2 circuit making q ≤ n^γ phase queries distinguishes Yes_n from Non with advantage at most 2^-Ω(n).The result is conditional on the conjectured decay and, combined with Theorem A.4, would yield an explicitly defined hard distribution for FH2 versus FH3.Source: §A.3 · p. 76
• Conjecture A.10 makes the level sum decay uniformly: its exponent exceeds the Fourier-growth exponent by ℓ/12, yielding an exponentially small bound.The proof bounds each level-ℓ term by 2^-nℓ/24 for sufficiently large n.Source: §A.3 · p. 77
• The proof uses the non-adaptive Fourier-growth bound of Girish, Sinha, Tal, and Wu [Gir+24]; a general growth bound would reduce the admissible query range.The conjectured prefactor is needed in both ranges for larger polynomial query counts; for q = o(n), only |X| < |Y| needs the conjecture.Source: §A.3 · pp. 75, 77

B A single-exponential constant in the Fourier-growth bound

• The growth theorem has a single-exponential constant 2^O(rℓ), uniformly over Fourier levels ℓ ≥ 1.The assignment count is evaluated in closed form using Möbius inversion.Source: B A single-exponential constant in the… · pp. 78–79
• The assignment count is rewritten as maps assigning each element to an admissible lower-index set, so its value depends only on the size profile.The bijection uses the partition of the symmetric difference into the disjoint sets J(c).Source: B A single-exponential constant in the… · p. 78
• A single-exponential constant permits Fourier depth k = O(n^1/3) in Corollary 3.22; a constant with an exponential logarithm would support only k = O((log n)^1/3).With the single-exponential constant, the binding constraint becomes the deciding circuit's 2^Θ(k) queries.Source: B A single-exponential constant in the… · pp. 78, 80

C Proof of the non-adaptive growth bound

• The bound is stable under restrictions, and the proof is written out because the application depends on how its constant grows with ℓ.The authors attribute the method to Girish, Sinha, Tal, and Wu [Gir+24] and claim no novelty for it.Source: C Proof of the non-adaptive growth bound · p. 80
• Each shape-specific contribution is factored in two ways, its four factors are norm-bounded, and the geometric mean of the resulting bounds is summed over ℓ + 1 shapes.The proof uses the two factorizations because each imposes the size constraint in a different direction.Source: C Proof of the non-adaptive growth bound · pp. 80–81
• The level-ℓ bound is L1,ℓ(f) ≤ (ℓ + 1)(Mτ)^(ℓ/4).The proof groups the level weight by the pair of sizes describing the symmetric difference.Source: C Proof of the non-adaptive growth bound · pp. 80–81