Quantum advantage with noisy shallow circuits in 3D

Abstract

Prior work has shown that there exists a relation problem which can be solved with certainty by a constant-depth quantum circuit composed of geometrically local gates in two dimensions, but cannot be solved with high probability by any classical constant depth circuit composed of bounded fan-in gates. Here we provide two extensions of this result. Firstly, we show that a separation in computational power persists even when the constant-depth quantum circuit is restricted to geometrically local gates in one dimension. The corresponding quantum algorithm is the simplest we know of which achieves a quantum advantage of this type. It may also be more practical for future implementations. Our second, main result, is that a separation persists even if the shallow quantum circuit is corrupted by noise. We construct a relation problem which can be solved with near certainty using a noisy constant-depth quantum circuit composed of geometrically local gates in three dimensions, provided the noise rate is below a certain constant threshold value. On the other hand, the problem cannot be solved with high probability by a noise-free classical circuit of constant depth. A key component of the proof is a quantum error-correcting code which admits constant-depth logical Clifford gates and single-shot logical state preparation. We show that the surface code meets these criteria. To this end, we provide a protocol for single-shot logical state preparation in the surface code which may be of independent interest.

References in corpus (34)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Good Quantum Error-Correcting Codes Exist
• Quantum Teleportation is a Universal Computational Primitive
• Topological quantum memory
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Multiple Particle Interference and Quantum Error Correction
• Characterizing Quantum Supremacy in Near-Term Devices
• Fault-tolerant quantum computation with high threshold in two dimensions
• Lieb-Robinson bounds and the generation of correlations and topological quantum order
• High threshold universal quantum computation on the surface code
• Quantum advantage with shallow circuits
• A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
• Quantum codes on a lattice with boundary
• Average-case complexity versus approximate simulation of commuting quantum computations
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Long-range quantum entanglement in noisy cluster states
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Quantum Supremacy through the Quantum Approximate Optimization Algorithm
• Quantum computation with realistic magic state factories
• Single-shot fault-tolerant quantum error correction
• Efficient classical simulation of random shallow 2D quantum circuits
• Leveraging Secondary Storage to Simulate Deep 54-qubit Sycamore Circuits
• Constant overhead quantum fault-tolerance with quantum expander codes
• Architectures for quantum simulation showing a quantum speedup
• Simulation of low-depth quantum circuits as complex undirected graphical models
• Classical Simulation of Intermediate-Size Quantum Circuits
• Proof of finite surface code threshold for matching
• Local Hamiltonians Whose Ground States are Hard to Approximate
• Transversal Clifford gates on folded surface codes
• Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
• Quantum Supremacy Circuit Simulation on Sunway TaihuLight
• Average-Case Quantum Advantage with Shallow Circuits
• Quantum Circuit Depth Lower Bounds For Homological Codes

Cited by in corpus (84)

