Quantum locally testable codes

DOI10.1137/140975498MaRDI QIDQ3449558zbMATH OpenOpenAlexFDO

Authors Dorit Aharonov, Lior Eldar

Publication date 4 November 2015

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.5664

zbMATH Keywords

locally testable codesquantum error correcting codesstabilizer codesquantum PCP

Mathematics Subject Classification ID

Quantum computation (81P68) Quantum coherence, entanglement, quantum correlations (81P40) Quantum information, communication, networks (quantum-theoretic aspects) (81P45) Quantum coding (general) (81P70) Other types of codes (94B60) Error probability in coding theory (94B70)

Abstract: We initiate the study of quantum Locally Testable Codes (qLTCs). We provide a definition together with a simplification, denoted sLTCs, for the special case of stabilizer codes, together with some basic results using those definitions. The most crucial parameter of such codes is their soundness, $R(delta)$, namely, the probability that a randomly chosen constraint is violated as a function of the distance of a word from the code ($delta$, the relative distance from the code, is called the proximity). We then proceed to study limitations on qLTCs. In our first main result we prove a surprising, inherently quantum, property of sLTCs: for small values of proximity, the better the small-set expansion of the interaction graph of the constraints, the less sound the qLTC becomes. This phenomenon, which can be attributed to monogamy of entanglement, stands in sharp contrast to the classical setting. The complementary, more intuitive, result also holds: an upper bound on the soundness when the code is defined on poor small-set expanders (a bound which turns out to be far more difficult to show in the quantum case). Together we arrive at a quantum upper-bound on the soundness of stabilizer qLTCs set on any graph, which does not hold in the classical case. Many open questions are raised regarding what possible parameters are achievable for qLTCs. In the appendix we also define a quantum analogue of PCPs of proximity (PCPPs) and point out that the result of Ben-Sasson et. al. by which PCPPs imply LTCs with related parameters, carries over to the sLTCs. This creates a first link between qLTCs and quantum PCPs.

Recommendations

• Locally decodable quantum codes
• Explicit strong LTCs with inverse poly-log rate and constant soundness
• Locally Testable Codes Require Redundant Testers
• Dense locally testable codes cannot have constant rate and distance
• Strong locally testable codes with relaxed local decoders

Cites work

• scientific article; zbMATH DE number 5788515 (Why is no real title available?)
• scientific article; zbMATH DE number 1776257 (Why is no real title available?)
• A Construction of Quantum LDPC Codes From Cayley Graphs
• A recursive approach to low complexity codes
• A short proof of stability of topological order under local perturbations
• Bounding the distance of quantum surface codes
• Computational Complexity
• Dense locally testable codes cannot have constant rate and distance
• Expander codes
• Fault-tolerant quantum computation by anyons
• Feasibility of self-correcting quantum memory and thermal stability of topological order
• Homological product codes
• Locally testable codes and PCPs of almost-linear length
• Probabilistic checking of proofs
• Product-state approximations to quantum ground states
• Proof verification and the hardness of approximation problems
• Property testing and its connection to learning and approximation
• Quantum Reed-Muller codes
• Quantum computation and quantum information. 10th anniversary edition
• Randomness conductors and constant-degree lossless expanders
• Robust Characterizations of Polynomials with Applications to Program Testing
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Short PCPs with Polylog Query Complexity
• Short locally testable codes and proofs: a survey in two parts
• Snarks for C: verifying program executions succinctly and in zero knowledge
• Some optimal inapproximability results
• Testing Reed–Muller Codes
• The PCP theorem by gap amplification
• The detectability lemma and quantum gap amplification
• Thermodynamic stability criteria for a quantum memory based on stabilizer and subsystem codes
• Topological quantum memory
• Topological quantum order: Stability under local perturbations

Cited in

(8)

• Good quantum LDPC codes with linear time decoders
• scientific article; zbMATH DE number 5568625 (Why is no real title available?)
• Quantum codes from high-dimensional manifolds
• Good approximate quantum LDPC codes from spacetime circuit Hamiltonians
• Locally decodable quantum codes
• Approximate low-weight check codes and circuit lower bounds for noisy ground states
• Single-shot decoding of good quantum LDPC codes
• A construction of combinatorial NLTS

This page was built for publication: Quantum locally testable codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3449558)