Circuits

Abstract: While quantum computing can accomplish tasks that are classically intractable, the presence of noise may destroy this advantage in the absence of fault tolerance. In this work, we present a quasi-polynomial-time classical algorithm for simulating quantum circuits under local depolarization noise, thereby ruling out their quantum advantage in these settings. Our algorithm leverages a property called approximate Markov property to sequentially sample from the measurement outcome distribution of noisy circuits. We establish approximate Markov property in a broad range of circuits: (1) we prove that it holds for any circuit when the noise rate exceeds a constant threshold, and (2) we provide strong analytical and numerical evidence that it holds for random quantum circuits subject to any constant noise rate, including non-unital noises. These regimes include previously known classically simulable cases as well as new ones, such as shallow random circuits and random circuits under non-unital noise, where anticoncentration does not hold and prior algorithms fail. Taken together, our results significantly extend the boundary of classical simulability and suggest that noise generically enforces approximate Markov property and classical simulability, thereby highlighting the limitation of noisy quantum circuits in demonstrating quantum advantage.

Abstract: Quantum access to arbitrary classical data encoded in unitary black-box oracles underlies interesting data-intensive quantum algorithms, such as machine learning or electronic structure simulation. The feasibility of these applications depends crucially on gate-efficient implementations of these oracles, which are commonly some reversible versions of the boolean circuit for a classical lookup table. We present a general parameterized architecture for quantum circuits implementing a lookup table that encompasses all prior work in realizing a continuum of optimal tradeoffs between qubits, non-Clifford gates, and error resilience, up to logarithmic factors. Our architecture assumes only local 2D connectivity, yet recovers results, with the appropriate parameters, poly-logarithmic error scaling. We also identify novel regimes, such as simultaneous sublinear scaling in all parameters. These results enable tailoring implementations of the commonly used lookup table primitive to any given quantum device with constrained resources.