As quantum computers grow more capable, simulating them on conventional hardware becomes more challenging yet more attractive since this helps in design and verification. Some quantum algorithms and circuits are amenable to surprisingly efficient simulation, and this makes hard-to-simulate computations particularly valuable. For such circuits, we develop accurate massively-parallel simulation with dramatic speedups over earlier methods on 42- and 45-qubit circuits. We propose two ways to trade circuit fidelity for computational speedups, so as to match the error rate of any quantum computer. Using Google Cloud, we simulate approximate sampling from the output of a circuit with 7 × 8 qubits and depth 42 with fidelity 0.5% at an estimated cost of $35K.
Aaronson and Ambainis (Theory of Computing, 2014) conjectured that quantum query algorithms admit efficient almost-everywhere classical simulation: for any
T-query quantum algorithm, its acceptance probability can be approximated on a
(1−δ) fraction of inputs, up to
ε additive error, using
poly(T,1/ε,1/δ) classical queries. At a high level, the conjecture suggests that exponential quantum speedups are possible only on sufficiently structured inputs.
In this work, we make progress on this conjecture by proving it for quantum algorithms that make massively parallel quantum queries. In contrast, Yamakawa and Zhandry (Journal of the ACM, 2024) showed that quantum algorithms restricted to parallel queries can still achieve exponential speedups over classical algorithms for sampling problems. We establish our simulation theorem by proving the stronger statement that parallel-query quantum algorithms cannot distinguish the uniform distribution over oracles from oracles drawn from so-called "dense distributions". Our main technical contribution is a coupling theorem that relates the uniform distribution over oracles to oracles drawn from dense distributions.
We further extend this approach beyond the purely parallel setting. We prove simulation theorems for quantum algorithms with constant rounds of adaptivity, and for quantum algorithms with a bounded quantum-query prefix followed by a massively parallel quantum-query stage.