Connectivity constrains quantum codes

Nouédyn Baspin1 and Anirudh Krishna2

1Université de Sherbrooke, Sherbrooke, Québec, Canada J1K 2R1
2Stanford University, Stanford, CA, USA, 94305

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Quantum low-density parity-check (LDPC) codes are an important class of quantum error correcting codes. In such codes, each qubit only affects a constant number of syndrome bits, and each syndrome bit only relies on some constant number of qubits. Constructing quantum LDPC codes is challenging. It is an open problem to understand if there exist good quantum LDPC codes, i.e. with constant rate and relative distance. Furthermore, techniques to perform fault-tolerant gates are poorly understood. We present a unified way to address these problems. Our main results are a) a bound on the distance, b) a bound on the code dimension and c) limitations on certain fault-tolerant gates that can be applied to quantum LDPC codes. All three of these bounds are cast as a function of the graph separator of the connectivity graph representation of the quantum code. We find that unless the connectivity graph contains an expander, the code is severely limited. This implies a necessary, but not sufficient, condition to construct good codes. This is the first bound that studies the limitations of quantum LDPC codes that does not rely on locality. As an application, we present novel bounds on quantum LDPC codes associated with local graphs in $D$-dimensional hyperbolic space.

► BibTeX data

► References

[1] S. Aaronson and D. Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70 (5): 052328, 2004. 10.1103/​PhysRevA.70.052328.
https:/​/​doi.org/​10.1103/​PhysRevA.70.052328

[2] I. Abraham, Y. Bartal, T.-H. Chan, K. Dhamdhere, A. Gupta, J. Kleinberg, O. Neiman, and A. Slivkins. Metric embeddings with relaxed guarantees. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05). IEEE, 2005. 10.1109/​sfcs.2005.51.
https:/​/​doi.org/​10.1109/​sfcs.2005.51

[3] I. Abraham, Y. Bartal, and O. Neiman. Nearly tight low stretch spanning trees. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science. IEEE, Oct. 2008. 10.1109/​focs.2008.62.
https:/​/​doi.org/​10.1109/​focs.2008.62

[4] I. Abraham, Y. Bartal, and O. Neiman. On low dimensional local embeddings. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Jan. 2009. 10.1137/​1.9781611973068.95.
https:/​/​doi.org/​10.1137/​1.9781611973068.95

[5] I. Abraham, A. Filtser, A. Gupta, and O. Neiman. Metric embedding via shortest path decompositions. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. ACM, June 2018. 10.1145/​3188745.3188808.
https:/​/​doi.org/​10.1145/​3188745.3188808

[6] D. Aharonov and M. Ben-Or. Fault-tolerant quantum computation with constant error. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 176–188. ACM, 1997. 10.1137/​S0097539799359385.
https:/​/​doi.org/​10.1137/​S0097539799359385

[7] L. Aleksandrov and H. Djidjev. Linear algorithms for partitioning embedded graphs of bounded genus. SIAM Journal on Discrete Mathematics, 9 (1): 129–150, Feb. 1996. 10.1137/​s0895480194272183.
https:/​/​doi.org/​10.1137/​s0895480194272183

[8] P. Aliferis, D. Gottesman, and J. Preskill. Quantum accuracy threshold for concatenated distance-3 codes. 2005. 10.48550/​ARXIV.QUANT-PH/​0504218.
https:/​/​doi.org/​10.48550/​ARXIV.QUANT-PH/​0504218

[9] I. Althöfer, G. Das, D. Dobkin, D. Joseph, and J. Soares. On sparse spanners of weighted graphs. Discrete & Computational Geometry, 9 (1): 81–100, Jan. 1993. 10.1007/​bf02189308.
https:/​/​doi.org/​10.1007/​bf02189308

[10] A. Ashikhmin and S. Litsyn. Upper bounds on the size of quantum codes. IEEE Transactions on Information Theory, 45 (4): 1206–1215, 1999. 10.1109/​18.761270.
https:/​/​doi.org/​10.1109/​18.761270

