We initiate the study of quantum locally testable codes (
qLTCs). Classical
LTCs are very important in computational complexity. These codes are defined as the linear subspace satisfying a set of local constraints, with the additional requirement that their soundness,
R(δ), which is the probability that a randomly chosen constraint is violated, is proportional to the proximity
δ, where
δn is the distance of a word from the code. Excellent
LTCs exist in the classical world, and they are tightly related to the celebrated
PCP (probabilistically checkable proof) theorem. In quantum complexity, quantum error correcting codes provide central examples in the study of the illusive behavior of multiparticle entanglement, and they have played a crucial role in many computational complexity results. We provide a definition of the quantum analogue of
LTCs and motivate it by connecting its central notions in the study of both entanglement and quantum Hamiltonian complexity. A natural question is whether such codes exist, and how good can their soundness be. To the best of our knowledge all quantum codes known today exhibit poor soundness. Moreover, we show that the soundness of
CSS codes (which are commonly used quantum codes defined by two classical codes) is governed by the minimal soundness of the two classical codes; in the most natural
CSS code we examined as a candidate
qLTC, namely, the Reed--Muller code, there is a tradeoff between the parameters of the two codes, which prevents the resulting quantum code from being
qLTC. These facts seem to suggest a more general phenomenon, by which the soundness of
qLTCs is inherently restricted due to multiparticle entanglement. Our main technical contribution consists of two complementary results regarding
qLTCs which are stabilizer codes (denoted
sLTCs). We first prove a surprising, inherently quantum property of
sLTCs. For small constant values of proximity, the better the local expansion of the interaction graph of the constraints, the less sound the
sLTC becomes. This stands in sharp contrast to the classical setting. The complementary, more intuitive result also holds (and is actually much more involved technically to prove in the quantum case): an upper bound on the soundness when the code is defined on bad local expanders. Together we arrive at a quantum upper bound on the soundness of
sLTCs 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, and their relation to other objects of interest in quantum information theory. In the appendix we also define a quantum analogue of
PCPs of proximity (
PCPPs) and point out that the result of [E. Ben-Sasson et al., SIAM J. Comput., 36 (2006), pp. 889--974] by which
PCPPs imply
LTCs with related parameters carries over to the
sLTCs. This creates a first link between
qLTCs and quantum
PCPs [D. Aharonov, I. Arad, and T. Vidick, ACM SIGACT News Archive, 44 (2013), pp. 47--79].
In this work, we continue the search for quantum locally testable codes (qLTCs) of new parameters by presenting three constructions that can make new qLTCs from old. The first analyses the soundness of a quantum code under Hastings’ weight reduction construction for qLDPC codes to give a weight reduction procedure for qLTCs. Secondly, we describe a novel ‘soundness amplification’ procedure for qLTCs which can increase the soundness of any qLTC to a constant while preserving its distance and dimension, with an impact only felt on its locality. Finally, we apply the AEL distance amplification construction to the case of qLTCs for the first time which can turn a high-distance qLTC into one with linear distance, at the expense of other parameters. These constructions can be used on as-yet undiscovered qLTCs to obtain new parameters, but we also find a number of present applications to prove the existence of codes in previously unknown parameter regimes. In particular, applications of these operations to the hypersphere product code and the hemicubic code yield many previously unknown parameters. In addition, applications of all three results are described to an upcoming work.
We construct quantum locally testable codes (LTCs) with constant rate, distance, soundness and locality under a variant of a product expansion conjecture of Bafna and Vyas about Reed-Solomon codes. In particular, we use the high-dimensional expansion framework of Dinur, Lin and Vidick for constructing quantum LTCs, instantiated with the non-Abelian cubical complexes of Rungtanapirom, Stix and Vdovina. Our code is obtained by equipping the complex with carefully chosen Reed-Solomon local codes whose symmetries are compatible with those of the complex.
In this paper, we prove a lower bound on the soundness of quantum locally testable codes under the distance balancing construction of Evra et al. arXiv:2004.07935 [quant-ph]. Our technical contribution is that the new soundness of the quantum code is at least the old soundness divided by the classical code length (up to a constant factor). This allows us to use any classical code with independent checks when distance balancing, where previously only the repetition code had been considered for qLTCs. By using a good classical LDPC code, we are able to grow the dimension of the hypersphere product codes arXiv:1608.05089 [quant-ph] and the hemicubic codes arXiv:1911.03069 [quant-ph] while maintaining their distance and locality, but at the expense of soundness. From this, and also by distance balancing a chain complex of Cross et al. arXiv:2209.11405 [cs.IT], we obtain quantum locally testable codes of new parameters.
In this paper, we present two constructions of quantum locally testable codes (QLTC) with constant soundness. In the first approach, we introduce an operation called check product, and show how this operation gives rise to QLTCs of constant soundness, constant rate, and distance scaling with locality. In the second approach, we consider hypergraph product of a quantum code and a classical repetition code, and observe a special case in which the soundness of component codes is preserved. This insight leads us to construct QLTCs of constant soundness, scalable rate and distance, and constant average locality. Our work marks a step towards constructing QLTCs of high soundness and distance, which would give a different construction to the No Low-Energy Trivial States (NLTS) theorem.
Quantum low-density parity-check (qLDPC) codes can be implemented by measuring only low-weight checks, making them compatible with noisy quantum hardware and central to the quest to build noise-resilient quantum computers. A fundamental open question is how constraints on check weight limit the achievable parameters of qLDPC codes. Here, we study stabilizer and subsystem codes with constrained check weight, combining analytical arguments with numerical optimization to establish strong upper bounds on their parameters. We show that stabilizer codes with checks of weight at most three cannot have nontrivial distance. We also prove tight tradeoffs between rate and distance for broad families of CSS stabilizer and subsystem codes with checks of weight at most four and two, respectively. Notably, our bounds are applicable to general qLDPC codes, as they rely only on check-weight constraints without assuming geometric locality or special graph connectivity. In the finite-size regime, we derive numerical upper bounds using linear programming techniques and identify explicit code constructions that approach these limits, delineating the landscape of practically relevant qLDPC codes with tens or hundreds of physical qubits.