Good approximate quantum LDPC codes from spacetime circuit Hamiltonians
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. The code space is stabilized by a set of 10-local noncommuting projectors, with each physical qubit only participating in O(polylogN) 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 1/poly(n) by analyzing a spacetime circuit-to-Hamiltonian construction for a bitonic sorting network architecture that is spatially local in polylog(N) dimensions. The reference for this talk is: Good approximate quantum LDPC codes from spacetime circuit Hamiltonians Good approximate quantum LDPC codes from spacetime circuit Hamiltonians T. Bohdanowicz, E. Crosson, C. Nirkhe, H. Yuen. arXiv:1811.00277. STOC 2019