[11] N. Bansal, U. Feige, R. Krauthgamer, K. Makarychev, V. Nagarajan, J. Seffi, and R. Schwartz. Min-max graph partitioning and small set expansion. SIAM Journal on Computing, 43 (2): 872–904, Jan. 2014. 10.1137/​120873996.
https:/​/​doi.org/​10.1137/​120873996

[12] J. Barát, J. Matoušek, and D. R. Wood. Bounded-degree graphs have arbitrarily large geometric thickness. The Electronic Journal of Combinatorics, 13 (1), Jan. 2006. 10.37236/​1029.
https:/​/​doi.org/​10.37236/​1029

[13] J. Batson, D. A. Spielman, N. Srivastava, and S.-H. Teng. Spectral sparsification of graphs. Communications of the ACM, 56 (8): 87–94, Aug. 2013. 10.1145/​2492007.2492029.
https:/​/​doi.org/​10.1145/​2492007.2492029

[14] I. Benjamini, O. Schramm, and Á. Timár. On the separation profile of infinite graphs. Groups, Geometry, and Dynamics, 6 (4): 639–658, 2012. 10.4171/​ggd/​168.
https:/​/​doi.org/​10.4171/​ggd/​168

[15] H. Bombin. Topological order with a twist: Ising anyons from an abelian model. Physical Review Letters, 105 (3): 030403, 2010. 10.1103/​PhysRevLett.105.030403.
https:/​/​doi.org/​10.1103/​PhysRevLett.105.030403

[16] H. Bombin and M. A. Martin-Delgado. Topological quantum distillation. Physical Review Letters, 97 (18): 180501, 2006. 10.1103/​PhysRevLett.97.180501.
https:/​/​doi.org/​10.1103/​PhysRevLett.97.180501

[17] J. Böttcher, K. P. Pruessmann, A. Taraz, and A. Würfl. Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs. European Journal of Combinatorics, 31 (5): 1217–1227, 2010. 10.1016/​j.ejc.2009.10.010.
https:/​/​doi.org/​10.1016/​j.ejc.2009.10.010

[18] S. Bravyi and M. B. Hastings. Homological product codes. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 273–282, 2014. 10.1145/​2591796.2591870.
https:/​/​doi.org/​10.1145/​2591796.2591870

[19] S. Bravyi and A. Y. Kitaev. Quantum codes on a lattice with boundary. arXiv preprint quant-ph/​9811052, 1998. 10.48550/​arXiv.quant-ph/​9811052.
https:/​/​doi.org/​10.48550/​arXiv.quant-ph/​9811052
arXiv:quant-ph/9811052

[20] S. Bravyi and R. König. Classification of topologically protected gates for local stabilizer codes. Physical Review Letters, 110 (17): 170503, 2013. 10.1103/​PhysRevLett.110.170503.
https:/​/​doi.org/​10.1103/​PhysRevLett.110.170503

[21] S. Bravyi and B. Terhal. A no-go theorem for a two-dimensional self-correcting quantum memory based on stabilizer codes. New Journal of Physics, 11 (4): 043029, 2009. 10.1088/​1367-2630/​11/​4/​043029.
https:/​/​doi.org/​10.1088/​1367-2630/​11/​4/​043029

[22] S. Bravyi, D. Poulin, and B. Terhal. Tradeoffs for reliable quantum information storage in 2D systems. Physical Review Letters, 104 (5): 050503, 2010. 10.1103/​PhysRevLett.104.050503.
https:/​/​doi.org/​10.1103/​PhysRevLett.104.050503

[23] N. P. Breuckmann and J. N. Eberhardt. Balanced product quantum codes. IEEE Transactions on Information Theory, pages 1–1, 2021a. 10.1109/​TIT.2021.3097347.
https:/​/​doi.org/​10.1109/​TIT.2021.3097347

[24] N. P. Breuckmann and J. N. Eberhardt. Quantum low-density parity-check codes. PRX Quantum, 2 (4), oct 2021b. 10.1103/​prxquantum.2.040101.
https:/​/​doi.org/​10.1103/​prxquantum.2.040101

