Forrelation: A Problem that Optimally Separates Quantum from Classical Computing

1 Introduction

• The Speedup Question asks whether a problem can require Ω(N) randomized queries yet only 1 quantum query.Source: §1 · p. 2
• The authors ask whether exponential quantum speedups share a common cause or can be captured by a single problem or technique.Source: §1 · p. 2
• Buhrman et al. asked for a maximal property-testing separation; the best Simon-based result then used Ω(N) classical and O(log N log log N) quantum queries.Source: §1 · p. 2
• Forrelation had a 1-query quantum algorithm and an Ω(N^1/4) randomized lower bound; period-finding's O(1) versus eΩ(N^1/4) gap required non-Boolean queries.Requiring Boolean queries multiplies the quantum query complexity by O(log N).Source: §1 · pp. 1–2

1.1.1 Maximal Quantum/Classical Separation

• Forrelation asks whether two Boolean functions have substantial correlation with one another through the Fourier transform.The input size is defined as N = 2^n.Source: §1.1.1 · pp. 2–3
• Forrelation is solvable with 1 quantum query and yields the largest quantum-versus-classical separation then known in the black-box model and property testing.The paper presents its lower bound as an improvement over prior work, though the supplied theorem fragments do not preserve its full quantitative expression.Source: §1.1.1 · p. 3

1.1.2 Proof of Optimality

• Any t-query quantum algorithm on an N-bit string can be simulated to constant additive error by a nonadaptive randomized algorithm using O(N^(1−1/2t)) queries.The simulation succeeds with high probability; the stated result assumes t = O(1).Source: §1.1.2 · p. 4
• This bound rules out a constant-versus-linear quantum–classical query gap, resolving Buhrman et al.’s open question in the negative.The paper leaves open the possibility of an O(log N)-versus-ẽΩ(N) gap and conjectures such a gap may be possible.Source: §1.1.2 · p. 4
• The authors conjecture that condition (ii) in their polynomial-estimation theorem can be removed, and establish this in the special case k = 2.Condition (ii) is identified as block-multilinearity in the supplied theorem passage.Source: §1.1.2 · p. 4

1.1.3 k-fold Forrelation

• k-fold Forrelation is solvable with ⌈k/2⌉ quantum queries; with functions given explicitly and k = poly(n), it is BQP-complete.The problem generalizes Forrelation to k Boolean functions and a twisted sum.Source: §1.1.3 · p. 4
• For even k, the authors conjecture that k-fold Forrelation achieves the optimal k/2-versus-ẽΩ(N^(1−1/k)) quantum–classical query separation.Source: §1.1.3 · p. 5

1.1.4 Other Results

• Fourier Sampling of a Boolean function uses 1 quantum query but requires Ω(N/log N) classical queries, exceeding the largest possible decision-problem gap established here.The paper also extends one-query simulation to bounded degree-2 polynomial estimation and conjectures an O(N^(1−1/k)) query bound for bounded degree-k polynomials.Source: §1.1.4 · p. 5

1.2.1 Randomized Lower Bound

• The lower-bound argument transfers Real Forrelation to Boolean Forrelation by rounding, then uses Gaussian geometry and martingale concentration to control how queries reveal correlations.The deviations from near-orthogonality form an unbiased random walk; the polynomial-size vector set allows a second application of Gaussian Azuma to bound individual deviations.Source: §1.2.1 · pp. 5–6

1.2.2 Randomized Upper Bound

• Any t-query quantum algorithm on an N-bit input can be simulated to constant additive error by a nonadaptive randomized algorithm using O(N^(1−1/2t)) queries.The proof represents quantum acceptance probabilities with bounded block-multilinear polynomials, balances influential variables by splitting, then estimates by random sampling.Source: §1.2.2 · p. 7
• An O(N)-query randomized algorithm estimates any bounded degree-2 polynomial, using influential-variable identification and splitting instead of block-multilinear variable splitting.The extension relies on Fourier-analytic results of Dinur et al..Source: §1.2.2 · p. 8

1.2.3 Other Results

• k-fold Forrelation’s defining sum is a circuit output amplitude, and a gadget construction cancels unwanted Hadamards to encode arbitrary quantum circuits.Hadamard and CCPHASE gates are universal, but the Forrelation circuit inserts Hadamards between every pair of function-phase gates.Source: §1.2.3 · p. 8
• For Fourier Sampling, a single output’s probability cannot depend on the truth table appropriately until Ω(N/log N) function values have been queried classically.The argument focuses on the probability of outputting 0^n and uses a binomial calculation.Source: §1.2.3 · p. 8
• The section establishes a randomized lower bound for k-fold Forrelation for every k ≥ 2 and gives general Hamming-distance conditions supporting its property-testing separation.Pairs far from the set of low-forrelation pairs have high forrelation, while generic pairs close in Hamming distance have close forrelation values.Source: §1.2.3 · p. 8

