#BQP and the Polynomial Hierarchy

The Limits of Search

Because proving $BQP \not\subseteq PH$ in the real world would imply $P \neq NP$, researchers utilize oracles to show that there exist black-box settings where quantum computers possess powers that no classical hierarchy can replicate.

The primary mechanism for demonstrating this separation is the Boolean Hidden Shift problem, which involves two Boolean functions $f$ and $g$ that are identical up to a secret bitwise shift $s$. A quantum algorithm can solve this problem efficiently by querying the functions in superposition and applying a Hadamard transform to extract the shift through constructive interference of the phases.

Phase Interference vs. Quantification

Classically, however, distinguishing the shift from a random permutation requires an exponential number of queries, even for an algorithm that can utilize the power of the entire Polynomial Hierarchy. This is because the PH is built on local existential and universal quantification, which is ill-suited for detecting the global, parity-based structures that quantum Fourier transforms can identify with a single query. The "global" nature of the quantum state allows it to sense properties of the entire function space that are effectively invisible to any depth of classical nesting.

Beyond Non-Deterministic Search

The abstraction provided by this research suggests that the complexity-theoretic foundations of quantum computing are not tied to the classical notions of "searching" for a witness. Instead, it implies that quantum computers operate on a level of "Fourier-checking" or global state correlation that is fundamentally orthogonal to the Polynomial Hierarchy.

This result reinforces the idea that BQP and PH are likely incomparable, meaning there are problems in BQP not in PH, and potentially problems in NP that are not in BQP.

Theoretical Limits of Quantum Advantage

This distinction is crucial for the long-term goal of identifying "Quantum Supremacy" tasks, as it points toward problems involving Gaussian sampling and Fourier analysis as the most likely candidates for demonstrating a clear gap between quantum and classical capabilities.

By framing quantum computing as an operation on the coefficients of a state vector rather than a search through a discrete space, Aaronson established a rigorous boundary between the powers of quantum and classical computation. This work continues to inform the search for new quantum algorithms that leverage global structure rather than local search.