[25] N. P. Breuckmann and V. Londe. Single-shot decoding of linear rate ldpc quantum codes with high performance. 2020. 10.48550/​ARXIV.2001.03568.
https:/​/​doi.org/​10.48550/​ARXIV.2001.03568

[26] N. P. Breuckmann and B. M. Terhal. Constructions and noise threshold of hyperbolic surface codes. IEEE transactions on Information Theory, 62 (6): 3731–3744, 2016. 10.1109/​TIT.2016.2555700.
https:/​/​doi.org/​10.1109/​TIT.2016.2555700

[27] S. Burton and D. Browne. Limitations on transversal gates for hypergraph product codes. 2020. 10.48550/​ARXIV.2012.05842.
https:/​/​doi.org/​10.48550/​ARXIV.2012.05842

[28] C. Chekuri and J. Chuzhoy. Degree-3 treewidth sparsifiers. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Dec. 2014. 10.1137/​1.9781611973730.19.
https:/​/​doi.org/​10.1137/​1.9781611973730.19

[29] N. Delfosse. Tradeoffs for reliable quantum information storage in surface codes and color codes. In Information Theory Proceedings (ISIT), 2013 IEEE International Symposium on, pages 917–921. IEEE, 2013. 10.1109/​ISIT.2013.6620360.
https:/​/​doi.org/​10.1109/​ISIT.2013.6620360

[30] N. Delfosse and G. Zémor. Upper bounds on the rate of low density stabilizer codes for the quantum erasure channel. 2012. 10.48550/​ARXIV.1205.7036.
https:/​/​doi.org/​10.48550/​ARXIV.1205.7036

[31] H. Dell, C. Komusiewicz, N. Talmon, and M. Weller. The PACE 2017 Parameterized Algorithms and Computational Experiments Challenge: The Second Iteration. In D. Lokshtanov and N. Nishimura, editors, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017), volume 89 of Leibniz International Proceedings in Informatics (LIPIcs), pages 30:1–30:12, Dagstuhl, Germany, 2018. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. ISBN 978-3-95977-051-4. 10.4230/​LIPIcs.IPEC.2017.30. URL http:/​/​drops.dagstuhl.de/​opus/​volltexte/​2018/​8558.
https:/​/​doi.org/​10.4230/​LIPIcs.IPEC.2017.30
http:/​/​drops.dagstuhl.de/​opus/​volltexte/​2018/​8558

[32] H. N. Djidjev and S. M. Venkatesan. Planarization of graphs embedded on surfaces. In Graph-Theoretic Concepts in Computer Science, pages 62–72. Springer Berlin Heidelberg, 1995. 10.1007/​3-540-60618-1_66.
https:/​/​doi.org/​10.1007/​3-540-60618-1_66

[33] V. Dujmović, D. Eppstein, and D. R. Wood. Genus, treewidth, and local crossing number. In International Symposium on Graph Drawing, pages 87–98. Springer, 2015. 10.1007/​978-3-319-27261-0_8.
https:/​/​doi.org/​10.1007/​978-3-319-27261-0_8

[34] V. Dujmovic, A. Sidiropoulos, and D. R. Wood. Layouts of expander graphs. Chicago Journal of Theoretical Computer Science, 22 (1): 1–21, 2016. 10.4086/​cjtcs.2016.001.
https:/​/​doi.org/​10.4086/​cjtcs.2016.001

[35] Z. Dvořák and S. Norin. Treewidth of graphs with balanced separations. Journal of Combinatorial Theory, Series B, 137: 137–144, July 2019. 10.1016/​j.jctb.2018.12.007.
https:/​/​doi.org/​10.1016/​j.jctb.2018.12.007

[36] L. Eldar, M. Ozols, and K. Thompson. The need for structure in quantum LDPC codes. IEEE Transactions on Information Theory, 66 (3): 1460–1473, 2020. 10.1109/​TIT.2019.2952366.
https:/​/​doi.org/​10.1109/​TIT.2019.2952366