1.3 Discussion

• The discussion contrasts Forrelation’s one-query quantum complexity with query costs for Simon’s problem, Glued-Trees, and ORs of independent Forrelation instances.For an N^(1/2+c) randomized lower bound, the stated construction uses Θ(N^c) quantum queries by taking an OR of N^(2c) instances of size N^(1−2c).Source: §1.3 · p. 9
• The paper presents k-fold Forrelation as a candidate to break the apparent N barrier and conjectures optimal separations for constant k.For k > 2, the analysis moves from a low-dimensional subspace to a nonlinear manifold, making posterior calculations harder.Source: §1.3 · p. 9
• Extending the randomized estimation algorithm from block-multilinear polynomials to arbitrary bounded degree-k polynomials appears to require generalizing the machinery of Dinur et al..The paper reports achieving this extension only for k = 2.Source: §1.3 · p. 10
• The authors leave open whether any efficiently described Boolean functions have Forrelation that is useful to estimate when their structure offers no fast classical method.They compare this prospective role to applications of factoring and discrete logarithms for period-finding.Source: §1.3 · p. 10
• Open questions include tightening Forrelation’s randomized lower bound, extending results to non-Boolean functions, and finding the largest separations for sampling, search, and relation problems.The discussion also asks how small the error can be for a one-query quantum algorithm and whether forrelatedness itself behaves well as a property-testing problem.Source: §1.3 · p. 10

3.1 Query Complexity

• Query complexity counts the maximum number of input queries over valid inputs; bounded error here means error at most 1/2−ε for constant ε > 0.This convention accommodates the one-query Forrelation algorithm with error 2/5; amplification reduces error at a constant-factor query cost.Source: §3.1 · p. 12

3.2 Forrelation

• k-fold Forrelation can be viewed as estimating the all-zero output amplitude of a circuit with function queries interleaved with Hadamard gates.The paper gives a bounded-error algorithm using ⌈k/2⌉ quantum queries and O(nk) gates.Source: §3.2 · p. 13, Figure 1 · p. 13

3.3 Gram-Schmidt Orthogonalization

• When unit vectors have pairwise inner products at most ε and t ≤ 0.1/ε, Gram–Schmidt orthogonalization keeps the resulting vectors close to the originals.In particular, the stated bounds are |⟨v_i|w_j⟩| ≤ 1.2ε and β_i ≤ 1 + 0.2ε.Source: §3.3 · p. 15

3.4 Gaussian Azuma’s Inequality

• The Gaussian Azuma inequality extends Azuma’s martingale concentration bound to differences dominated by Gaussian tails.The paper cites Shamir’s generalization for this purpose.Source: §3.4 · p. 16

4 Maximal Quantum/Classical Query Complexity Gap

• The classical lower-bound argument upgrades Forrelation’s previous Ω(N^1/4) lower bound to eΩ(sqrt(N)/log N).It proceeds through Real Forrelation, a continuous Gaussian relaxation whose task is to detect correlation between two functions.Source: §4 · p. 17

4.1 Discrete Versus Continuous

• Rounding forrelated Gaussian functions to their signs gives Boolean Forrelation with expected value 2/π, and any T-query Boolean algorithm yields an O(T)-query algorithm for Real Forrelation.The authors note that the exact value 2/π improves on Aaronson’s earlier constant for this reduction.Source: §4.1 · pp. 18, 20

4.2 Lower Bound for Real Forrelation

• For Gaussian Distinguishing, Theorem 11 gives a classical query lower bound when the test-vector set has bounded size and distinct vectors have small pairwise inner products.Real Forrelation uses M = 2N test vectors with pairwise inner products bounded by 1/√N; the theorem’s dependence on 1/ε is tight, while large M can limit the bound obtainable from coherence alone.Source: §4.2 · p. 21

4.3 Upper-Bounding |∆(D)|

• The analysis bounds the distinguishing statistic by replacing Gram-Schmidt-derived coefficients with simpler approximations on well-behaved data, which occurs with probability at least 0.99 over U.The proof can focus on data drawn from U because small statistic values with high probability under U imply the same under F.Source: §4.3 · pp. 23–25
• If |r_i| = O(1/t) for every i with high probability, the algorithm must make Ω(t) queries.Under this condition, the algorithm has not yet distinguished the forrelated distribution from the Gaussian null distribution with bias 1/2.Source: §4.3 · p. 27

4.4 Upper-Bounding |ri|

