×

Quantum locally testable codes. (English) Zbl 1326.81054

Summary: 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(\delta)\), which is the probability that a randomly chosen constraint is violated, is proportional to the proximity \(\delta\), where \(\delta 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, No. 4, 889–974 (2006; Zbl 1118.68071)] 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, “The quantum PCP conjecture”, ACM SIGACT News 44, No. 2, 47–79 (2013; doi:10.1145/2491533.2491549)].

MSC:

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

Citations:

Zbl 1118.68071

References:

[1] D. Aharonov, I. Arad, Z. Landau, and U. Vazirani, {\it The Detectability Lemma and Quantum Gap Amplification}, preprint, arXiv:0811.3412. · Zbl 1304.68049
[2] D. Aharonov, I. Arad, and T. Vidick, {\it The quantum PCP conjecture}, ACM SIGACT News Archive, 44 (2013), pp. 47-79.
[3] D. Aharonov and L. Eldar, {\it The commuting local Hamiltonian problem on local expanders is in NP}, preliminary version of the results appeared in the preprint quant-ph arXiv:1301.3407.
[4] N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn, and D. Ron, {\it Testing Reed-Muller codes}, IEEE Trans. Inform. Theory, 51 (2005), pp. 4032-4039. · Zbl 1247.94057
[5] S. Arora, {\it Probabilistic Checking of Proofs and the Hardness of Approximation Problems}, Ph.D. thesis, UC Berkeley, 1994.
[6] S. Arora and B. Barak, {\it Computational Complexity: A Modern Approach}, Cambridge University Press, Cambridge, UK, 2009. · Zbl 1193.68112
[7] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, {\it Proof verification and intractability of Approximation problems}, J. ACM, 45 (1998), pp. 501-555. · Zbl 1065.68570
[8] S. Arora and S. Safra, {\it Probabilistic checking of proofs: A new characterization of NP}, J. ACM, 45 (1998), pp. 70-122. · Zbl 0903.68076
[9] L. Babai, L. Fortnow, L. Levin, and M. Szegedy, {\it Checking computation in polylogarithmic time}, in Proceedings of the 23rd ACM Symposium on Theory of Computation, New Orleans, 1991.
[10] D. Bacon, {\it Operator quantum error correcting subsystems for self-correcting quantum memories}, Phys. Rev. A, 73 (2005), 012340.
[11] H. Barnum, C. Crepeau, D. Gottesman, A. Smith, and A. Tapp, {\it Authentication of quantum messages}, in Proceedings of the 43rd Annual IEEE Symposium on the Foundations of Computer Science (FOCS ’02), IEEE Press, 2002, pp. 449-458.
[12] H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf, {\it Quantum fingerprinting}, Phys. Rev. Lett., 87 (2001), 167902.
[13] E. Ben-Sasson, A. Chiesa, D. Genkin, E. Tromer, and M. Virza, {\it Verifying program executions succinctly and in zero knowledge}, in Proceedings of the 33rd International Cryptology Conference (CRYPTO 2013). · Zbl 1317.68050
[14] E. Ben-Sasson, O. Goldreich, P. Harsha, M. Sudan, and S. P. Vadhan, {\it Sound PCPs of proximity, shorter PCPs, and applications to coding}, SIAM J. Comput., 36 (2006), pp. 889-974. · Zbl 1118.68071
[15] E. Ben-Sasson and M. Sudan, {\it Short PCPs with polylog query complexity}, SIAM J. Comput., 38 (2008), pp. 551-607. · Zbl 1172.68025
[16] F. G. S. L. Branda͂o and A. W. Harrow, {\it Product-state approximations to quantum ground states}, in Proceedings of the 45th ACM Symposium on Theory of Computing (STOC 2013), pp. 871-880. · Zbl 1293.68127
[17] S. Bravyi and M. B. Hastings, {\it Homological Product Codes}, preprint, arXiv:1311.0885, 2013. · Zbl 1315.94143
[18] S. Bravyi and M. B. Hastings, {\it A short proof of stability of topological order under local perturbations}, Commun. Math. Phys., 307 (2011), pp. 609-627. · Zbl 1229.81089
[19] S. Bravyi, M. B. Hastings, and S. Michalakis, {\it Topological quantum order: Stability under local perturbations}, J. Math. Phys., 51 (2010), 093512. · Zbl 1309.81067
[20] S. Bravyi, D. Poulin, and B. M. Terhal, {\it Tradeoffs for reliable quantum information storage in \(2\) D systems}, Phys. Rev. Lett., 104 (2010), 050503. · Zbl 1197.81083
[21] S. Bravyi and B. Terhal, {\it A no-go theorem for a two-dimensional self-correcting quantum memory based on stabilizer codes}, New J. Phys., 11 (2009).
[22] M. R. Capalbo, O. Reingold, S. Vadhan, and A. Wigderson, {\it Randomness conductors and constant-degree lossless expanders}, in Proceedings of the ACM Symposium on Theory of Computing (STOC), 2002, pp. 659-668. · Zbl 1192.68475
[23] S. Chesi, D. Loss, S. Bravyi, and B. M. Terhal, {\it Thermodynamic stability criteria for a quantum memory based on stabilizer and subsystem codes}, New J. Phys., 12 (2010), 025013. · Zbl 1360.82045
[24] A. Couvreur, N. Delfosse, and G. Zémor, {\it A construction of quantum LDPC codes from Cayley graphs}, in Proceedings of the IEEE International Symposium on Information Theory Proceedings (ISIT), 2011, pp. 643-647. · Zbl 1364.81086
[25] E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, {\it Topological quantum memory}, J. Math. Phys., 43 (2002), pp. 4452-4505. · Zbl 1060.94045
[26] I. Dinur, {\it The PCP theorem by gap amplification}, J. ACM, 54 (2007), 12. · Zbl 1292.68074
[27] I. Dinur and T. Kaufman, {\it On the Structure of NP-hard \(3\)-SAT Instances, and a Similar Question for LTCs}, talk at the Fourth Israel CS Theory Day Thursday, March 24, 2011.
[28] I. Dinur and T. Kaufman, {\it Locally Testable Codes and Expanders}, preprint. · Zbl 1343.94103
[29] L. Eldar, {\it Quantum Systems with Approximation-Robust Entanglement}, preprint, 2015.
[30] E. Fetaya, {\it Bounding the distance of quantum surface codes}, J. Math. Phys., 53 (2012), 062202. · Zbl 1276.81036
[31] K. Friedl and M. Sudan, {\it Some improvements to total degree tests}, in Proceedings of the 3rd Israel Symposium on Theoretical and Computing Systems (Tel Aviv, Israel), 1998.
[32] O. Goldreich, {\it Short Locally Testable Codes and Proofs: A Survey in Two Parts}, in Property Testing: Current Research and Surveys, Lecture Notes in Comput. Sci. 6390, Springer, New York, 2010, pp. 65-104. · Zbl 1309.68218
[33] O. Goldreich, S. Goldwasser, and D. Ron, {\it Property testing and its connection to learning and approximation}, J. ACM, 45 (1998), pp. 653-750. · Zbl 1065.68575
[34] O. Goldreich and M. Sudan, {\it Locally testable codes and PCPs of almost-linear length}, J. ACM, 53 (2006), pp. 558-655. · Zbl 1315.94144
[35] D. Gottesman, {\it Stabilizer Codes and Quantum Error Correction}, Ph.D. thesis, Caltech, Pasadena, CA, 2004.
[36] D. Gottesman, {\it A theory of fault-tolerant quantum computation}, Phys. Rev. A, 57 (1998), pp. 127-137.
[37] D. Gottesman, {\it On the theory of quantum secret sharing}, Phys. Rev. A, 61 (2000), 042311.
[38] J. Haah, {\it Local stabilizer codes in three dimensions without string logical operators}, Phys. Rev. A, 83 (2011), 042330.
[39] J. Haah and J. Preskill, {\it Logical-operator tradeoff for local quantum codes}, Phys. Rev. A, 86 (2012), 032308.
[40] J. H\aa stad, {\it Some optimal inapproximability results}, J. ACM, 48 (2001), pp. 798-859. · Zbl 1127.68405
[41] M. B. Hastings, {\it Trivial Low Energy States for Commuting Hamiltonians, and the Quantum PCP Conjecture}, preprint, arXiv:1201.3387v1, 2012.
[42] M. B. Hastings, {\it Decoding in Hyperbolic Spaces: LDPC Codes with Linear Rate and Efficient Error Correction}, preprint, arXiv:1312.2546, 2013.
[43] A. Yu. Kitaev, {\it Fault-tolerant quantum computation by anyons}, Ann. Physics, 303 (2003), pp. 2-30. · Zbl 1012.81006
[44] A. Yu. Kitaev, A. H. Shen, and M. N. Vyalyi, {\it Classical and Quantum Computation}, Grad. Stud. Math. 47, AMS, Providence, RI, 2002. · Zbl 1022.68001
[45] E. Knill, R. Laflamme, A. Ashikhmin, H. Barnum, L. Viola, and W. H. Zurek, {\it Introduction to Quantum Error Correction}, preprint, \burlhttp://arxiv.org/abs/quant-ph/0207170, 2002.
[46] A. A. Kovalev and L. P. Pryadko, {\it Fault Tolerance of “Bad” Quantum Low Density Parity Check Codes}, preprint, arXiv:1208.2317, 2012.
[47] A. A. Kovalev and L. P. Pryadko, {\it Quantum “Hyperbicycle” Low Density Parity Check Codes with Finite Rate}, preprint, arXiv:1212.6703, 2012.
[48] F. J. MacWilliams and N. J. A. Sloane, North-Holland, Amsterdam, 1977.
[49] K. Michnicki, {\it 3-d Quantum Stabilizer Codes with a Power Law Energy Barrier}, preprint, arXiv:1208.3496, 2012.
[50] M. A. Nielsen and I. L. Chuang, {\it Quantum Computation and Quantum Information} (10th anniversary ed.), Cambridge University Press, Cambridge, UK, 2010. · Zbl 1288.81001
[51] R. Rubinfeld and M. Sudan, {\it Robust characterizations of polynomials with applications to program testing}, SIAM J. Comput., 25 (1996), pp. 252-271. · Zbl 0844.68062
[52] M. Sipser and D. Spielman, {\it Expander codes}, IEEE Trans. Inform. Theory, 42 (1996), pp. 1710-1722. · Zbl 0943.94543
[53] A. Steane, {\it Quantum Reed-Muller Codes}, preprint, arXiv:quant-ph/9608026, 1996. · Zbl 0957.94054
[54] R. M. Tanner, {\it A recursive approach to low-complexity codes}, IEEE Trans. Inform. Theory, 27 (1981), pp. 533-547. · Zbl 0474.94029
[55] J. P. Tillich and G. Zémor, {\it Quantum LDPC codes with positive rate and minimum distance proportional to \(n^{1/2}\)}, in Proceedings of the IEEE International Symposium on Information Theory (ISIT) 2009, pp. 799-803.
[56] B. Yoshida, {\it Feasibility of self-correcting quantum memory and thermal stability of topological order}, Ann. Phys., 326 (2011), pp. 2566-2633. · Zbl 1232.81012
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.