Complexity and order in approximate quantum error-correcting codes

Abstract

We establish rigorous connections between quantum circuit complexity and approximate quantum error correction (AQEC) capability, two properties of fundamental importance to the physics and practical use of quantum many-body systems, covering systems with both all-to-all connectivity and geometric scenarios like lattice systems in finite spatial dimensions. To this end, we introduce a type of code parameter that we call subsystem variance, which is closely related to the optimal AQEC precision. Our key finding is that, for a code encoding $k$ logical qubits in $n$ physical qubits, if the subsystem variance is below an $O(k/n)$ threshold, then any state in the code subspace must obey certain circuit complexity lower bounds, which identify nontrivial "phases" of codes. Based on our results, we propose $O(k/n)$ as a boundary between subspaces that should and should not count as AQEC codes. This theory of AQEC provides a versatile framework for understanding quantum complexity and order in many-body quantum systems, generating new insights for wide-ranging physical scenarios, in particular topological order and critical quantum systems which are of outstanding importance in many-body and high energy physics. We observe from various different perspectives that roughly $O(1/n)$ represents a common, physically significant "scaling threshold" of subsystem variance for features associated with nontrivial quantum order.

30 pages, 2 figures. Compared to published version: similar content, slightly different organization and presentation

References in corpus (40)

• Gauge Theory Correlators from Non-Critical String Theory
• The Large N Limit of Superconformal Field Theories and Supergravity
• Topological entanglement entropy
• A bound on chaos
• Detecting topological order in a ground state wave function
• Comments on the Sachdev-Ye-Kitaev model
• Symmetries and Strings in Field Theory and Gravity
• Local unitary transformation, long-range quantum entanglement, wave function renormalization, and topological order
• Bulk Locality and Quantum Error Correction in AdS/CFT
• Holography from Conformal Field Theory
• Lieb-Robinson bounds and the generation of correlations and topological quantum order
• Three-Dimensional Gravity Revisited
• Quasi-adiabatic Continuation of Quantum States: The Stability of Topological Ground State Degeneracy and Emergent Gauge Invariance
• Topological quantum order: stability under local perturbations
• The Second Law of Quantum Complexity
• A Universal Inequality for CFT and Quantum Gravity
• Central Charge Bounds in 4D Conformal Field Theory
• General conditions for approximate quantum error correction and near-optimal recovery channels
• A simple approach to approximate quantum error correction based on the transpose channel
• Continuous symmetries and approximate quantum error correction
• Quantum Error Correcting Codes in Eigenstates of Translation-Invariant Spin Chains
• Markov entropy decomposition: a variational dual for quantum belief propagation
• Tensor product representation of topological ordered phase: necessary symmetry conditions
• Using Quantum Metrological Bounds in Quantum Error Correction: A Simple Proof of the Approximate Eastin-Knill Theorem
• Continuous groups of transversal gates for quantum error correcting codes from finite clock reference frames
• Operator Product Expansion Coefficients of the 3D Ising Criticality via Quantum Fuzzy Sphere
• Conformal fields and operator product expansion in critical quantum spin chains
• Error Correction of Quantum Reference Frame Information
• New perspectives on covariant quantum error correction
• Near-optimal covariant quantum error-correcting codes from random unitaries with symmetries
• Optimal Universal Quantum Error Correction via Bounded Reference Frames
• Long-range entanglement is necessary for a topological storage of quantum information
• Limits on the storage of quantum information in a volume of space
• Approximate quantum error correction
• Approximate symmetries and quantum error correction
• Quasi-exact quantum computation
• Good approximate quantum LDPC codes from spacetime circuit Hamiltonians
• Theory of quasi-exact fault-tolerant quantum computing and valence-bond-solid codes
• Quantum error correction meets continuous symmetries: fundamental trade-offs and case studies
• Approaching the Quantum Singleton Bound with Approximate Error Correction

Cited by in corpus (12)

• Extracting Error Thresholds through the Framework of Approximate Quantum Error Correction Condition
• Quantum-machine-assisted Drug Discovery
• Covariant Quantum Error-Correcting Codes with Metrological Entanglement Advantage
• Letting the tiger out of its cage: bosonic coding without concatenation
• Vulnerability of fault-tolerant topological quantum error correction to quantum deviations in code space
• Variational LOCC-assisted quantum circuits for long-range entangled states
• Quantum circuit complexity and unsupervised machine learning of topological order
• Error Threshold of SYK Codes from Strong-to-Weak Parity Symmetry Breaking
• Universal Decay of Mutual Information and Conditional Mutual Information in Gapped Pure- and Mixed-State Quantum Matter
• Non-Commutative weak measurements: Entanglement, Symmetry Breaking, and the Role of Readout
• Approximate Quantum Error Correction with 1D Log-Depth Circuits
• Wavefunction branches demand a definition!