• Proposition 15 gives a crude bound on |r_i| that yields a Gaussian Distinguishing lower bound independent of the number of test vectors M.The passage states that this bound has no dependence on M, but its displayed quantitative expression is incomplete.Source: §4.4 · p. 27
• For Real Forrelation with M = 2N, the refined bound on |r_i| yields the desired query lower bound.The supplied passage omits the bound's exponent and logarithmic factors, so they are not specified here.Source: §4.4 · pp. 27–28
• Section 4.4 sharpens the high-probability bound on each |r_i| by repeatedly applying a lemma.The proof uses a martingale difference sequence and a union bound over test vectors and query indices.Source: §4.4 · pp. 27–28

5 Simulation of t-Query Quantum Algorithms

• Any t-query quantum algorithm with t = O(1) has its acceptance probability on every input estimable by a nonadaptive randomized algorithm using O(N^{1−1/2t}) queries.The result yields a nearly tight separation for one-query algorithms and rules out a partial Boolean function with constant quantum query complexity and linear randomized query complexity, resolving an open problem of Buhrman et al..Source: §5 · p. 29
• A bounded degree-k block-multilinear polynomial can be estimated with O(N^{1−1/k}) variable queries; the query bound’s big-O constant is exponential in k.The authors conjecture block-multilinearity can be removed and prove that conjecture for k = 2.Source: §5 · p. 29
• Block-multilinear approximate degree is a lower bound on quantum query complexity at least as strong as ordinary approximate degree, but its possible asymptotic separations remain unknown.The section also reports no known technique for upper-bounding block-multilinear approximate degree without also upper-bounding quantum query complexity.Source: §5 · p. 31

5.1 Preprocessing the Polynomial

• Variable-splitting preprocesses the polynomial so that every nonempty block subset S has Λ_S ≤ ε²/N, introducing at most 2kN/ε² new variables.Splitting a variable into several variables preserves boundedness at Boolean inputs.Source: §5.1 · pp. 32, 34

5.2 The Estimator

• The estimator is unbiased, and its variance analysis yields ε-precision estimation using O(n^{1−1/k}) queries.The stated query bound follows because only sampled variables are needed to calculate the estimator.Source: §5.2 · p. 34

5.3 Warmup

• The warmup estimator is unbiased and has variance at most δ/n.Source: §5.3 · p. 35

5.4 Second Estimator

• For each S ⊆ [k], the proof applies inclusion-exclusion to pairs of k-tuples that agree on S but are not identical.Source: §5.4 · p. 36
• Adding identical pairs can only increase the sum, and grouping terms by shared indices lets the proof bound the sum of squares by δ using (5).Source: §5.4 · p. 37
• The proof combines Lemma 23 with (7) to obtain the stated bound.Source: §5.4 · p. 37

6 BQP-Completeness

• For k = poly(n), explicit k-fold Forrelation is PromiseBQP-complete, and the reduction uses functions whose exponents are degree-3 polynomials.The hardness proof reduces a complete quantum simulation problem to Forrelation.Source: §6 · pp. 37, 38, 40
• The reduction maps a circuit Q to Boolean functions f1, . . . , fk with Φf1,...,fk = AQ, encoding CCSIGN gates with diagonal functions and Hadamards with Forrelation’s kernel.For a circuit with m Hadamard and CCSIGN gates, the construction uses k = O(m) functions of the stated simple forms.Source: §6 · pp. 38–39
• A selective-Hadamard gadget cancels unwanted Hadamards; its induced swaps are handled by tracking and exchanging qubit labels.The reduction extends the two-qubit gadget to arbitrary subsets by pairing qubits and adding a dummy qubit when needed.Source: §6 · pp. 38–39
• Restricting each function to at most two input bits places k-fold Forrelation in P, while the hardness construction permits up to three bits.The two-bit restriction yields stabilizer circuits, to which the Gottesman–Knill theorem applies.Source: §6 · pp. 38–40
• Depth-d circuits reduce to explicit (2d + 1)-fold Forrelation, with each output function given by a degree-3 polynomial.The construction combines functions across layers to remove intervening constant functions.Source: §6 · p. 40
• Explicit log n-fold Forrelation is complete for PromiseBQNC1, a class capturing log-depth quantum circuits and containing Factoring by Cleve and Watrous [13].The passage identifies PromiseBQNC1 with problems solvable by log-depth quantum circuits.Source: §6 · p. 40

7 Appendix: Separations for Sampling and Relation Problems