• Noisy intermediate-scale quantum (NISQ) algorithms
• Scalable mitigation of measurement errors on quantum computers
• Scalable error mitigation for noisy quantum circuits produces competitive expectation values
• Kochen-Specker Contextuality
• Computational advantage of quantum random sampling
• Exponential Error Suppression for Near-Term Quantum Devices
• Error mitigation for universal gates on encoded qubits
• Simulating the dynamics of braiding of Majorana zero modes using an IBM quantum computer
• Demonstration of algorithmic quantum speedup
• Determining the proton content with a quantum computer
• Quantum Neural Network Classifiers: A Tutorial
• Creation of Optical Cat and GKP States Using Shaped Free Electrons
• Quantum unary approach to option pricing
• Classically-Verifiable Quantum Advantage from a Computational Bell Test
• Variational Quantum Algorithm for Non-equilibrium Steady States
• Accelerated quantum Monte Carlo with mitigated error on noisy quantum computer
• Fault-tolerant qubit from a constant number of components
• Well-conditioned multi-product formulas for hardware-friendly Hamiltonian simulation
• Quantum advantage for computations with limited space
• Quantum Gaussian Process Regression for Bayesian Optimization
• Low-Overhead Transversal Fault Tolerance for Universal Quantum Computation
• Fast and reliable entanglement distribution with quantum repeaters: principles for improving protocols using reinforcement learning
• Epitaxial Superconductor-Semiconductor Two-Dimensional Systems for Superconducting Quantum Circuits
• Quantum supremacy and random circuits
• Looped Pipelines Enabling Effective 3D Qubit Lattices in a Strictly 2D Device
• Learning shallow quantum circuits
• Quantum computational advantage with string order parameters of 1D symmetry-protected topological order
• Logical Clifford Synthesis for Stabilizer Codes
• Conditionally rigorous mitigation of multiqubit measurement errors
• Quantum Latent Diffusion Models
• Towards Efficient Quantum Hybrid Diffusion Models
• Quantum computational advantage attested by nonlocal games with the cyclic cluster state
• Entanglement-induced provable and robust quantum learning advantages
• Cross-cap defects and fault-tolerant logical gates in the surface code and the honeycomb Floquet code
• Hierarchies of resources for measurement-based quantum computation
• Quantum computational advantage with constant-temperature Gibbs sampling
• Stabilizer Entanglement Distillation and Efficient Fault-Tolerant Encoders
• Parallel Quantum Algorithm for Hamiltonian Simulation
• Application of the Diamond Gate in Quantum Fourier Transformations and Quantum Machine Learning
• Concatenation Schemes for Topological Fault-tolerant Quantum Error Correction
• Robust sparse IQP sampling in constant depth
• Modeling Short-Range Microwave Networks to Scale Superconducting Quantum Computation
• Fault-tolerant quantum speedup from constant depth quantum circuits
• Parametrized constant-depth quantum neuron
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates
• Test of the physical significance of Bell nonlocality
• Demonstration of Algorithmic Quantum Speedup for an Abelian Hidden Subgroup Problem
• Fault-tolerant compiling of classically hard IQP circuits on hypercubes
• Forging quantum data: classically defeating an IQP-based quantum test
• Max-cut Clustering Utilizing Warm-Start QAOA and IBM Runtime
• Measurement-induced entanglement and complexity in random constant-depth 2D quantum circuits
• Fast simulation of planar Clifford circuits
• Device-independent and semi-device-independent entanglement certification in broadcast Bell scenarios
• Kernel-Function Based Quantum Algorithms for Finite Temperature Quantum Simulation
• The Golay codes and Quantum Contextuality
• Dynamics of single-mode nonclassicalities and quantum correlations in the Jaynes-Cummings model
• Unconditional quantum magic advantage in shallow circuit computation
• Possibilistic simulation of quantum circuits by classical circuits
• Single-shot preparation of hypergraph product codes via dimension jump
• Limitations of Noisy Quantum Devices in Computational and Entangling Power
• Utility of NISQ devices: optimizing experimental parameters for the fabrication of Au atomic junction using gate-based quantum computers
• Reachability in Controlled Markovian Quantum Systems: An Operator-Theoretic Approach
• Single-qubit gate teleportation provides a quantum advantage
• Characterizing high-dimensional quantum contextuality
• Quantum advantage in temporally flat measurement-based quantum computation
• Exploring the boundary of quantum correlations with a time-domain optical processor
• Policy Gradient Approach to Compilation of Variational Quantum Circuits
• Unconditionally separating noisy ${\mathsf{QNC}}^0$ from bounded polynomial threshold circuits of constant depth
• Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations
• Symmetry-enhanced Counterdiabatic Quantum Algorithm for Qudits
• Constructive nonlocal games with very small classical values
• Interactive quantum advantage with noisy, shallow Clifford circuits
• Compression of quantum shallow-circuit states
• Quantum Pattern Recognition in Photonic Circuits
• Consideration of the Need for Quantum Grid Computing
• Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms
• Quantum advantage through the magic pentagram problem
• Efficient classical simulation of cluster state quantum circuits with alternative inputs
• Special-Purpose Quantum Processor Design
• Self-Testing Graph States Permitting Bounded Classical Communication
• Speeding up Lindblad dynamics via time-rescaling engineering
• Robust and optimal loading of general classical data into quantum computers
• Quantum contextuality from measurement invasiveness
• Convexity of noncontextual wirings and how they order the set of correlations