Fourier Spectrum of Noisy Quantum Algorithms
Abstract
Quantum computing promises exponential speedups for certain problems, yet fully universal quantum computers remain out of reach and near-term devices are inherently noisy. Motivated by this, we study noisy quantum algorithms and the landscape between BQP and BPP. We build on a powerful technique to differentiate quantum and classical algorithms called the level-ℓ Fourier growth (the sum of absolute values of Fourier coefficients of sets of size ℓ) and show that it can also be used to differentiate quantum algorithms based on the types of resources used. We show that noise acting on a quantum algorithm dampens its Fourier growth in ways intricately linked to the type of noise.
Fields of Study & Subjects
Quantum Computing Algorithms and Architecture
Publication details
- Journal / source
- Proceedings of the 58th Annual ACM Symposium on Theory of Computing
- Publisher
- ACM
- Pages
- 305–313
- Publication date
- 9 June 2026
- Language
- EN