• One quantum query solves Fourier Sampling exactly, by applying Hadamards before and after the oracle query and measuring in the computational basis.The stated quantum algorithm uses ε = 0.Source: §7 · p. 41
• Ω(N/ log N) classical randomized queries are required for Fourier Sampling when ε = 0.01.Here N = 2^n is the size of the function’s truth table.Source: §7 · p. 41
• For t = o(N/ log N), the relevant conditional probabilities have ratio 1 + o(1), preventing a nonnegative linear combination from meeting both acceptance targets.This is the proof’s key comparison for the classical lower bound.Source: §7 · pp. 43–44
• The authors conjecture that Fourier Sampling has an O(N/ log N)-query randomized algorithm and propose corresponding bounds for approximate sampling with k quantum queries.For constant k, they conjecture O(N/(log N)^(1/k)) randomized queries and a tight k-fold generalization.Source: §7 · p. 44
• A relation variant solvable with one quantum query is conjectured to resist classical algorithms using o(N/ log N) queries, with success probability at most about the stated bound.For c = 1, the passage gives a 0.8 versus 0.317 success-probability gap; amplification would increase the quantum query count.Source: §7 · pp. 44–45

8 Appendix: Estimator for Arbitrary Bounded Quadratics

• For a bounded degree-k polynomial, the estimator’s variable-splitting approach seeks O(N) new variables while meeting two requirements; the second is proved here only for k = 2.Requirement (i) is tied to the warmup estimator’s variance bound, and requirement (ii) to the real estimator.Source: §8 · p. 45

8.1 Fourier Basics

• For degree-k polynomials, total squared nonconstant Fourier coefficients equal k times the variance, and each variable’s influence is at most k times the variance.These Fourier identities are used to locate variables with large influence.Source: §8.1 · p. 46, §8.2 · p. 46

8.2 Requirement (i)

• When a bounded degree-k polynomial has variance at least C/N, some variable has influence at least 1/(Ck); splitting such variables reduces variance to O(1/N) in O(N) steps.The process halts once variance falls below C/N, and introduces at most O(N) new variables.Source: §8.2 · pp. 46–47

8.3 Requirement (ii)

• For bounded quadratics, the linear part can be estimated with O(1) queries, leaving the quadratic form for the splitting procedure.The quadratic procedure repeatedly splits a variable of maximum influence and reaches V[pj] < C log N/N after O(N/ log N) splits.Source: §8.3 · pp. 48, 50
• The quadratic splitting step relies on an influence bound: if V[P] is sufficiently large relative to log N/N, some variable has influence Ω(V[P]^2).The passage gives this as Lemma 33’s conclusion.Source: §8.3 · p. 49

9 Appendix: Lower Bound for k-fold Forrelation

• For every k ≥ 2, the appendix proves an eΩ(N) randomized-query lower bound for k-fold Forrelation.The authors note that strengthening the bound as k increases would be desirable, but requires additional work.Source: §9 · p. 50

9.1 Concentration Inequalities

• For uniformly random input functions, Lemmas 34 and 35 provide concentration results used in the lower-bound argument.The proof strategy reduces Gaussian Distinguishing to k-fold Forrelation and applies a general lower bound.Source: §9 · p. 50, §9.1 · p. 51

9.2 Continuous/Discrete Hybrid

• The continuous/discrete hybrid has a coefficient bound |cx| ≤ log N with probability 1 − o(1/N), and its bounded-error query complexity transfers to Boolean k-fold Forrelation with O(T) queries.The appendix also states reductions between the hybrid and Boolean versions.Source: §9.2 · pp. 53, 55

9.3 Lower Bound

• The lower bound for k-fold Real Forrelation is N/log^(7/2) N randomized queries and almost matches the two-fold case.The reduction gives the algorithm f1, . . . , fk−2 for free, then expresses the remaining task as Gaussian Distinguishing.Source: §9.3 · pp. 55–56

• The property-testing promise separates tuples with Φ ≤ 1/100 from tuples at Hamming distance at least ε·k2^n from every tuple satisfying that threshold.Source: §10 · p. 56
• If Φ is nonnegative, changing at most ε·2^n coordinates in each function can produce a tuple whose Φ is at most (1 − ε)^k times the original value.Source: §10 · p. 57
• The authors conjecture that the smoothing lemma also holds in the reverse direction, but state that they do not have a proof.Source: §10 · p. 58
• A uniformly random k-tuple is good with probability at least 1 − δ_k, where δ_k can be made arbitrarily small by increasing C_k.Source: §10 · p. 58
• For good tuples, the paper bounds how much Φ can change when each function is modified on at most an ε fraction of inputs.Source: §10 · pp. 58–59
• One quantum query distinguishes the promised property-testing cases with Θ(ε) bias, while for k > 2 the classical lower bound is Ω(log^(7/2) N) queries.Source: §10 · pp. 59–60