Single-shot decoding of good quantum LDPC codes. (English) Zbl 07824913
Summary: Quantum Tanner codes constitute a family of quantum low-density parity-check codes with good parameters, i.e., constant encoding rate and relative distance. In this article, we prove that quantum Tanner codes also facilitate single-shot quantum error correction (QEC) of adversarial noise, where one measurement round (consisting of constant-weight parity checks) suffices to perform reliable QEC even in the presence of measurement errors. We establish this result for both the sequential and parallel decoding algorithms introduced by A. Leverrier and G. Zémor [IEEE Trans. Inf. Theory 69, No. 8, 5100–5115 (2023; Zbl 07883295)]. Furthermore, we show that in order to suppress errors over multiple repeated rounds of QEC, it suffices to run the parallel decoding algorithm for constant time in each round. Combined with good code parameters, the resulting constant-time overhead of QEC and robustness to (possibly time-correlated) adversarial noise make quantum Tanner codes alluring from the perspective of quantum fault-tolerant protocols.
MSC:
| 81P70 | Quantum coding (general) |
| 81P73 | Computational stability and error-correcting codes for quantum computation and communication processing |
| 81P68 | Quantum computation |
Citations:
Zbl 07883295References:
| [1] | Shor, PW, Scheme for reducing decoherence in quantum computer memory, Phys. Rev. A, 52, R2493, 1995 · doi:10.1103/PhysRevA.52.R2493 |
| [2] | Steane, AM, Error correcting codes in quantum theory, Phys. Rev. Lett., 77, 793, 1996 · Zbl 0944.81505 · doi:10.1103/PhysRevLett.77.793 |
| [3] | Gottesman, D., Class of quantum error-correcting codes saturating the quantum Hamming bound, Phys. Rev. A, 54, 1862, 1996 · doi:10.1103/PhysRevA.54.1862 |
| [4] | Kitaev, A., Fault-tolerant quantum computation by Anyons, Ann. Phys., 303, 2, 2003 · Zbl 1012.81006 · doi:10.1016/S0003-4916(02)00018-0 |
| [5] | Dennis, E.; Kitaev, A.; Landahl, A.; Preskill, J., Topological quantum memory, J. Math. Phys., 43, 4452, 2002 · Zbl 1060.94045 · doi:10.1063/1.1499754 |
| [6] | Bombin, H.; Martin-Delgado, MA, Topological quantum distillation, Phys. Rev. Lett., 97, 2006 · doi:10.1103/PhysRevLett.97.180501 |
| [7] | Bombín, H.; Martin-Delgado, M., Exact topological quantum order in \(D=3\) and beyond: Branyons and brane-net condensates, Phys. Rev. B, 75, 2007 · doi:10.1103/PhysRevB.75.075103 |
| [8] | Kubica, A.: The ABCs of the Color Code: A Study of Topological Quantum Codes as Toy Models for Fault-Tolerant Quantum Computation and Quantum Phases Of Matter, Ph.D. thesis, Caltech (2018). doi:10.7907/059V-MG69 |
| [9] | Bravyi, S.; Terhal, B., A no-go theorem for a two-dimensional self-correcting quantum memory based on stabilizer codes, New J. Phys., 11, 2009 · doi:10.1088/1367-2630/11/4/043029 |
| [10] | Bravyi, S.; Poulin, D.; Terhal, B., Tradeoffs for reliable quantum information storage in 2D systems, Phys. Rev. Lett., 104, 2010 · Zbl 1197.81083 · doi:10.1103/PhysRevLett.104.050503 |
| [11] | Baspin, N.; Krishna, A., Quantifying nonlocality: how outperforming local quantum codes is expensive, Phys. Rev. Lett., 129, 2022 · doi:10.1103/PhysRevLett.129.050505 |
| [12] | Breuckmann, NP; Eberhardt, JN, Quantum low-density parity-check codes, PRX Quantum, 2, 2021 · doi:10.1103/prxquantum.2.040101 |
| [13] | Evra, S., Kaufman, T., Zémor, G.: Decodable quantum ldpc codes beyond the \(\sqrt{n}\) distance barrier using high-dimensional expanders. SIAM J. Comput. FOCS20 (2022). doi:10.1137/20M1383689 · Zbl 1498.81063 |
| [14] | Hastings, M.B., Haah, J., O’Donnell, R.: Fiber bundle codes: breaking the \(n^{1/2} \text{polylog}(n)\) barrier for quantum LDPC codes. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 1276-1288 (2021). doi:10.1145/3406325.3451005 · Zbl 07765248 |
| [15] | Panteleev, P.; Kalachev, G., Quantum LDPC codes with almost linear minimum distance, IEEE Trans. Inf. Theory, 68, 213, 2022 · Zbl 1489.94162 · doi:10.1109/tit.2021.3119384 |
| [16] | Breuckmann, NP; Eberhardt, JN, Balanced product quantum codes, IEEE Trans. Inf. Theory, 67, 6653, 2021 · Zbl 1487.81056 · doi:10.1109/tit.2021.3097347 |
| [17] | Panteleev, P., Kalachev, G.: Asymptotically good quantum and locally testable classical LDPC codes. In: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 375-388 (2022). doi:10.1145/3519935.3520017 · Zbl 07774346 |
| [18] | Leverrier, A., Zémor, G.: Quantum Tanner codes. In: 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2022), pp. 872-883. doi:10.1109/FOCS54457.2022.00117 |
| [19] | Dinur, I., Hsieh, M.-H., Lin, T.-C., Vidick, T.: Good quantum LDPC codes with linear time decoders (2022). arXiv:2206.07750 |
| [20] | Terhal, BM, Quantum error correction for quantum memories, Rev. Mod. Phys., 87, 307, 2015 · doi:10.1103/RevModPhys.87.307 |
| [21] | Leverrier, A., Zémor, G.: Efficient decoding up to a constant fraction of the code length for asymptotically good quantum codes. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (SIAM, 2023), pp. 1216-1244. doi:10.1137/1.9781611977554.ch45 · Zbl 07848005 |
| [22] | Gu, S., Pattison, C.A., Tang, E.: An efficient decoder for a linear distance quantum LDPC code. In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing, series and number STOC 2023 (publisher Association for Computing Machinery, address New York, NY, USA, 2023), pp. 919-932. doi:10.1145/3564246.3585169 · Zbl 07844641 |
| [23] | Shor, P.: Fault-tolerant quantum computation. In: Proceedings of 37th Conference on Foundations of Computer Science (publisher IEEE Comput. Soc. Press, 1996), pp. 56-65. doi:10.1109/SFCS.1996.548464 |
| [24] | Bombín, H., Single-shot fault-tolerant quantum error correction, Phys. Rev. X, 5, 2015 · doi:10.1103/PhysRevX.5.031043 |
| [25] | Fawzi, O., Grospellier, A., Leverrier, A.: Constant overhead quantum fault-tolerance with quantum expander codes. In: 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) (publisher IEEE, 2018). doi:10.1109/focs.2018.00076 · Zbl 1428.81065 |
| [26] | Kubica, A.; Vasmer, M., Single-shot quantum error correction with the three-dimensional subsystem toric code, Nat. Commun., 13, 6272, 2022 · doi:10.1038/s41467-022-33923-4 |
| [27] | Bridgeman, J.C., Kubica, A., Vasmer, M.: Lifting topological codes: three-dimensional subsystem codes from two-dimensional Anyon models (2023). arXiv:2305.06365 |
| [28] | Bombín, H., Gauge color codes: optimal transversal gates and gauge fixing in topological stabilizer codes, New J. Phys., 17, 2015 · Zbl 1454.81052 · doi:10.1088/1367-2630/17/8/083002 |
| [29] | Campbell, ET, A theory of single-shot error correction for adversarial noise, Quantum Sci. Technol., 4, 2019 · doi:10.1088/2058-9565/aafc8f |
| [30] | Fujiwara, Y., Ability of stabilizer quantum error correction to protect itself from its own imperfection, Phys. Rev. A, 90, 2014 · doi:10.1103/PhysRevA.90.062304 |
| [31] | Ashikhmin, A.; Lai, CY; Brun, TA, Quantum Data-Syndrome Codes, IEEE J. Sel. Areas Commun., 38, 449, 2020 · doi:10.1109/JSAC.2020.2968997 |
| [32] | Delfosse, N.; Reichardt, BW; Svore, KM, Beyond single-shot fault-tolerant quantum error correction, IEEE Trans. Inf. Theory, 68, 287, 2022 · Zbl 1489.81016 · doi:10.1109/tit.2021.3120685 |
| [33] | Leverrier, A.; Zémor, G., Decoding quantum tanner codes, IEEE Trans. Inform. Theory, 2023 · Zbl 07883295 · doi:10.1109/TIT.2023.3267945 |
| [34] | Ben-Sasson, E.; Sudan, M., Robust locally testable codes and products of codes, Random Struct. Algor., 28, 387, 2006 · Zbl 1103.90080 · doi:10.1002/rsa.20120 |
| [35] | Dinur, I., Evra, S., Livne, R., Lubotzky, A., Mozes, S.: Locally testable codes with constant rate, distance, and locality. In: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (2022), pp. 357-374. doi:10.1145/3519935.3520024 · Zbl 07774345 |
| [36] | Kalachev, G., Panteleev, P.: Two-sided robustly testable codes (2022). arXiv:2206.09973 · Zbl 07774346 |
| [37] | Calderbank, AR; Shor, PW, Good quantum error-correcting codes exist, Phys. Rev. A, 54, 1098, 1996 · Zbl 07918813 · doi:10.1103/PhysRevA.54.1098 |
| [38] | Steane, A., Multiple-particle interference and quantum error correction, Proc. R. Soc. Lond. Ser. A: Math. Phys. Eng. Sci., 452, 2551, 1996 · Zbl 0876.94002 · doi:10.1098/rspa.1996.0136 |
| [39] | Knill, E., Quantum computing with realistically noisy devices, Nature, 434, 39, 2005 · doi:10.1038/nature03350 |
| [40] | Steane, AM, Active stabilization, quantum computation, and quantum state synthesis, Phys. Rev. Lett., 78, 2252, 1997 · doi:10.1103/physrevlett.78.2252 |
| [41] | Gottesman, D., Fault-tolerant quantum computation with constant overhead, Quantum Info. Comput., 14, 1338-1372, 2014 · doi:10.5555/2685179.2685184 |
| [42] | Grospellier, A.: Constant time decoding of quantum expander codes and application to fault-tolerant quantum computation, Ph.D. thesis, School Sorbonne Université (2019). https://theses.hal.science/tel-03364419v3 |
| [43] | Kaufman, T., Lubotzky, A.: High dimensional expanders and property testing (2013). arXiv:1312.2367 · Zbl 1365.68462 |
| [44] | Anshu, A., Breuckmann, N., Nirkhe, C.: NLTS Hamiltonians from good quantum codes (2022). arXiv:2206.13228 |
| [45] | Quintavalle, AO; Vasmer, M.; Roffe, J.; Campbell, ET, Single-shot error correction of three-dimensional homological product codes, PRX Quantum, 2, 2021 · doi:10.1103/PRXQuantum.2.020340 |
| [46] | Aharonov, D.; Eldar, L., Quantum locally testable codes, SIAM J. Comput., 44, 1230, 2015 · Zbl 1326.81054 · doi:10.1137/140975498 |
| [47] | Hastings, M. B.: Quantum codes from high-dimensional manifolds. In: 8th Innovations in Theoretical Computer Science Conference (ITCS 2017) (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017). doi:10.4230/LIPIcs.ITCS.2017.25 · Zbl 1406.81020 |
| [48] | Leverrier, A.; Londe, V.; Zémor, G., Towards local testability for quantum coding, Quantum, 6, 661, 2022 · Zbl 1326.81054 · doi:10.1137/140975498 |
| [49] | Cross, A., He, Z., Natarajan, A., Szegedy, M., Zhu, G.: Quantum locally testable code with exotic parameters (2022). arXiv:2209.11405 |
| [50] | Wills, A., Lin, T.-C., Hsieh, M.-H.: General distance balancing for quantum locally testable codes (2023). arXiv:2305.00689 |
| [51] | Cohen, L.Z., Kim, I.H., Bartlett, S.D., Brown, B.J.: Low-overhead fault-tolerant quantum computing using long-range connectivity. Sci. Adv. 8, eabn1717 (2022). doi:10.1126/sciadv.abn1717 |
| [52] | Tremblay, MA; Delfosse, N.; Beverland, ME, Constant-overhead quantum error correction with thin planar connectivity, Phys. Rev. Lett., 129, 2022 · doi:10.1103/physrevlett.129.050504 |
| [53] | Pattison, C.A., Krishna, A., Preskill, J.: Hierarchical memories: simulating quantum LDPC codes with local gates (2023). arXiv:2303.04798 |
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.
