Good quantum LDPC codes with linear time decoders. (English) Zbl 07844640
Saha, Barna (ed.) et al., Proceedings of the 55th annual ACM SIGACT symposium on theory of computing, STOC ’23, Orlando, FL, USA, June 20–23, 2023. New York, NY: Association for Computing Machinery (ACM). 905-918 (2023).
MSC:
| 68Qxx | Theory of computing |
References:
| [1] | Dorit Aharonov, Itai Arad, and Thomas Vidick. 2013. Guest column: the quantum PCP conjecture. Acm sigact news, 44, 2 (2013), 47-79. https://doi.org/10.1145/2491533.2491549 10.1145/2491533.2491549 |
| [2] | Dorit Aharonov and Lior Eldar. 2015. Quantum locally testable codes. SIAM J. Comput., 44, 5 (2015), 1230-1262. https://doi.org/10.1137/140975498 10.1137/140975498 · Zbl 1326.81054 |
| [3] | Vedat Levi Alev and Lap Chi Lau. 2020. Improved Analysis of Higher Order Random Walks and Applications. arXiv preprint arXiv:2001.02827. · Zbl 07298321 |
| [4] | Noga Alon and Fan RK Chung. 1988. Explicit construction of linear sized tolerant networks. Discrete Mathematics, 72, 1-3 (1988), 15-19. https://doi.org/10.1016/0012-365X(88)90189-6 10.1016/0012-365X(88)90189-6 · Zbl 0657.05068 |
| [5] | Nima Anari, Kuikui Liu, and Shayan Oveis Gharan. 2020. Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model. arXiv preprint arXiv:2001.00303. · Zbl 1522.05449 |
| [6] | Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant. 2019. Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. 1-12. https://doi.org/10.1145/3313276.3316385 10.1145/3313276.3316385 · Zbl 1433.68606 |
| [7] | Anurag Anshu, Nikolas Breuckmann, and Chinmay Nirkhe. 2022. NLTS Hamiltonians from good quantum codes. arXiv preprint arXiv:2206.13228. |
| [8] | Mitali Bafna, Max Hopkins, Tali Kaufman, and Shachar Lovett. 2021. Hypercontractivity on High Dimensional Expanders. arXiv preprint arXiv:2111.09444. |
| [9] | Eli Ben-Sasson and Madhu Sudan. 2004. Robust locally testable codes and products of codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer, 286-297. https://doi.org/10.1007/978-3-540-27821-4_26 10.1007/978-3-540-27821-4_26 · Zbl 1105.68346 |
| [10] | Nikolas P Breuckmann and Jens N Eberhardt. 2021. Balanced product quantum codes. IEEE Transactions on Information Theory, 67, 10 (2021), 6653-6674. https://doi.org/10.1109/TIT.2021.3097347 10.1109/TIT.2021.3097347 · Zbl 1487.81056 |
| [11] | Nikolas P Breuckmann and Jens Niklas Eberhardt. 2021. Quantum low-density parity-check codes. PRX Quantum, 2, 4 (2021), 040101. https://doi.org/10.1103/PRXQuantum.2.040101 10.1103/PRXQuantum.2.040101 · Zbl 1487.81056 |
| [12] | Nicolas Delfosse and Naomi H Nickerson. 2021. Almost-linear time decoding algorithm for topological codes. Quantum, 5 (2021), 595. https://doi.org/10.22331/q-2021-12-02-595 10.22331/q-2021-12-02-595 |
| [13] | Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill. 2002. Topological quantum memory. J. Math. Phys., 43, 9 (2002), 4452-4505. https://doi.org/10.1063/1.1499754 10.1063/1.1499754 · Zbl 1060.94045 |
| [14] | Yotam Dikstein and Irit Dinur. 2019. Agreement testing theorems on layered set systems. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). 1495-1524. https://doi.org/10.1109/FOCS.2019.00088 10.1109/FOCS.2019.00088 |
| [15] | Yotam Dikstein, Irit Dinur, Yuval Filmus, and Prahladh Harsha. 2018. Boolean function analysis on high-dimensional expanders. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). · Zbl 1522.68739 |
| [16] | Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, and Shahar Mozes. 2021. Locally Testable Codes with constant rate, distance, and locality. arXiv preprint arXiv:2111.04808. |
| [17] | Irit Dinur, Yuval Filmus, Prahladh Harsha, and Madhur Tulsiani. 2020. Explicit SoS lower bounds from high-dimensional expanders. arXiv preprint arXiv:2009.05218. |
| [18] | Irit Dinur, Min-Hsiu Hsieh, Ting-Chun Lin, and Thomas Vidick. 2022. Good quantum LDPC codes with linear time decoders. arXiv preprint arXiv:2206.07750. |
| [19] | Irit Dinur and Tali Kaufman. 2017. High dimensional expanders imply agreement expanders. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). 974-985. https://doi.org/10.1109/FOCS.2017.94 10.1109/FOCS.2017.94 |
| [20] | Irit Dinur, Madhu Sudan, and Avi Wigderson. 2006. Robust local testability of tensor products of LDPC codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer, 304-315. https://doi.org/10.1007/11830924_29 10.1007/11830924_29 · Zbl 1155.94402 |
| [21] | Guillaume Duclos-Cianci and David Poulin. 2010. Fast Decoders for Topological Quantum Codes. Phys. Rev. Lett., 104 (2010), Feb, 050504. https://doi.org/10.1103/PhysRevLett.104.050504 10.1103/PhysRevLett.104.050504 · Zbl 1356.81116 |
| [22] | Shai Evra and Tali Kaufman. 2016. Bounded degree cosystolic expanders of every dimension. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing. 36-48. https://doi.org/10.1145/2897518.2897543 10.1145/2897518.2897543 · Zbl 1376.05095 |
| [23] | Shai Evra, Tali Kaufman, and Gilles Zémor. 2020. Decodable quantum LDPC codes beyond the square root distance barrier using high dimensional expanders. arXiv preprint arXiv:2004.07935. · Zbl 1498.81063 |
| [24] | Michael H Freedman, David A Meyer, and Feng Luo. 2002. Z2-systolic freedom and quantum codes. In Mathematics of quantum computation. Chapman and Hall/CRC, 303-338. |
| [25] | Oded Goldreich. 2010. Short locally testable codes and proofs: A survey in two parts. In Property testing. Springer, 65-104. https://doi.org/10.1007/978-3-642-16367-8_6 10.1007/978-3-642-16367-8_6 · Zbl 1309.68218 |
| [26] | Daniel Gottesman. 2013. Fault-tolerant quantum computation with constant overhead. arXiv preprint arXiv:1310.2984. |
| [27] | Mikhail Gromov. 2010. Singularities, expanders and topology of maps. Part 2: From combinatorics to topology via algebraic isoperimetry. Geometric and Functional Analysis, 20, 2 (2010), 416-526. https://doi.org/10.1007/s00039-010-0073-8 10.1007/s00039-010-0073-8 · Zbl 1251.05039 |
| [28] | Shouzhen Gu, Christopher A Pattison, and Eugene Tang. 2022. An efficient decoder for a linear distance quantum LDPC code. arXiv preprint arXiv:2206.06557. |
| [29] | Tom Gur, Noam Lifshitz, and Siqi Liu. 2021. Hypercontractivity on high dimensional expanders. arXiv preprint arXiv:2111.09375. |
| [30] | Matthew B Hastings, Jeongwan Haah, and Ryan O’Donnell. 2021. Fiber bundle codes: breaking the n 1/2 polylog (n) barrier for Quantum LDPC codes. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. 1276-1288. https://doi.org/10.1145/3406325.3451005 10.1145/3406325.3451005 · Zbl 07765248 |
| [31] | Allen Hatcher. 2002. Algebraic Topology. Cambridge University Press. · Zbl 1044.55001 |
| [32] | Shlomo Hoory, Nathan Linial, and Avi Wigderson. 2006. Expander graphs and their applications. Bull. Amer. Math. Soc., 43, 4 (2006), 439-561. · Zbl 1147.68608 |
| [33] | Max Hopkins and Ting-Chun Lin. 2022. Explicit Lower Bounds Against Ω (n)-Rounds of Sum-of-Squares. arXiv preprint arXiv:2204.11469. |
| [34] | Fernando Granha Jeronimo, Shashank Srivastava, and Madhur Tulsiani. 2021. Near-linear time decoding of Ta-Shma’s codes via splittable regularity. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. 1527-1536. https://doi.org/10.1145/3406325.3451126 10.1145/3406325.3451126 · Zbl 07765267 |
| [35] | Gleb Kalachev and Pavel Panteleev. 2022. Two-sided Robustly Testable Codes. arXiv preprint arXiv:2206.09973. |
| [36] | Tali Kaufman, David Kazhdan, and Alexander Lubotzky. 2014. Ramanujan complexes and bounded degree topological expanders. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. 484-493. https://doi.org/10.1109/FOCS.2014.58 10.1109/FOCS.2014.58 · Zbl 1339.05075 |
| [37] | Tali Kaufman and Izhar Oppenheim. 2020. High order random walks: Beyond spectral gap. Combinatorica, 1-37. https://doi.org/10.1007/s00493-019-3847-0 10.1007/s00493-019-3847-0 · Zbl 1463.05543 |
| [38] | Tali Kaufman and Ran J Tessler. 2020. New Cosystolic Expanders from Tensors Imply Explicit Quantum LDPC Codes with Ω (√ n olog^k n) Distance. arXiv preprint arXiv:2008.09495. |
| [39] | A Yu Kitaev. 2003. Fault-tolerant quantum computation by anyons. Annals of Physics, 303, 1 (2003), 2-30. https://doi.org/10.1016/S0003-4916(02)00018-0 10.1016/S0003-4916(02)00018-0 · Zbl 1012.81006 |
| [40] | Anthony Leverrier, Vivien Londe, and Gilles Zémor. 2022. Towards local testability for quantum coding. Quantum, 6 (2022), 661. https://doi.org/10.22331/q-2022-02-24-661 10.22331/q-2022-02-24-661 |
| [41] | Anthony Leverrier, Jean-Pierre Tillich, and Gilles Zémor. 2015. Quantum expander codes. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. 810-824. https://doi.org/10.1109/FOCS.2015.55 10.1109/FOCS.2015.55 |
| [42] | Anthony Leverrier and Gilles Zémor. 2022. Efficient decoding up to a constant fraction of the code length for asymptotically good quantum codes. arXiv preprint arXiv:2206.07571. |
| [43] | Anthony Leverrier and Gilles Zémor. 2022. A parallel decoder for good quantum LDPC codes. arXiv preprint arXiv:2208.05537. |
| [44] | Anthony Leverrier and Gilles Zémor. 2022. Quantum Tanner codes. arXiv preprint arXiv:2202.13641. |
| [45] | Ting-Chun Lin and Min-Hsiu Hsieh. 2022. c^3-Local Testable Codes from Lossless Expanders. arXiv preprint arXiv:2201.11369. |
| [46] | Ting-Chun Lin and Min-Hsiu Hsieh. 2022. Good quantum LDPC codes with linear time decoder from lossless expanders. arXiv preprint arXiv:2203.03581. |
| [47] | Nathan Linial* and Roy Meshulam*. 2006. Homological connectivity of random 2-complexes. Combinatorica, 26, 4 (2006), 475-487. https://doi.org/10.1007/s00493-006-0027-9 10.1007/s00493-006-0027-9 · Zbl 1121.55013 |
| [48] | Alexander Lubotzky. 2014. Ramanujan complexes and high dimensional expanders. Japanese Journal of Mathematics, 9, 2 (2014), 137-169. https://doi.org/10.1007/s11537-014-1265-z 10.1007/s11537-014-1265-z · Zbl 1302.05095 |
| [49] | Pavel Panteleev and Gleb Kalachev. 2019. Degenerate Quantum LDPC Codes With Good Finite Length Performance. arxiv:1904.02703. · Zbl 1489.94162 |
| [50] | Pavel Panteleev and Gleb Kalachev. 2021. Asymptotically Good Quantum and Locally Testable Classical LDPC Codes. arXiv preprint arXiv:2111.03654. · Zbl 1489.94162 |
| [51] | Pavel Panteleev and Gleb Kalachev. 2022. Quantum LDPC codes with almost linear minimum distance. IEEE Transactions on Information Theory, 68, 1 (2022), 213-229. https://doi.org/10.1109/TIT.2021.3119384 10.1109/TIT.2021.3119384 · Zbl 1489.94162 |
| [52] | A Philips, R Lubotsky, and P Sarnak. 1988. Ramanujan graphs. Combinatorica, 8, 3 (1988), 261-277. https://doi.org/10.1007/BF02126799 10.1007/BF02126799 · Zbl 0661.05035 |
| [53] | Michael Sipser and Daniel A Spielman. 1996. Expander codes. IEEE transactions on Information Theory, 42, 6 (1996), 1710-1722. https://doi.org/10.1109/18.556667 10.1109/18.556667 · Zbl 0943.94543 |
| [54] | R Tanner. 1981. A recursive approach to low complexity codes. IEEE Transactions on information theory, 27, 5 (1981), 533-547. https://doi.org/10.1109/TIT.1981.1056404 10.1109/TIT.1981.1056404 · Zbl 0474.94029 |
| [55] | Jean-Pierre Tillich and Gilles Zémor. 2013. Quantum LDPC codes with positive rate and minimum distance proportional to the square root of the blocklength. IEEE Transactions on Information Theory, 60, 2 (2013), 1193-1202. https://doi.org/10.1109/TIT.2013.2292061 10.1109/TIT.2013.2292061 · Zbl 1364.94630 |
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.
