Good approximate quantum LDPC codes from spacetime circuit Hamiltonians

Abstract

We study approximate quantum low-density parity-check (QLDPC) codes, which are approximate quantum error-correcting codes specified as the ground space of a frustration-free local Hamiltonian, whose terms do not necessarily commute. Such codes generalize stabilizer QLDPC codes, which are exact quantum error-correcting codes with sparse, low-weight stabilizer generators (i.e. each stabilizer generator acts on a few qubits, and each qubit participates in a few stabilizer generators). Our investigation is motivated by an important question in Hamiltonian complexity and quantum coding theory: do stabilizer QLDPC codes with constant rate, linear distance, and constant-weight stabilizers exist? We show that obtaining such optimal scaling of parameters (modulo polylogarithmic corrections) is possible if we go beyond stabilizer codes: we prove the existence of a family of $[[N,k,d,\epsilon ]]$ approximate QLDPC codes that encode $k=\tilde{\Omega }(N)$ logical qubits into $N$ physical qubits with distance $d=\tilde{\Omega }(N)$ and approximation infidelity $\epsilon =\mathcal{O}(1/\text{polylog}(N))$. The code space is stabilized by a set of 10-local noncommuting projectors, with each physical qubit only participating in $\mathcal{O}(\text{polylog}N)$ projectors. We prove the existence of an efficient encoding map, and we show that arbitrary Pauli errors can be locally detected by circuits of polylogarithmic depth. Finally, we show that the spectral gap of the code Hamiltonian is $\tilde{\Omega }(N^{-3.09})$ by analyzing a spacetime circuit-to-Hamiltonian construction for a bitonic sorting network architecture that is spatially local in $\text{polylog}(N)$ dimensions.

arXiv comment51 pages, 13 figures

References in corpus (25)

• Fault-tolerant quantum computation by anyons
• Good Quantum Error-Correcting Codes Exist
• Bulk Locality and Quantum Error Correction in AdS/CFT
• Topological quantum order: stability under local perturbations
• Quantum LDPC codes with positive rate and minimum distance proportional to n^{1/2}
• A no-go theorem for a two-dimensional self-correcting quantum memory based on stabilizer codes
• Simple proof of equivalence between adiabatic quantum computation and the circuit model
• Approximate quantum error correction can lead to better codes
• General conditions for approximate quantum error correction and near-optimal recovery channels
• Quantum Error Correcting Codes in Eigenstates of Translation-Invariant Spin Chains
• Local Hamiltonians Whose Ground States are Hard to Approximate
• Universal adiabatic quantum computation via the space-time circuit-to-Hamiltonian construction
• The Feynman-Kitaev computer's clock: bias, gaps, idling and pulse tuning
• Limits on the storage of quantum information in a volume of space
• Space-Time Circuit-to-Hamiltonian Construction and Its Applications
• Short random circuits define good quantum error correcting codes
• Adiabatic and Hamiltonian computing on a 2D lattice with simple 2-qubit interactions
• Fault-Tolerant Quantum Computation with Constant Overhead
• The spectral gap of the ferromagnetic XXZ chain
• Topological quantum error correction in the Kitaev honeycomb model
• Good approximate quantum LDPC codes from spacetime circuit Hamiltonians
• Quantum Codes from High-Dimensional Manifolds
• Hamiltonian sparsification and gap-simulations
• Quantum ground state isoperimetric inequalities for the energy spectrum of local Hamiltonians
• History-state Hamiltonians are critical

Cited by in corpus (10)

• Balanced Product Quantum Codes
• Good approximate quantum LDPC codes from spacetime circuit Hamiltonians
• Towards local testability for quantum coding
• Complexity and order in approximate quantum error-correcting codes
• Theory of quasi-exact fault-tolerant quantum computing and valence-bond-solid codes
• Detailed Analysis of Circuit-to-Hamiltonian Mappings
• Constructing quantum codes from any classical code and their embedding in ground space of local Hamiltonians
• Approximate Quantum Codes From Long Wormholes
• Approximate low-weight check codes and circuit lower bounds for noisy ground states
• Quantum Merlin-Arthur proof systems for synthesizing quantum states