Phase Coordinate Uncomputation in Quantum Recursive Fourier Sampling

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.

8 pages, 2 figures, v3: Close to published version

References in corpus (7)

• Improved Simulation of Stabilizer Circuits
• Quantum Algorithms Revisited
• A Theory of Fault-Tolerant Quantum Computation
• In defense of the epistemic view of quantum states: a toy theory
• Quantum advantage with shallow circuits
• Quantum Simulation Logic, Oracles, and the Quantum Advantage
• Efficient contextual ontological model of $n$-qubit stabilizer quantum mechanics

Cited by in corpus (1)

• Quantum mechanics based on real numbers: A consistent description