Fault-tolerant quantum speedup from constant depth quantum circuits

Abstract

A defining feature in the field of quantum computing is the potential of a quantum device to outperform its classical counterpart for a specific computational task. By now, several proposals exist showing that certain sampling problems can be done efficiently quantumly, but are not possible efficiently classically, assuming strongly held conjectures in complexity theory. A feature dubbed quantum speedup. However, the effect of noise on these proposals is not well understood in general, and in certain cases it is known that simple noise can destroy the quantum speedup. Here we develop a fault-tolerant version of one family of these sampling problems, which we show can be implemented using quantum circuits of constant depth. We present two constructions, each taking $poly(n)$ physical qubits, some of which are prepared in noisy magic states. The first of our constructions is a constant depth quantum circuit composed of single and two-qubit nearest neighbour Clifford gates in four dimensions. This circuit has one layer of interaction with a classical computer before final measurements. Our second construction is a constant depth quantum circuit with single and two-qubit nearest neighbour Clifford gates in three dimensions, but with two layers of interaction with a classical computer before the final measurements. For each of these constructions, we show that there is no classical algorithm which can sample according to its output distribution in $poly(n)$ time, assuming two standard complexity theoretic conjectures hold. The noise model we assume is the so-called local stochastic quantum noise. Along the way, we introduce various new concepts such as constant depth magic state distillation (MSD), and constant depth output routing, which arise naturally in measurement based quantum computation (MBQC), but have no constant-depth analogue in the circuit model.

26 pages, 6 figures, comments are welcome, new references added

References in corpus (49)

• Quantum Computing in the NISQ era and beyond
• Fault-tolerant quantum computation by anyons
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum Machine Learning
• Topological quantum memory
• Measurement-based quantum computation with cluster states
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Black holes as mirrors: quantum information in random subsystems
• Characterizing Quantum Supremacy in Near-Term Devices
• Quantum algorithms: an overview
• Quantum Computational Supremacy
• Exact and Approximate Unitary 2-Designs: Constructions and Applications
• Topological fault-tolerance in cluster state quantum computation
• A blueprint for demonstrating quantum supremacy with superconducting qubits
• Quantum advantage with shallow circuits
• A fault-tolerant one-way quantum computer
• Quantum computing with nearest neighbor interactions and error rates over 1%
• Magic state distillation with low overhead
• Randomizing quantum states: Constructions and applications
• Local random quantum circuits are approximate polynomial-designs
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Average-case complexity versus approximate simulation of commuting quantum computations
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Random Quantum Circuits and Pseudo-Random Operators: Theory and Applications
• Ultrahigh Error Threshold for Surface Codes with Biased Noise
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Quantum advantage with noisy shallow circuits in 3D
• Improved magic states distillation for quantum universality
• Generalized Flow and Determinism in Measurement-based Quantum Computation
• Multilevel distillation of magic states for quantum computing
• Architectures for quantum simulation showing a quantum speedup
• Thermalization and canonical typicality in translation-invariant quantum lattice systems
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• A magic state's fidelity can be superior to the operations that created it
• Classical simulation of photonic linear optics with lost particles
• Fault-tolerant magic state preparation with flag qubits
• Codes and Protocols for Distilling $T$, controlled-$S$, and Toffoli Gates
• Magic State Distillation with Low Space Overhead and Optimal Asymptotic Input Count
• Distillation with sublogarithmic overhead
• Resource-efficient verification of quantum computing using Serfling's bound
• Anticoncentration theorems for schemes showing a quantum speedup
• Proof of finite surface code threshold for matching
• Quantum Commuting Circuits and Complexity of Ising Partition Functions
• Transversal Clifford gates on folded surface codes
• Noise in BosonSampling and the threshold of efficient classical simulatability
• Efficient quantum pseudorandomness with simple graph states
• Derandomizing quantum circuits with measurement based unitary designs
• Nonadaptive fault-tolerant verification of quantum supremacy with noise
• Testing randomness with photons

Cited by in corpus (6)

• Logical quantum processor based on reconfigurable atom arrays
• Computational advantage of quantum random sampling
• Quantum computational advantage with constant-temperature Gibbs sampling
• Robust sparse IQP sampling in constant depth
• Fault-tolerant compiling of classically hard IQP circuits on hypercubes
• Unconditionally separating noisy ${\mathsf{QNC}}^0$ from bounded polynomial threshold circuits of constant depth