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 prove a lower bound on the soundness of quantum locally testable codes under the distance balancing construction of Evra et al. Our technical contribution is that the soundness of the quantum code after this procedure is at least its soundness before the procedure divided by the length of the classical code used to perform distance balancing. This allows us to use any classical code when distance balancing, where previously only the repetition code had been considered for these codes. By using a good classical low-density parity check (LDPC) code, we are able to grow the dimension of the hypersphere product codes and the hemicubic codes 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., 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.
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].
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.
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(δ), namely, the probability that a randomly chosen constraint is violated as a function of the distance of a word from the code (
δ, 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.