A Caltech Library Service

Good approximate quantum LDPC codes from spacetime circuit Hamiltonians

Bohdanowicz, Thomas C. and Crosson, Elizabeth and Nirkhe, Chinmay and Yuen, Henry (2019) Good approximate quantum LDPC codes from spacetime circuit Hamiltonians. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC '19). Association for Computing Machinery , New York, NY, pp. 481-490. ISBN 978-1-4503-6705-9.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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,ε]] approximate QLDPC codes that encode k = Ω(N) logical qubits into N physical qubits with distance d = Ω(N) and approximation infidelity ε = 1/(N). The code space is stabilized by a set of 10-local noncommuting projectors, with each physical qubit only participating in N projectors. We prove the existence of an efficient encoding map and show that the spectral gap of the code Hamiltonian scales as Ω(N^(−3.09)). We also show that arbitrary Pauli errors can be locally detected by circuits of polylogarithmic depth. Our family of approximate QLDPC codes is based on applying a recent connection between circuit Hamiltonians and approximate quantum codes (Nirkhe, et al., ICALP 2018) to a result showing that random Clifford circuits of polylogarithmic depth yield asymptotically good quantum codes (Brown and Fawzi, ISIT 2013). Then, in order to obtain a code with sparse checks and strong detection of local errors, we use a spacetime circuit-to-Hamiltonian construction in order to take advantage of the parallelism of the Brown-Fawzi circuits. Because of this, we call our codes spacetime codes. The analysis of the spectral gap of the code Hamiltonian is the main technical contribution of this work. We show that for any depth D quantum circuit on n qubits there is an associated spacetime circuit-to-Hamiltonian construction with spectral gap Ω(n^(−3.09)D⁻² log⁻⁶ (n)). To lower bound this gap we use a Markov chain decomposition method to divide the state space of partially completed circuit configurations into overlapping subsets corresponding to uniform circuit segments of depth logn, which are based on bitonic sorting circuits. We use the combinatorial properties of these circuit configurations to show rapid mixing between the subsets, and within the subsets we develop a novel isomorphism between the local update Markov chain on bitonic circuit configurations and the edge-flip Markov chain on equal-area dyadic tilings, whose mixing time was recently shown to be polynomial (Cannon, Levin, and Stauffer, RANDOM 2017). Previous lower bounds on the spectral gap of spacetime circuit Hamiltonians have all been based on a connection to exactly solvable quantum spin chains and applied only to 1+1 dimensional nearest-neighbor quantum circuits with at least linear depth.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Additional Information:© 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM. We thank Winton Brown, Aram Harrow, and Umesh Vazirani for helpful discussions. Author TCB acknowleges support from NSERC through a PGSD award. Author CN is supported by ARO Grant W911NF-12-1-0541 and NSF Grant CCF-1410022. Part of this work was completed while authors EC, CN, and HY were visitors at the Simon’s Institute 2018 summer cluster Challenges in Quantum Computation.
Funding AgencyGrant Number
Natural Sciences and Engineering Research Council of Canada (NSERC)UNSPECIFIED
Army Research Office (ARO)W911NF-12-1-0541
Record Number:CaltechAUTHORS:20200423-091940720
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:102743
Deposited By: Tony Diaz
Deposited On:23 Apr 2020 16:36
Last Modified:23 Apr 2020 16:36

Repository Staff Only: item control page