Quantum coding with low-depth random circuits

Abstract

Random quantum circuits have played a central role in establishing the computational advantages of near-term quantum computers over their conventional counterparts. Here, we use ensembles of low-depth random circuits with local connectivity in $D\ge 1$ spatial dimensions to generate quantum error-correcting codes. For random stabilizer codes and the erasure channel, we find strong evidence that a depth $O(\log N)$ random circuit is necessary and sufficient to converge (with high probability) to zero failure probability for any finite amount below the optimal erasure threshold, set by the channel capacity, for any $D$. Previous results on random circuits have only shown that $O(N^{1/D})$ depth suffices or that $O({\log }^{3}N)$ depth suffices for all-to-all connectivity ($D\to \infty$). We then study the critical behavior of the erasure threshold in the so-called moderate deviation limit, where both the failure probability and the distance to the optimal threshold converge to zero with $N$. We find that the requisite depth scales like $O(\log N)$ only for dimensions $D\ge 2$, and that random circuits require $O(\sqrt{N})$ depth for $D=1$. Finally, we introduce an "expurgation" algorithm that uses quantum measurements to remove logical operators that cause the code to fail by turning them into additional stabilizers or gauge operators. With such targeted measurements, we can achieve sub-logarithmic depth in $D\ge 2$ below capacity without increasing the maximum weight of the check operators. We find that for any rate beneath the capacity, high-performing codes with thousands of logical qubits are achievable with depth 4-8 expurgated random circuits in $D=2$ dimensions. These results indicate that finite-rate quantum codes are practically relevant for near-term devices and may significantly reduce the resource requirements to achieve fault tolerance for near-term applications.

arXiv comment23 pages, 11 figures; v1: Presented at QIP 2021; v2: Accepted journal version, minor changes to improve readability and rigor

