The Acrobatics of BQP

Scott Aaronson, DeVon Ingram, William Kretschmer

Introduction

In the landscape of computational complexity, the relationship between quantum and classical power is often viewed through the lens of the Polynomial Hierarchy (PH). While we understand how classical randomness (BPP) interacts with these levels—often collapsing into them—the "quantumness" of BQP (Bounded-error Quantum Polynomial time) behaves quite differently. This paper explores the "acrobatics" of BQP, proving that quantum computation can be decoupled from classical hierarchies in ways that defy standard intuition.

The Challenge of "Quantumness"

A cornerstone of classical complexity is the ability to "pull out" randomness. In a randomized algorithm (BPP), one can treat the random bits as a fixed auxiliary input, leading to results like Adleman’s Theorem ($BPP \subset P/poly$). Quantum mechanics, however, forbids such a simplification. Because quantum amplitudes involve interference patterns rather than simple probability distributions, there is no known way to "fix" the quantum state without destroying the very properties that give quantum computers their edge.

This leads to a fundamental question: Is the power of BQP inherently tied to the power of classical classes like NP? If we lived in a world where $P = NP$, would quantum computers lose their unique advantage? Before this work, many questions regarding how BQP interacts with the various levels of the Polynomial Hierarchy remained open, even in the oracle (black-box) setting.

Methodological Breakthroughs

To address these questions, the authors developed a suite of "quantum-aware" mathematical tools designed to analyze the limits of quantum query algorithms:

  • Quantum-Aware Random Restrictions: This method analyzes quantum algorithms by randomly fixing a large portion of the input bits. The authors demonstrate that under these restrictions, a quantum algorithm's behavior simplifies and can be approximated by relatively simple classical structures, such as small decision trees.
  • Block Sensitivity Concentration: The authors proved a new theorem regarding $AC^0$ circuits—the class of circuits that define the PH. They showed these circuits are "insensitive" to specific input patterns, meaning they cannot "see" the Fourier-related structures (such as the Forrelation problem) that quantum algorithms exploit.
  • Sparse Oracle Simulation: By proving a version of the Aaronson-Ambainis Conjecture for "sparse" oracles, the authors showed that on specific, mostly-empty inputs, classical algorithms can occasionally match quantum performance, providing a boundary for quantum advantage.

Key Insights: Decoupling the Hierarchy

The core finding of this work is that quantumness is fundamentally distinct from classical randomness. This is best illustrated by the "order of operations" in complexity classes. In classical computing, $NP^{BPP}$ is essentially the same as $BPP^{NP}$ (both are contained within the class AM). However, the authors show that in the quantum realm, $NP^{BQP} \not\subset BQP^{PH}$ relative to an oracle. This means that combining a nondeterministic machine with a quantum one yields different results depending on which has "top-level" control.

Furthermore, the paper demonstrates that the classical "P vs. NP" question is entirely uncoupled from quantum advantages. They construct an oracle world where $P = NP$, yet quantum computers still maintain a massive advantage over classical verifiers (the difference between BQP and QCMA).

Major Results and Oracle Separations

The paper provides several landmark oracle separations that clarify the boundaries of BQP:

  • Resolving Fortnow’s Problem: It resolves a 2005 open problem by Lance Fortnow, proving the existence of an oracle where $NP^{BQP} \not\subset BQP^{PH}$.
  • The QMA Hierarchy: It proves that the class PP (associated with counting) is not contained in the "QMA hierarchy" (the quantum analogue of the PH) relative to a random oracle.
  • BQP Power vs. PH Stability: The authors constructed an oracle where BQP is as powerful as $P^{\#P}$, yet the classical Polynomial Hierarchy remains infinite, refusing to collapse into a simpler level.
  • Bridging the Gap: They showed that quantum computers cannot "bridge" the gaps between classical levels; specifically, $\Sigma^P_{k+1} \not\subset BQP^{\Sigma^P_k}$ relative to a random oracle.

Conclusion and Future Directions

While these results are relativized (holding in the presence of an oracle), they provide a rigorous proof that current classical techniques are insufficient to bound the power of quantum computers. The "acrobatics" of BQP allow it to leap over classical barriers that trap randomized algorithms.

Future research aims to push these separations even further. The authors conjecture the existence of an oracle where $NP \subseteq BQP$ but $PH \not\subset BQP$. Such a result would be the ultimate demonstration of BQP's ability to selectively "swallow" certain classical classes while remaining distinct from the broader hierarchy.

Summary updated

BibTeX
@inproceedings{aaronson2022acrobatics,
  author = {Scott Aaronson and DeVon Ingram and William Kretschmer},
  title = {{The Acrobatics of BQP}},
  booktitle = {CCC},
  year = {2022},
  doi = {10.4230/lipics.ccc.2022.20},
}
Figure