Towards local testability for quantum coding

Abstract

We introduce the hemicubic codes, a family of quantum codes obtained by associating qubits with the $p$-faces of the $n$-cube (for $n>p$) and stabilizer constraints with faces of dimension $(p\pm 1)$. The quantum code obtained by identifying antipodal faces of the resulting complex encodes one logical qubit into $N=2^{n-p-1}\left(\genfrac{}{}{0ex}{}{n}{p}\right)$ physical qubits and displays local testability with a soundness of $\Omega (1/\log (N))$ beating the current state-of-the-art of $1/{\log }^2(N)$ due to Hastings. We exploit this local testability to devise an efficient decoding algorithm that corrects arbitrary errors of size less than the minimum distance, up to polylog factors. We then extend this code family by considering the quotient of the $n$-cube by arbitrary linear classical codes of length $n$. We establish the parameters of these generalized hemicubic codes. Interestingly, if the soundness of the hemicubic code could be shown to be constant, similarly to the ordinary $n$-cube, then the generalized hemicubic codes could yield quantum locally testable codes of length not exceeding an exponential or even polynomial function of the code dimension.

arXiv comment44 pages, an extended abstract appeared at ITCS 2021 v2: journal version

References in corpus (17)

• Fault-tolerant quantum computation by anyons
• Good Quantum Error-Correcting Codes Exist
• Multiple Particle Interference and Quantum Error Correction
• Lieb-Robinson bounds and the generation of correlations and topological quantum order
• Stabilizer Formalism for Operator Quantum Error Correction
• Quantum LDPC Codes with Almost Linear Minimum Distance
• General conditions for approximate quantum error correction and near-optimal recovery channels
• Quantum Expander Codes
• Fiber Bundle Codes: Breaking the $N^{1/2}\mathrm{polylog}(N)$ Barrier for Quantum LDPC Codes
• Local Hamiltonians Whose Ground States are Hard to Approximate
• Low-degree testing for quantum states, and a quantum entangled games PCP for QMA
• Product-state Approximations to Quantum Ground States
• Good approximate quantum LDPC codes from spacetime circuit Hamiltonians
• Quantum Codes from High-Dimensional Manifolds
• Sparse Quantum Codes from Quantum Circuits
• Approximate low-weight check codes and circuit lower bounds for noisy ground states
• An application of Khovanov homology to quantum codes

Cited by in corpus (4)

• Software Tools for Decoding Quantum Low-Density Parity Check Codes
• Circuit lower bounds for low-energy states of quantum code Hamiltonians
• A construction of Combinatorial NLTS
• Quantum Locally Testable Code with Constant Soundness