[37] S. Evra, T. Kaufman, and G. Zémor. Decodable quantum LDPC codes beyond the square root distance barrier using high dimensional expanders. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 218–227. IEEE, 2020. 10.1109/​FOCS46700.2020.00029.
https:/​/​doi.org/​10.1109/​FOCS46700.2020.00029

[38] O. Fawzi, A. Grospellier, and A. Leverrier. Efficient decoding of random errors for quantum expander codes. 2017. 10.48550/​ARXIV.1711.08351.
https:/​/​doi.org/​10.48550/​ARXIV.1711.08351

[39] O. Fawzi, A. Grospellier, and A. Leverrier. Constant overhead quantum fault-tolerance with quantum expander codes. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 743–754. IEEE, 2018. 10.1109/​FOCS.2018.00076.
https:/​/​doi.org/​10.1109/​FOCS.2018.00076

[40] G. N. Federickson. Fast algorithms for shortest paths in planar graphs, with applications. SIAM Journal on Computing, 16 (6): 1004–1022, Dec. 1987. 10.1137/​0216064.
https:/​/​doi.org/​10.1137/​0216064

[41] M. H. Freedman, D. A. Meyer, and F. Luo. Z2-systolic freedom and quantum codes. Mathematics of quantum computation, Chapman & Hall/​CRC, pages 287–320, 2002.

[42] J. R. Gilbert, J. P. Hutchinson, and R. E. Tarjan. A separator theorem for graphs of bounded genus. Journal of Algorithms, 5 (3): 391–407, Sept. 1984. 10.1016/​0196-6774(84)90019-1.
https:/​/​doi.org/​10.1016/​0196-6774(84)90019-1

[43] V. Gladkova and V. Shum. Separation profiles of graphs of fractals. Journal of Topology and Analysis, pages 1–13, Jan. 2020. 10.1142/​s1793525320500417.
https:/​/​doi.org/​10.1142/​s1793525320500417

[44] D. Gottesman. Class of quantum error-correcting codes saturating the quantum Hamming bound. Physical Review A, 54 (3): 1862, 1996. 10.1103/​PhysRevA.54.1862.
https:/​/​doi.org/​10.1103/​PhysRevA.54.1862

[45] D. Gottesman. Stabilizer codes and quantum error correction. 1997. 10.48550/​ARXIV.QUANT-PH/​9705052.
https:/​/​doi.org/​10.48550/​ARXIV.QUANT-PH/​9705052

[46] D. Gottesman. Fault-tolerant quantum computation with constant overhead. Quantum Information & Computation, 14 (15-16): 1338–1372, 2014. 10.5555/​2685179.2685184.
https:/​/​doi.org/​10.5555/​2685179.2685184

[47] D. Gottesman and I. L. Chuang. Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations. Nature, 402 (6760): 390–393, Nov. 1999. 10.1038/​46503.
https:/​/​doi.org/​10.1038/​46503

[48] M. Grohe and D. Marx. On tree width, bramble size, and expansion. Journal of Combinatorial Theory, Series B, 99 (1): 218–228, 2009. ISSN 0095-8956. 10.1016/​j.jctb.2008.06.004.
https:/​/​doi.org/​10.1016/​j.jctb.2008.06.004

[49] L. Guth and A. Lubotzky. Quantum error correcting codes and 4-dimensional arithmetic hyperbolic manifolds. Journal of Mathematical Physics, 55 (8): 082202, 2014. 10.1063/​1.4891487.
https:/​/​doi.org/​10.1063/​1.4891487

[50] M. B. Hastings. Decoding in hyperbolic spaces: Ldpc codes with linear rate and efficient error correction. 2013. 10.48550/​ARXIV.1312.2546.
https:/​/​doi.org/​10.48550/​ARXIV.1312.2546

[51] M. B. Hastings, J. Haah, and R. O'Donnell. Fiber bundle codes: Breaking the $n^{1/​2}$poly$\log(n)$ barrier for quantum LDPC codes. page 1276–1288, 2021. 10.1145/​3406325.3451005.
https:/​/​doi.org/​10.1145/​3406325.3451005

