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

arXiv:quant-ph/0209060

Quantum Lower Bound for Recursive Fourier Sampling

Scott Aaronson

Published Sep 9, 2002• 5 citations
arXivHTMLPDF

Abstract

One of the earliest quantum algorithms was discovered by Bernstein and Vazirani, for a problem called Recursive Fourier Sampling. This paper shows that the Bernstein-Vazirani algorithm is not far from optimal. The moral is that the need to "uncompute" garbage can impose a fundamental limit on efficient quantum computation. The proof introduces a new parameter of Boolean functions called the "nonparity coefficient," which might be of independent interest.

DOI
10.48550/arxiv.quant-ph/0209060

Related papers

Quantum lower bound for recursive Fourier sampling

Scott Aaronson

We revisit the oft-neglected `recursive Fourier sampling' (RFS) problem, introduced by Bernstein and Vazirani to prove an oracle separation between BPP and BQP. We show that the known quantum algorithm for RFS is essentially optimal, despite its seemingly wasteful need to uncompute information. This implies that, to place \mathsf{BQP} outside of PH[\log] relative to an oracle, one would need to go outside the RFS framework. Our proof argues that, given any variant of RFS, either the adversary method of Ambainis yields a good quantum lower bound, or else there is an efficient classical algorithm. This technique may be of independent interest.

Quantum Information and Computation•Mar 1, 2003•32 citations

Quantum lower bound for recursive Fourier sampling

AaronsonScott

We revisit the oft-neglected 'recursive Fourier sampling' (RFS) problem, introduced by Bernstein and Vazirani to prove an oracle separation between BPP and BQP. We show that the known quantum algor...

Quantum Information and Computation•Mar 1, 2003•1 citation

Phase Coordinate Uncomputation in Quantum Recursive Fourier Sampling

Christoffer Hindlycke, Niklas Johansson, Jan-Åke Larsson

Recursive Fourier Sampling (RFS) was one of the earliest problems to demonstrate a quantum advantage, and is known to lie outside the Merlin-Arthur complexity class. This work contains a new description of quantum algorithms in phase space terminology, demonstrating its use in RFS, and how and why this gives a better understanding of the quantum advantage in RFS. Most importantly, describing the computational process of quantum computation in phase space terminology gives a much better understanding of why uncomputation is necessary when solving RFS: the advantage is present only when phase coordinate garbage is uncomputed. This is the underlying reason for the limitations of the quantum advantage.

arXiv:2408.15938•Entropy•Jun 2, 2025•1 citation

Nearly Optimal Quantum Sample Complexity of Learning Fourier-Sparse Boolean Functions

Zekun Ye

We study the number of uniform quantum examples needed to exactly learn a Boolean function with at most $k$ nonzero Fourier coefficients. We give a learner with near-optimal $\widetilde{O}(k)$ sample complexity independent of the input length $n$. The learner uses only separate measurements of individual examples. This improves the previous $O(k^{3/2}\log^2 k)$ upper bound (Arunachalam, Chakraborty, Lee, Paraashar, and de Wolf, 2021). The main ingredient is a candidate set formed by symmetric differences of subsets from independent groups of Fourier samples. A multilinear majority polynomial combines unbiased random approximations into an accurate witness whose Fourier support lies in this set. Granularity then forces the set to contain the entire Fourier support, including subsets never directly sampled. For comparison, we derive the tight classical sample complexity $Θ(nk)$ by combining known sparse-recovery and lower-bound results.

quant-pharXiv:2610.17648•Oct 14, 2026•0 citations

Quantum Resources and Performance in the Initialization-Free Bernstein-Vazirani Algorithm

Haesol Han, Alexander Streltsov, Soojoon Lee

Naseri et al. [Phys. Rev. A 106, 062429 (2022); arXiv:2205.13610] studied which quantum resources in initial states are essential for the probabilistic Bernstein-Vazirani (BV) algorithm, defining its performance as the optimal average success probability over all measurements. In this work, we consider a variant of BV algorithm, which is called the initialization-free (IF) BV algorithm, in which an arbitrary ancilla state as the oracle register is allowed, to improve the performance. We derive an explicit formula for the performance of the probabilistic IF-BV algorithm and obtain a necessary and sufficient condition for an initial state to achieve maximal performance. We further prove that, under a suitable ordering assumption on the coefficients of the initial state, the probabilistic IF-BV algorithm outperforms the standard probabilistic BV algorithm.

quant-pharXiv:2607.06033•Jul 8, 2026•0 citations

Upper and lower bounds for recursive fourier sampling

Leo A. Harrington, Benjamin Johnson

We define a canonical version of the recursive Fourier sampling problem from quantum complexity theory, and systematically address a variety of its computational properties, including quantum query complexity, classical randomized query complexity, polynomial degree, and circuit size. Our analysis yields improvements for several of the known upper and lower bounds with regard to these complexity measures. For quantum query complexity, we define an explicit reduced-query quantum algorithm for the problem, and recursively construct a quantum circuit that implements the algorithm. For classical query complexity, we give new proofs of the known lower bounds that improve the constants, and we give complete proofs of the complexity class separations relative to oracles, that follow from these bounds. For polynomial degree, we construct an exactly representing real polynomial of extremely low degree, and extend it to representations over other Fields. We show that this degree is exactly optimal, even for a 2 weakly-representing polynomial. For circuit size, we construct a small depth-two circuit for the non-recursive version of the problem, and we show that the size is optimal even if the depth is not restricted. We also prove asymptotically matching upper and lower bounds on circuit size for the full recursive version of the problem when the depth is restricted to two. To prove the tight results for polynomial degree and circuit size we introduce and define a general notion of reduction for both polynomials and circuits that represent boolean functions on a partial domain. We also introduce and define, separately, a new measure of circuit complexity called effort.

•Jan 1, 2008•6 citations
One of the earliest quantum algorithms was discovered by Bernstein and Vazirani, for a problem called Recursive Fourier Sampling. This paper shows that the Bernstein-Vazirani algorithm is not far from optimal. The moral is that the need to "uncompute" garbage can impose a fundamental limit on efficient quantum computation. The proof introduces a new parameter of Boolean functions called the "nonparity coefficient," which might be of independent interest.
We revisit the oft-neglected `recursive Fourier sampling' (RFS) problem, introduced by Bernstein and Vazirani to prove an oracle separation between BPP and BQP. We show that the known quantum algorithm for RFS is essentially optimal, despite its seemingly wasteful need to uncompute information. This implies that, to place \mathsf{BQP} outside of PH[\log] relative to an oracle, one would need to go outside the RFS framework. Our proof argues that, given any variant of RFS, either the adversary method of Ambainis yields a good quantum lower bound, or else there is an efficient classical algorithm. This technique may be of independent interest.
Recursive Fourier Sampling (RFS) was one of the earliest problems to demonstrate a quantum advantage, and is known to lie outside the Merlin-Arthur complexity class. This work contains a new description of quantum algorithms in phase space terminology, demonstrating its use in RFS, and how and why this gives a better understanding of the quantum advantage in RFS. Most importantly, describing the computational process of quantum computation in phase space terminology gives a much better understanding of why uncomputation is necessary when solving RFS: the advantage is present only when phase coordinate garbage is uncomputed. This is the underlying reason for the limitations of the quantum advantage.
We study the number of uniform quantum examples needed to exactly learn a Boolean function with at most kkk nonzero Fourier coefficients. We give a learner with near-optimal O~(k)\widetilde{O}(k)O(k) sample complexity independent of the input length nnn. The learner uses only separate measurements of individual examples. This improves the previous O(k3/2log⁡2k)O(k^{3/2}\log^2 k)O(k3/2log2k) upper bound (Arunachalam, Chakraborty, Lee, Paraashar, and de Wolf, 2021). The main ingredient is a candidate set formed by symmetric differences of subsets from independent groups of Fourier samples. A multilinear majority polynomial combines unbiased random approximations into an accurate witness whose Fourier support lies in this set. Granularity then forces the set to contain the entire Fourier support, including subsets never directly sampled. For comparison, we derive the tight classical sample complexity Θ(nk)Θ(nk)Θ(nk) by combining known sparse-recovery and lower-bound results.
Naseri et al. [Phys. Rev. A 106, 062429 (2022); arXiv:2205.13610] studied which quantum resources in initial states are essential for the probabilistic Bernstein-Vazirani (BV) algorithm, defining its performance as the optimal average success probability over all measurements. In this work, we consider a variant of BV algorithm, which is called the initialization-free (IF) BV algorithm, in which an arbitrary ancilla state as the oracle register is allowed, to improve the performance. We derive an explicit formula for the performance of the probabilistic IF-BV algorithm and obtain a necessary and sufficient condition for an initial state to achieve maximal performance. We further prove that, under a suitable ordering assumption on the coefficients of the initial state, the probabilistic IF-BV algorithm outperforms the standard probabilistic BV algorithm.
We define a canonical version of the recursive Fourier sampling problem from quantum complexity theory, and systematically address a variety of its computational properties, including quantum query complexity, classical randomized query complexity, polynomial degree, and circuit size. Our analysis yields improvements for several of the known upper and lower bounds with regard to these complexity measures. For quantum query complexity, we define an explicit reduced-query quantum algorithm for the problem, and recursively construct a quantum circuit that implements the algorithm. For classical query complexity, we give new proofs of the known lower bounds that improve the constants, and we give complete proofs of the complexity class separations relative to oracles, that follow from these bounds. For polynomial degree, we construct an exactly representing real polynomial of extremely low degree, and extend it to representations over other Fields. We show that this degree is exactly optimal, even for a 2 weakly-representing polynomial. For circuit size, we construct a small depth-two circuit for the non-recursive version of the problem, and we show that the size is optimal even if the depth is not restricted. We also prove asymptotically matching upper and lower bounds on circuit size for the full recursive version of the problem when the depth is restricted to two. To prove the tight results for polynomial degree and circuit size we introduce and define a general notion of reduction for both polynomials and circuits that represent boolean functions on a partial domain. We also introduce and define, separately, a new measure of circuit complexity called effort.