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:2408.15938 · Entropy

Phase Coordinate Uncomputation in Quantum Recursive Fourier Sampling

Christoffer Hindlycke, Niklas Johansson, Jan-Åke Larsson

Published Jun 2, 2025• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.3390/e27060596

Related papers

Quantum Lower Bound for Recursive Fourier Sampling

Scott Aaronson

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.

arXiv:quant-ph/0209060•Sep 9, 2002•5 citations

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

Understanding the Speedup of Quantum Computation

Christoffer Hindlycke

A quantum computer applies the axioms of quantum mechanics to efficiently run quantum algorithms, thereby performing calculations which, we speculate, would demand exponential time or memory on a classical computer. This thesis focuses on deriving better explanations of, and in the process improving upon, quantum algorithms and models of (a sub-theory of) the quantum mechanical foundations that dictate how quantum computers operate. Our contributions consist of three parts. First, we construct an efficient Einstein-Podolsky-Rosen(EPR)-complete hidden-variable model of the sub-theory of quantum mechanics given by the stabilizer formalism. Being EPR-complete means every element of physical reality is contained in the model. Next, we create a single-qubit rotation algorithm using the universal Toffoli gate. Our circuit requires only a logarithmic gate depth (and so a loga-rithmic number of Toffolis), substantially improving on previous algorithms. The circuit admits an efficient construction, that uses a comparison with a constant obtained through a trigonometric expression, and so the gate array can be constructed in polynomial time. We perform quantum state and process tomography on our algorithm when run on both a simulated and a real quantum computer, and analyze the results, attaining good estimates of our algorithm’s performance under various (both simulated and real) noise levels. Finally, we study Recursive Fourier Sampling (RFS): The quantum algorithm solving RFS is one of the first such appearing to give an advantage over any classical algorithm. By reformulating RFS in terms of which information its oracles write into the phase of the qubits, we show that the quantum algorithm solving RFS relies on the quantum computational resource of phase kickback, strengthening similar arguments made in related work. We show that this algorithm cannot be improved as the calculations carried out by the oracles must be uncomputed, lest random information gets written into the phase.

Linköping studies in science and technology. Dissertations•Nov 12, 2024•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

The Power of Quantum Fourier Sampling

Bill Fefferman, Christopher Umans

How powerful are Quantum Computers? Despite the prevailing belief that Quantum Computers are more powerful than their classical counterparts, this remains a conjecture backed by little formal evidence. Shor's famous factoring algorithm [Shor97] gives an example of a problem that can be solved efficiently on a quantum computer with no known efficient classical algorithm. Factoring, however, is unlikely to be NP-Hard, meaning that few unexpected formal consequences would arise, should such a classical algorithm be discovered. Could it then be the case that any quantum algorithm can be simulated efficiently classically? Likewise, could it be the case that Quantum Computers can quickly solve problems much harder than factoring? If so, where does this power come from, and what classical computational resources do we need to solve the hardest problems for which there exist efficient quantum algorithms? We make progress toward understanding these questions through studying the relationship between classical nondeterminism and quantum computing. In particular, is there a problem that can be solved efficiently on a Quantum Computer that cannot be efficiently solved using nondeterminism? In this thesis we address this problem from the perspective of sampling problems. Namely, we give evidence that approximately sampling the Quantum Fourier Transform of an efficiently computable function, while easy quantumly, is hard for any classical machine in the Polynomial Time Hierarchy. In particular, we prove the existence of a class of distributions that can be sampled efficiently by a Quantum Computer, that likely cannot be approximately sampled in randomized polynomial time with an oracle for the Polynomial Time Hierarchy. Our work complements and generalizes the evidence given in Aaronson and Arkhipov's work [AA2013] where a different distribution with the same computational properties was given. Our result is more general than theirs, but requires a more powerful quantum sampler.

Conference on Theory of Quantum Computation, Communication and Cryptography•Jan 1, 2016•7 citations
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 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.
A quantum computer applies the axioms of quantum mechanics to efficiently run quantum algorithms, thereby performing calculations which, we speculate, would demand exponential time or memory on a classical computer. This thesis focuses on deriving better explanations of, and in the process improving upon, quantum algorithms and models of (a sub-theory of) the quantum mechanical foundations that dictate how quantum computers operate. Our contributions consist of three parts. First, we construct an efficient Einstein-Podolsky-Rosen(EPR)-complete hidden-variable model of the sub-theory of quantum mechanics given by the stabilizer formalism. Being EPR-complete means every element of physical reality is contained in the model. Next, we create a single-qubit rotation algorithm using the universal Toffoli gate. Our circuit requires only a logarithmic gate depth (and so a loga-rithmic number of Toffolis), substantially improving on previous algorithms. The circuit admits an efficient construction, that uses a comparison with a constant obtained through a trigonometric expression, and so the gate array can be constructed in polynomial time. We perform quantum state and process tomography on our algorithm when run on both a simulated and a real quantum computer, and analyze the results, attaining good estimates of our algorithm’s performance under various (both simulated and real) noise levels. Finally, we study Recursive Fourier Sampling (RFS): The quantum algorithm solving RFS is one of the first such appearing to give an advantage over any classical algorithm. By reformulating RFS in terms of which information its oracles write into the phase of the qubits, we show that the quantum algorithm solving RFS relies on the quantum computational resource of phase kickback, strengthening similar arguments made in related work. We show that this algorithm cannot be improved as the calculations carried out by the oracles must be uncomputed, lest random information gets written into the phase.
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.
How powerful are Quantum Computers? Despite the prevailing belief that Quantum Computers are more powerful than their classical counterparts, this remains a conjecture backed by little formal evidence. Shor's famous factoring algorithm [Shor97] gives an example of a problem that can be solved efficiently on a quantum computer with no known efficient classical algorithm. Factoring, however, is unlikely to be NP-Hard, meaning that few unexpected formal consequences would arise, should such a classical algorithm be discovered. Could it then be the case that any quantum algorithm can be simulated efficiently classically? Likewise, could it be the case that Quantum Computers can quickly solve problems much harder than factoring? If so, where does this power come from, and what classical computational resources do we need to solve the hardest problems for which there exist efficient quantum algorithms? We make progress toward understanding these questions through studying the relationship between classical nondeterminism and quantum computing. In particular, is there a problem that can be solved efficiently on a Quantum Computer that cannot be efficiently solved using nondeterminism? In this thesis we address this problem from the perspective of sampling problems. Namely, we give evidence that approximately sampling the Quantum Fourier Transform of an efficiently computable function, while easy quantumly, is hard for any classical machine in the Polynomial Time Hierarchy. In particular, we prove the existence of a class of distributions that can be sampled efficiently by a Quantum Computer, that likely cannot be approximately sampled in randomized polynomial time with an oracle for the Polynomial Time Hierarchy. Our work complements and generalizes the evidence given in Aaronson and Arkhipov's work [AA2013] where a different distribution with the same computational properties was given. Our result is more general than theirs, but requires a more powerful quantum sampler.