Abstract
This work investigates the oracle separation between the physically motivated complexity class of noisy quantum circuits, inspired by definitions such as those presented by Chen, Cotler, Huang, and Li (2022). We establish that with a constant error rate, separation can be achieved in terms of NP. When the error rate is $\Omega(\log n/n)$, we can extend this result to the separation of PH. Notably, our oracles, in all separations, do not necessitate error correction schemes or fault tolerance, as all quantum circuits are of constant depth. This indicates that even quantum computers with minor errors, without error correction, may surpass classical complexity classes under various scenarios and assumptions. We also explore various common noise settings and present new classical hardness results, generalizing those found in studies by Raz and Tal (2022) and Bassirian, Bouland, Fefferman, Gunn, and Tal (2021), which are of independent interest.
Introduction
In the current era of quantum computing, often referred to as the Noisy Intermediate-Scale Quantum (NISQ) era, researchers face a significant gap between theoretical ideals and hardware reality. While theoretical computer science suggests that quantum computers ($BQP$) possess capabilities far exceeding classical ones, physical qubits are notoriously fragile. Traditional paths to quantum advantage rely on fault-tolerant error correction, which requires a massive overhead in qubits—a luxury current technology does not yet afford.
This paper addresses a fundamental question: Does a noisy quantum computer, operating without the safety net of error correction, still possess a provable advantage over classical complexity classes? By bridging the gap between NISQ limitations and rigorous complexity theory, the authors demonstrate that quantum advantage persists even in the presence of significant depolarizing noise, provided the circuits remain "shallow."
Defining Noisy Quantum Complexity
To analyze this problem, the authors define a new complexity class, $BQP_\lambda$. This class represents the set of problems solvable by a classical computer that has access to the output of a noisy quantum device. The noise model employed is "local depolarizing noise," where every gate, initialization, and measurement has a probability $\lambda$ of failing and resulting in a completely random state.
The core of the paper's argument rests on the use of constant-depth circuits. Because these circuits have a fixed, low depth regardless of the input size $n$, noise has limited opportunity to accumulate. This allows the "quantumness"—the essential superposition and interference—to survive long enough to be measured and provide a computational signal that classical machines cannot easily replicate.
Oracle Separations: $BQP_\lambda$ vs. $NP$
The authors establish the power of noisy quantum computing through "oracle separations." These are mathematical proofs showing that if both a quantum and a classical computer are given access to a specific "black-box" function (an oracle), the quantum computer can solve certain problems that the classical one cannot.
To separate $BQP_\lambda$ from $NP$, the authors utilize the Deutsch-Jozsa algorithm. They prove that even under a constant noise rate $\lambda > 0$, a quantum computer can distinguish between "constant" and "balanced" functions using $O(n^2 \log n)$ queries. In contrast, a classical $NP$ machine would require significantly more resources to achieve the same result.
As shown in Figure 1, the circuit utilizes a standard oracle $O_f$ flanked by Hadamard transforms ($H^n$). The constant depth of this arrangement is key; it ensures that the noise does not completely wash out the interference pattern required to identify the function's properties.
Extending the Separation to the Polynomial Hierarchy
Moving beyond $NP$, the authors investigate the entire Polynomial Hierarchy ($PH$). They employ a variation of the "Forrelation" problem—specifically "Squared Forrelation"—to determine if two functions are highly correlated in the Fourier domain.
Their findings reveal a specific threshold for noise scaling. While a constant error rate suffices for separation from $NP$, separating quantum power from $PH$ requires the error rate to scale slightly with the input size, specifically $\lambda(n) = \Omega(\log n / n)$. This result suggests that as the complexity of the classical class increases, the tolerance for quantum noise decreases, though it still remains within a regime that does not strictly require full fault tolerance.
Key Insights and Theoretical Limits
Several significant insights emerge from this work:
- The Power of Shallowness: Error correction is not a binary requirement for quantum advantage. Shallow circuits allow quantum interference to persist in noisy environments.
- Quantum vs. Classical Randomness: The paper reinforces that the inherent randomness in quantum measurement is fundamentally different from classical probabilistic randomness ($BPP$). Even when noisy, this quantum randomness can be leveraged for computational gains.
- The Constant Noise Gap: The authors provide a "no-go" theorem suggesting that with their current mathematical framework, it may be impossible to prove a separation from $PH$ if the noise rate is a fixed constant, regardless of input size. This remains an open challenge for the field.
Conclusion
This research provides a robust theoretical foundation for the potential of NISQ devices. By proving that noisy, constant-depth quantum circuits can outperform classical $NP$ and $PH$ classes relative to an oracle, the authors show that the path to quantum advantage may not strictly require the daunting overhead of full error correction. Future work will likely focus on "unrelativized" separations—proving these results without the use of oracles—and exploring models that allow for limited, noisy intermediate measurements.
Summary updated