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 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.
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 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±1) . The quantum code obtained by identifying antipodal faces of the resulting complex encodes one logical qubit into N=2n−p−1(np) physical qubits and displays local testability with a soundness of Ω(1/log(N)) beating the current state-of-the-art of 1/log2(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.