[52] M. R. Henzinger, P. Klein, S. Rao, and S. Subramanian. Faster shortest-path algorithms for planar graphs. Journal of Computer and System Sciences, 55 (1): 3–23, Aug. 1997. 10.1006/​jcss.1997.1493.
https:/​/​doi.org/​10.1006/​jcss.1997.1493

[53] D. Hume. A continuum of expanders. Fundamenta Mathematicae, 238 (2): 143–152, 2017. 10.4064/​fm101-11-2016.
https:/​/​doi.org/​10.4064/​fm101-11-2016

[54] D. Hume, J. Mackay, and R. Tessera. Poincaré profiles of groups and spaces. Revista Matemática Iberoamericana, 36 (6): 1835–1886, Mar. 2020. 10.4171/​rmi/​1184.
https:/​/​doi.org/​10.4171/​rmi/​1184

[55] W. R. Inc. Mathematica, Version 12.3.1. Champaign, IL, 2021.

[56] T. Kaufman and R. J. Tessler. New cosystolic expanders from tensors imply explicit quantum LDPC codes with $\Omega(\sqrt{n}\log^{k}n)$ distance. page 1317–1329, 2021. 10.1145/​3406325.3451029.
https:/​/​doi.org/​10.1145/​3406325.3451029

[57] T. Kaufman, D. Kazhdan, and A. Lubotzky. Ramanujan complexes and bounded degree topological expanders. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 484–493. IEEE, 2014. 10.1109/​FOCS.2014.58.
https:/​/​doi.org/​10.1109/​FOCS.2014.58

[58] K.-i. Kawarabayashi and B. Reed. A separator theorem in minor-closed classes. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 153–162, 2010. 10.1109/​FOCS.2010.22.
https:/​/​doi.org/​10.1109/​FOCS.2010.22

[59] J. A. Kelner. Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus. SIAM Journal on Computing, 35 (4): 882–902, Jan. 2006. 10.1137/​s0097539705447244.
https:/​/​doi.org/​10.1137/​s0097539705447244

[60] S. Kisfaludi-Bak. Hyperbolic intersection graphs and (quasi)-polynomial time. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1621–1638. SIAM, 2020. 10.1137/​1.9781611975994.100.
https:/​/​doi.org/​10.1137/​1.9781611975994.100

[61] A. Kitaev. Fault-tolerant quantum computation by anyons. Annals of Physics, 303 (1): 2–30, jan 2003. 10.1016/​s0003-4916(02)00018-0.
https:/​/​doi.org/​10.1016/​s0003-4916(02)00018-0

[62] A. Y. Kitaev. Quantum computations: algorithms and error correction. Russian Mathematical Surveys, 52 (6): 1191–1249, dec 1997. 10.1070/​rm1997v052n06abeh002155.
https:/​/​doi.org/​10.1070/​rm1997v052n06abeh002155

[63] E. Knill and R. Laflamme. Theory of quantum error-correcting codes. Phys. Rev. A, 55: 900–911, Feb 1997. 10.1103/​PhysRevA.55.900. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevA.55.900.
https:/​/​doi.org/​10.1103/​PhysRevA.55.900

[64] E. Knill, R. Laflamme, and W. H. Zurek. Resilient quantum computation: error models and thresholds. In Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, volume 454, pages 365–384. The Royal Society, 1998. 10.1126/​science.279.5349.342.
https:/​/​doi.org/​10.1126/​science.279.5349.342

[65] A. A. Kovalev and L. P. Pryadko. Improved quantum hypergraph-product LDPC codes. In Information Theory Proceedings (ISIT), 2012 IEEE International Symposium on, pages 348–352. IEEE, 2012. 10.1109/​ISIT.2012.6284206.
https:/​/​doi.org/​10.1109/​ISIT.2012.6284206

[66] A. A. Kovalev and L. P. Pryadko. Fault tolerance of quantum low-density parity check codes with sublinear distance scaling. Physical Review A, 87 (2): 020304, 2013. 10.1103/​PhysRevA.87.020304.
https:/​/​doi.org/​10.1103/​PhysRevA.87.020304