References in corpus (111)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• The Quantum Internet
• Surface codes: Towards practical large-scale quantum computation
• Many body localization and thermalization in quantum statistical mechanics
• From Quantum Chaos and Eigenstate Thermalization to Statistical Mechanics and Thermodynamics
• Entropy and Area
• Topological quantum memory
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Improved Simulation of Stabilizer Circuits
• Black holes as mirrors: quantum information in random subsystems
• Quantum Computing with Very Noisy Devices
• Characterizing Quantum Supremacy in Near-Term Devices
• Holographic quantum error-correcting codes: Toy models for the bulk/boundary correspondence
• The capacity of the noisy quantum channel
• Demonstration of a small programmable quantum computer with atomic qubits
• Operator Spreading in Random Unitary Circuits
• Measurement-Induced Phase Transitions in the Dynamics of Entanglement
• Topological Quantum Distillation
• A simple formula for the average gate fidelity of a quantum dynamical operation
• Quantum Zeno Effect and the Many-body Entanglement Transition
• Chaos in quantum channels
• Large Scale Modular Quantum Computer Architecture with Atomic Memory and Photonic Interconnects
• Quantum Entanglement Growth Under Random Unitary Dynamics
• Quantum data processing and error correction
• Parallel implementation of high-fidelity multi-qubit gates with neutral atoms
• Dynamically protected cat-qubits: a new paradigm for universal quantum computation
• Measurement-driven entanglement transition in hybrid quantum circuits
• Surface code quantum computing by lattice surgery
• Operator hydrodynamics, OTOCs, and entanglement growth in systems without conservation laws
• High-Fidelity Universal Gate Set for ${}^9$Be${}^{+}$ Ion Qubits
• Detecting arbitrary quantum errors via stabilizer measurements on a sublattice of the surface code
• Theory of the phase transition in random unitary circuits with measurements
• Measurement-induced criticality in random quantum circuits
• Operator spreading and the emergence of dissipative hydrodynamics under unitary evolution with conservation laws
• Operator Quantum Error Correcting Subsystems for Self-Correcting Quantum Memories
• From Classical to Quantum Shannon Theory
• Unitary-projective entanglement dynamics
• A blueprint for demonstrating quantum supremacy with superconducting qubits
• Quantum Error Correction in Scrambling Dynamics and Measurement-Induced Phase Transition
• A Coherent Spin-Photon Interface in Silicon
• Towards the fast scrambling conjecture
• Dynamical purification phase transitions induced by quantum measurements
• Critical properties of the measurement-induced transition in random quantum circuits
• Fidelity benchmarks for two-qubit gates in silicon
• Capacities of Quantum Erasure Channels
• Entanglement transition in a monitored free fermion chain -- from extended criticality to area law
• Random Quantum Circuits are Approximate 2-designs
• Entanglement in a fermion chain under continuous monitoring
• Scalable probes of measurement-induced criticality
• Local random quantum circuits are approximate polynomial-designs
• Diffusive hydrodynamics of out-of-time-ordered correlators with charge conservation
• Quantum Channel Capacity of Very Noisy Channels
• Hardware-efficient autonomous quantum error correction
• Solution of a minimal model for many-body quantum chaos
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Quantum LDPC codes with positive rate and minimum distance proportional to n^{1/2}
• Entanglement transition from variable-strength weak measurements
• Emergent statistical mechanics of entanglement in random unitary circuits
• The XZZX Surface Code
• Fast Decoders for Topological Quantum Codes
• Entanglement phase transitions in measurement-only dynamics
• Measurement-induced topological entanglement transitions in symmetric random quantum circuits
• Almost-linear time decoding algorithm for topological codes
• Statistical mechanics of quantum error correcting codes
• Measurement Protected Quantum Phases
• Measurement and entanglement phase transitions in all-to-all quantum circuits, on quantum trees, and in Landau-Ginsburg theory
• Ultrahigh Error Threshold for Surface Codes with Biased Noise
• Efficient learning of quantum noise
• Fault-tolerant quantum computation against biased noise
• Measurement-induced quantum criticality under continuous monitoring
• Topological Computation without Braiding
• Long-range quantum entanglement in noisy cluster states
• Self-Organized Error Correction in Random Unitary Circuits with Measurement
• Bias-preserving gates with stabilized cat qubits
• Tradeoffs for reliable quantum information storage in 2D systems
• Measurement-induced phase transition: A case study in the non-integrable model by density-matrix renormalization group calculations
• A decoupling approach to the quantum capacity
• Repetition Cat Qubits for Fault-Tolerant Quantum Computation
• Entanglement Transition in the Projective Transverse Field Ising Model
• Degenerate Quantum Codes for Pauli Channels
• Dynamics of entanglement and transport in 1D systems with quenched randomness
• Tailoring surface codes for highly biased noise
• Efficient estimation of Pauli channels
• Poking holes and cutting corners to achieve Clifford gates with the surface code
• Fault-tolerant thresholds for the surface code in excess of 5% under biased noise
• Measurement-induced entanglement transitions in many-body localized systems
• Fault-Tolerant Quantum Computation with Local Gates
• Fault-Tolerance of "Bad" Quantum Low-Density Parity Check Codes
• Measurement-induced dynamics of many-body systems at quantum criticality
• Measurement-induced transitions of the entanglement scaling law in ultracold gases with controllable dissipation
• High threshold error correction for the surface code
• Decoupling with random quantum circuits
• A scheme for demonstration of fractional statistics of anyons in an exactly solvable model
• Statistical mechanical models for quantum codes with correlated noise
• Two-qubit entangling gates within arbitrarily long chains of trapped ions
• Linear-Time Maximum Likelihood Decoding of Surface Codes over the Quantum Erasure Channel
• Nonuniversal Entanglement Level Statistics in Projection-driven Quantum Circuits
• How Dynamical Quantum Memories Forget
• Quantum Expander Codes
• Mean-field entanglement transitions in random tree tensor networks
• An efficient Markov chain Monte Carlo algorithm for the surface code
• Quantum Coding with Finite Resources
• A fault-tolerant non-Clifford gate for the surface code in two dimensions
• Clifford Gates by Code Deformation
• Calderbank-Steane-Shor Holographic Quantum Error Correcting Codes
• Fault-Tolerant Quantum Gates with Defects in Topological Stabiliser Codes
• Moderate deviation analysis for classical communication over quantum channels
• Short random circuits define good quantum error correcting codes
• Approximate quantum error correction
• Fault-Tolerant Quantum Computation with Constant Overhead
• Decoding Schemes for Foliated Sparse Quantum Error Correcting Codes

Cited by in corpus (25)

• Observation of measurement-induced quantum phases in a trapped-ion quantum computer
• Topological order and criticality in (2+1)D monitored random quantum circuits
• Measurement-induced criticality and entanglement clusters: a study of 1D and 2D Clifford circuits
• Topological transitions with continuously monitored free fermions
• Classical Shadow Tomography with Locally Scrambled Quantum Dynamics
• Entanglement Domain Walls in Monitored Quantum Circuits and the Directed Polymer in a Random Environment
• Disordered monitored free fermions
• Entanglement phase transitions in random stabilizer tensor networks
• Re-examining the quantum volume test: Ideal distributions, compiler optimizations, confidence intervals, and scalable resource estimations
• Quantum Lego: Building Quantum Error Correction Codes from Tensor Networks
• Diagnosing entanglement dynamics in noisy and disordered spin chains via the measurement-induced steady-state entanglement transition
• Decodable hybrid dynamics of open quantum systems with Z_2 symmetry
• Clifford-deformed Surface Codes
• Crystalline Quantum Circuits
• Surface codes, quantum circuits, and entanglement phases
• Absence of measurement-induced entanglement transition due to feedback-induced skin effect
• Quantum Error Correction via Noise Guessing Decoding
• One-shot quantum error correction of classical and quantum information
• Local tensor-network codes
• Non-unitary Entanglement Dynamics in Continuous Variable Systems
• Low-depth random Clifford circuits for quantum coding against Pauli noise using a tensor-network decoder
• Finite-rate sparse quantum codes aplenty
• Quantum error correction in a time-dependent transverse field Ising model
• Field theory of charge sharpening in symmetric monitored quantum circuits
• Information Bounds on phase transitions in disordered systems