Quantum locally testable codes

DOI10.1137/140975498zbMATH Open1326.81054arXiv1310.5664OpenAlexW2120102043MaRDI QIDQ3449558FDOQ3449558

Authors: Dorit Aharonov, Lior Eldar 

Publication date: 4 November 2015

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

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.

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

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

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)

Cites Work

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

Cited In (8)

• A construction of combinatorial NLTS
• 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
• Good quantum LDPC codes with linear time decoders
• Quantum codes from high-dimensional manifolds
• Single-shot decoding of good quantum LDPC codes
• Title not available (Why is that?)

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)