[67] C. Le Coz. Separation and Poincaré profiles. Theses, Université Paris-Saclay, Sept. 2020.

[68] A. Leverrier, S. Apers, and C. Vuillot. Quantum XYZ product codes. arXiv preprint arXiv:2011.09746, 2020. 10.48550/​ARXIV.2011.09746.
https:/​/​doi.org/​10.48550/​ARXIV.2011.09746
arXiv:2011.09746

[69] R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36 (2): 177–189, 1979. 10.1137/​0136016.
https:/​/​doi.org/​10.1137/​0136016

[70] V. Londe and A. Leverrier. Golden codes: quantum LDPC codes from regular tessellations of hyperbolic 4-manifolds. Quantum Inf. Comput., 19 (5&6): 361–391, may 2019. 10.26421/​QIC19.5-6-1.
https:/​/​doi.org/​10.26421/​QIC19.5-6-1

[71] A. Matsubayashi. Separator-based graph embedding into multidimensional grids with small edge-congestion. Discrete Applied Mathematics, 185: 119–137, Apr. 2015. 10.1016/​j.dam.2014.11.024.
https:/​/​doi.org/​10.1016/​j.dam.2014.11.024

[72] G. L. Miller, S.-H. Teng, W. Thurston, and S. A. Vavasis. Separators for sphere-packings and nearest neighbor graphs. Journal of the ACM (JACM), 44 (1): 1–29, 1997. 10.1145/​256292.256294.
https:/​/​doi.org/​10.1145/​256292.256294

[73] M. A. Nielsen and I. Chuang. Quantum computation and quantum information. 2002. 10.1038/​46503.
https:/​/​doi.org/​10.1038/​46503

[74] L. Orecchia, S. Sachdeva, and N. K. Vishnoi. Approximating the exponential, the lanczos method and an $\widetilde{O}(m)$-time spectral algorithm for balanced separator. In Proceedings of the 44th symposium on Theory of Computing - STOC'12. ACM Press, 2012. 10.1145/​2213977.2214080.
https:/​/​doi.org/​10.1145/​2213977.2214080

[75] P. Panteleev and G. Kalachev. Quantum LDPC codes with almost linear minimum distance. IEEE Transactions on Information Theory, 68 (1): 213–229, jan 2022. 10.1109/​tit.2021.3119384.
https:/​/​doi.org/​10.1109/​tit.2021.3119384

[76] F. Pastawski and B. Yoshida. Fault-tolerant logical gates in quantum error-correcting codes. Physical Review A, 91 (1), Jan 2015. ISSN 1094-1622. 10.1103/​physreva.91.012305. URL http:/​/​dx.doi.org/​10.1103/​PhysRevA.91.012305.
https:/​/​doi.org/​10.1103/​physreva.91.012305

[77] P. Sarvepalli and A. Klappenecker. Degenerate quantum codes and the quantum Hamming bound. Physical Review A, 81 (3): 032318, 2010. 10.1103/​PhysRevA.81.032318.
https:/​/​doi.org/​10.1103/​PhysRevA.81.032318

[78] P. W. Shor. Fault-tolerant quantum computation. In Proceedings of 37th Conference on Foundations of Computer Science, pages 56–65. IEEE, 1996. 10.1109/​SFCS.1996.548464.
https:/​/​doi.org/​10.1109/​SFCS.1996.548464

[79] A. Sidiropoulos, D. Wang, and Y. Wang. Metric embeddings with outliers. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Jan. 2017. 10.1137/​1.9781611974782.43.
https:/​/​doi.org/​10.1137/​1.9781611974782.43

[80] M. Sipser and D. Spielman. Expander codes. IEEE Transactions on Information Theory, 42 (6): 1710–1722, 1996. 10.1109/​18.556667.
https:/​/​doi.org/​10.1109/​18.556667

[81] D. A. Spielman. Spectral graph theory and its applications. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07). IEEE, Oct. 2007. 10.1109/​focs.2007.56.
https:/​/​doi.org/​10.1109/​focs.2007.56

