Fiber bundle codes: breaking the \(N^{1/2}\mathrm{polylog}(N)\) barrier for quantum LDPC codes. (English) Zbl 07765248
Khuller, Samir (ed.) et al., Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, STOC ’21, virtual, Italy, June 21–25, 2021. New York, NY: Association for Computing Machinery (ACM). 1276-1288 (2021).
MSC:
| 68Qxx | Theory of computing |
References:
| [1] | Noga Alon and Fan R. K. Chung. 1988. Explicit construction of linear sized tolerant networks. Discrete Math., 72, 1-3, 1988. Pages 15-19. issn:0012-365X https://doi.org/10.1016/0012-365X(88)90189-6 · Zbl 0657.05068 · doi:10.1016/0012-365X(88)90189-6 |
| [2] | Noga Alon and Yuval Roichman. 1994. Random Cayley graphs and expanders. Random Structures Algorithms, 5, 2, 1994. Pages 271-284. · Zbl 0798.05048 · doi:1042-9832 |
| [3] | Dave Bacon, Steven T. Flammia, Aram W. Harrow, and Jonathan Shi. 2017. Sparse Quantum Codes from Quantum Circuits. IEEE Transactions on Information Theory, 63, 2017. Pages 2464-2479. · Zbl 1366.81187 · doi:10.1109/TIT.2017.2663199 |
| [4] | Leonid Bassalygo. 1981. Asymptotically optimal switching circuits. Problems of Information Transmission, 17, 3, 1981. Pages 206-211. · Zbl 0486.94021 |
| [5] | Sergey Bravyi and Matthew B. Hastings. 2014. Homological product codes. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing. ACM, New York. Pages 273-282. · Zbl 1315.94143 |
| [6] | Fan R. K. Chung. 1979. On concentrators, superconcentrators, generalizers, and nonblocking networks. Bell System Tech. J., 58, 8, 1979. Pages 1765-1777. · Zbl 0415.94021 · doi:10.1002/j.1538-7305.1979.tb02972.x |
| [7] | Shai Evra, Tali Kaufman, and Gilles Zémor. 2020. Decodable quantum LDPC codes beyond the \sqrt n distance barrier using high dimensional expanders. |
| [8] | Michael H. Freedman and Matthew B. Hastings. 2014. Quantum systems on non-k-hyperfinite complexes: a generalization of classical statistical mechanics on expander graphs. Quantum Inf. Comput., 14, 1-2, 2014. Pages 144-180. issn:1533-7146 |
| [9] | Michael H. Freedman and David A. Meyer. 2001. Projective plane and planar quantum codes. Found. Comput. Math., 1, 3, 2001. Pages 325-332. · Zbl 0995.94037 · doi:10.1007/s102080010013 |
| [10] | Michael H. Freedman, David A. Meyer, and Feng Luo. 2002. Z_2-systolic freedom and quantum codes. In Mathematics of quantum computation. Chapman & Hall/CRC, Boca Raton, FL. Pages 287-320. · Zbl 1075.81508 |
| [11] | Matthew B. Hastings. 2017. Quantum codes from high-dimensional manifolds. In Proceedings of the 8th Annual Innovations in Theoretical Computer Science. LIPIcs. Leibniz Int. Proc. Inform.. 67, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern. Pages Art. No. 25, 26. · Zbl 1406.81020 |
| [12] | Matthew B. Hastings. 2017. Weight reduction for quantum codes. Quantum Inf. Comput., 17, 15-16, 2017. Pages 1307-1334. issn:1533-7146 |
| [13] | Tali Kaufman and Ran J. Tessler. 2020. Quantum LDPC codes with \Omega (\sqrt n\qopname \relax olog^k n) distance, for any k. |
| [14] | Alexei Yu.\spacefactor @m Kitaev. 2003. Fault-tolerant quantum computation by anyons. Ann. Physics, 303, 1, 2003. Pages 2-30. issn:0003-4916 https://doi.org/10.1016/S0003-4916(02)00018-0 · Zbl 1012.81006 · doi:10.1016/S0003-4916(02)00018-0 |
| [15] | Anthony Leverrier, Jean-Pierre Tillich, and Gilles Zémor. 2015. Quantum expander codes. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Soc., Los Alamitos, CA. Pages 810-824. · doi:10.1109/FOCS.2015.55 |
| [16] | Pavel Panteleev and Gleb Kalachev. 2019. Degenerate quantum LDPC codes with good finite length performance. |
| [17] | Pavel Panteleev and Gleb Kalachev. 2020. Quantum LDPC codes with almost linear minimum distance. |
| [18] | David Poulin. 2005. Stabilizer Formalism for Operator Quantum Error Correction. Phys. Rev. Lett., 95, 2005. Pages 230504. · doi:10.1103/PhysRevLett.95.230504 |
| [19] | Tom Richardson and Rüdiger Urbanke. 2008. Modern Coding Theory. Cambridge University Press. · Zbl 1188.94001 |
| [20] | Jean-Pierre Tillich and Gilles Zémor. 2014. Quantum LDPC codes with positive rate and minimum distance proportional to the square root of the blocklength. IEEE Trans. Inform. Theory, 60, 2, 2014. Pages 1193-1202. · Zbl 1364.94630 · doi:10.1109/TIT.2013.2292061 |
| [21] | Salil P. Vadhan. 2012. Pseudorandomness. Now. |
| [22] | Noga Alon and Fan R. K. Chung. 1988. Explicit construction of linear sized tolerant networks. Discrete Math., 72, 1-3, 1988. Pages 15-19. issn:0012-365X https://doi.org/10.1016/0012-365X(88)90189-6 · Zbl 0657.05068 · doi:10.1016/0012-365X(88)90189-6 |
| [23] | Noga Alon and Yuval Roichman. 1994. Random Cayley graphs and expanders. Random Structures Algorithms, 5, 2, 1994. Pages 271-284. · Zbl 0798.05048 · doi:1042-9832 |
| [24] | Dave Bacon, Steven T. Flammia, Aram W. Harrow, and Jonathan Shi. 2017. Sparse Quantum Codes from Quantum Circuits. IEEE Transactions on Information Theory, 63, 2017. Pages 2464-2479. · Zbl 1366.81187 · doi:10.1109/TIT.2017.2663199 |
| [25] | Leonid Bassalygo. 1981. Asymptotically optimal switching circuits. Problems of Information Transmission, 17, 3, 1981. Pages 206-211. · Zbl 0486.94021 |
| [26] | Sergey Bravyi and Matthew B. Hastings. 2014. Homological product codes. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing. ACM, New York. Pages 273-282. · Zbl 1315.94143 |
| [27] | Fan R. K. Chung. 1979. On concentrators, superconcentrators, generalizers, and nonblocking networks. Bell System Tech. J., 58, 8, 1979. Pages 1765-1777. · Zbl 0415.94021 · doi:10.1002/j.1538-7305.1979.tb02972.x |
| [28] | Shai Evra, Tali Kaufman, and Gilles Zémor. 2020. Decodable quantum LDPC codes beyond the \sqrt n distance barrier using high dimensional expanders. |
| [29] | Michael H. Freedman and Matthew B. Hastings. 2014. Quantum systems on non-k-hyperfinite complexes: a generalization of classical statistical mechanics on expander graphs. Quantum Inf. Comput., 14, 1-2, 2014. Pages 144-180. issn:1533-7146 |
| [30] | Michael H. Freedman and David A. Meyer. 2001. Projective plane and planar quantum codes. Found. Comput. Math., 1, 3, 2001. Pages 325-332. · Zbl 0995.94037 · doi:10.1007/s102080010013 |
| [31] | Michael H. Freedman, David A. Meyer, and Feng Luo. 2002. Z_2-systolic freedom and quantum codes. In Mathematics of quantum computation. Chapman & Hall/CRC, Boca Raton, FL. Pages 287-320. · Zbl 1075.81508 |
| [32] | Matthew B. Hastings. 2017. Quantum codes from high-dimensional manifolds. In Proceedings of the 8th Annual Innovations in Theoretical Computer Science. LIPIcs. Leibniz Int. Proc. Inform.. 67, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern. Pages Art. No. 25, 26. · Zbl 1406.81020 |
| [33] | Matthew B. Hastings. 2017. Weight reduction for quantum codes. Quantum Inf. Comput., 17, 15-16, 2017. Pages 1307-1334. issn:1533-7146 |
| [34] | Tali Kaufman and Ran J. Tessler. 2020. Quantum LDPC codes with \Omega (\sqrt n\qopname \relax olog^k n) distance, for any k. |
| [35] | Alexei Yu.\spacefactor @m Kitaev. 2003. Fault-tolerant quantum computation by anyons. Ann. Physics, 303, 1, 2003. Pages 2-30. issn:0003-4916 https://doi.org/10.1016/S0003-4916(02)00018-0 · Zbl 1012.81006 · doi:10.1016/S0003-4916(02)00018-0 |
| [36] | Anthony Leverrier, Jean-Pierre Tillich, and Gilles Zémor. 2015. Quantum expander codes. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Soc., Los Alamitos, CA. Pages 810-824. · doi:10.1109/FOCS.2015.55 |
| [37] | Pavel Panteleev and Gleb Kalachev. 2019. Degenerate quantum LDPC codes with good finite length performance. |
| [38] | Pavel Panteleev and Gleb Kalachev. 2020. Quantum LDPC codes with almost linear minimum distance. |
| [39] | David Poulin. 2005. Stabilizer Formalism for Operator Quantum Error Correction. Phys. Rev. Lett., 95, 2005. Pages 230504. · doi:10.1103/PhysRevLett.95.230504 |
| [40] | Tom Richardson and Rüdiger Urbanke. 2008. Modern Coding Theory. Cambridge University Press. · Zbl 1188.94001 |
| [41] | Jean-Pierre Tillich and Gilles Zémor. 2014. Quantum LDPC codes with positive rate and minimum distance proportional to the square root of the blocklength. IEEE Trans. Inform. Theory, 60, 2, 2014. Pages 1193-1202. · Zbl 1364.94630 · doi:10.1109/TIT.2013.2292061 |
| [42] | Salil P. Vadhan. 2012. Pseudorandomness. Now. |
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.