[82] D. A. Spielman and S.-H. Teng. Spectral partitioning works: planar graphs and finite element meshes. In Proceedings of 37th Conference on Foundations of Computer Science. IEEE, 1996. 10.1109/​sfcs.1996.548468.
https:/​/​doi.org/​10.1109/​sfcs.1996.548468

[83] S. Teng. Points, Spheres, and Separators, A Unified Geometric Approach to Graph Partitioning. PhD thesis, Carnegie Mellon University, Pittsburgh, August 1991. CMU CS Tech Report CMU-CS-91-184.

[84] S. Teng, G. Miller, and S. Vavasis. A unified geometric approach to graph separators. In 1991 Proceedings 32nd Annual Symposium of Foundations of Computer Science, pages 538–547, Los Alamitos, CA, USA, oct 1991. IEEE Computer Society. 10.1109/​SFCS.1991.185417.
https:/​/​doi.org/​10.1109/​SFCS.1991.185417

[85] S.-H. Teng. Combinatorial aspects of geometric graphs. Computational Geometry, 9 (4): 277–287, 1998. ISSN 0925-7721. 10.1016/​S0925-7721(96)00008-9.
https:/​/​doi.org/​10.1016/​S0925-7721(96)00008-9

[86] J.-P. Tillich and G. Zémor. Quantum LDPC codes with positive rate and minimum distance proportional to the square root of the blocklength. IEEE Transactions on Information Theory, 60 (2): 1193–1202, 2014. 10.1109/​TIT.2013.2292061.
https:/​/​doi.org/​10.1109/​TIT.2013.2292061

[87] G. Zémor. On expander codes. IEEE Transactions on Information Theory, 47 (2): 835–837, 2001. 10.1109/​18.910593.
https:/​/​doi.org/​10.1109/​18.910593

[88] W. Zeng and L. P. Pryadko. Higher-dimensional quantum hypergraph-product codes with finite rates. Physical Review Letters, 122 (23): 230501, 2019. 10.1103/​PhysRevLett.122.230501.
https:/​/​doi.org/​10.1103/​PhysRevLett.122.230501

Cited by

[1] Lawrence Z. Cohen, Isaac H. Kim, Stephen D. Bartlett, and Benjamin J. Brown, "Low-overhead fault-tolerant quantum computing using long-range connectivity", arXiv:2110.10794, Science Advances 8 20, eabn1717 (2022).

[2] Nouédyn Baspin and Anirudh Krishna, "Quantifying Nonlocality: How Outperforming Local Quantum Codes Is Expensive", Physical Review Letters 129 5, 050505 (2022).

[3] Joshua Ramette, Josiah Sinclair, Zachary Vendeiro, Alyssa Rudelis, Marko Cetina, and Vladan Vuletić, "Any-To-Any Connected Cavity-Mediated Architecture for Quantum Computing with Trapped Ions or Rydberg Arrays", PRX Quantum 3 1, 010344 (2022).

[4] Terry Farrelly, David K. Tuckett, and Thomas M. Stace, "Local tensor-network codes", New Journal of Physics 24 4, 043015 (2022).

[5] Joschka Roffe, Lawrence Z. Cohen, Armanda O. Quintivalle, Daryus Chandra, and Earl T. Campbell, "Bias-tailored quantum LDPC codes", arXiv:2202.01702.

[6] Nicolas Delfosse, Michael E. Beverland, and Maxime A. Tremblay, "Bounds on stabilizer measurement circuits and obstructions to local implementations of quantum LDPC codes", arXiv:2109.14599.

[7] Gleb Kalachev and Sergey Sadov, "On the Cleaning Lemma of Quantum Coding Theory", arXiv:2204.04699.

The above citations are from Crossref's cited-by service (last updated successfully 2022-10-04 09:40:16) and SAO/NASA ADS (last updated successfully 2022-10-04 09:40:17). The list may be incomplete as not all publishers provide suitable and complete citation data.