Quantum XYZ Product Codes

Anthony Leverrier1, Simon Apers2, and Christophe Vuillot1

1Inria, France
2CNRS, IRIF, Université Paris Cité

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


We study a three-fold variant of the hypergraph product code construction, differing from the standard homological product of three classical codes. When instantiated with 3 classical LDPC codes, this "XYZ product" yields a non CSS quantum LDPC code which might display a large minimum distance. The simplest instance of this construction, corresponding to the product of 3 repetition codes, is a non CSS variant of the 3-dimensional toric code known as the Chamon code. The general construction was introduced in Denise Maurice's PhD thesis, but has remained poorly understood so far. The reason is that while hypergraph product codes can be analyzed with combinatorial tools, the XYZ product codes also depend crucially on the algebraic properties of the parity-check matrices of the three classical codes, making their analysis much more involved.
Our main motivation for studying XYZ product codes is that the natural representatives of logical operators are two-dimensional objects. This contrasts with standard hypergraph product codes in 3 dimensions which always admit one-dimensional logical operators. In particular, specific instances of XYZ product codes with constant rate might display a minimum distance as large as $\Theta(N^{2/3})$. While we do not prove this result here, we obtain the dimension of a large class of XYZ product codes, and when restricting to codes with dimension 1, we reduce the problem of computing the minimum distance to a more elementary combinatorial problem involving binary 3-tensors. We also discuss in detail some families of XYZ product codes that can be embedded in three dimensions with local interaction. Some of these codes seem to share properties with Haah's cubic codes and might be interesting candidates for self-correcting quantum memories with a logarithmic energy barrier.

► BibTeX data

► References

[1] Dorit Aharonov and Lior Eldar. Quantum locally testable codes. SIAM Journal on Computing, 44 (5): 1230–1262, 2015. 10.1137/​140975498.

[2] J Pablo Bonilla Ataides, David K Tuckett, Stephen D Bartlett, Steven T Flammia, and Benjamin J Brown. The XZZX surface code. Nature Communications, 12 (1): 1–12, 2021. 10.1038/​s41467-021-22274-1.

[3] Benjamin Audoux and Alain Couvreur. On tensor products of CSS Codes. Annales de l’Institut Henri Poincaré (D) Combinatorics, Physics and their Interactions, 6 (2): 239–287, 2019. 10.4171/​AIHPD/​71.

[4] H. Bombin and M. A. Martin-Delgado. Exact topological quantum order in $d=3$ and beyond: Branyons and brane-net condensates. Phys. Rev. B, 75: 075103, Feb 2007. 10.1103/​PhysRevB.75.075103.

[5] Sergey Bravyi and Matthew B Hastings. Homological product codes. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 273–282. ACM, 2014. 10.1145/​2591796.2591870.

[6] Sergey Bravyi and Barbara 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.

[7] Sergey Bravyi, Barbara M Terhal, and Bernhard Leemhuis. Majorana fermion codes. New Journal of Physics, 12 (8): 083039, 2010. 10.1088/​1367-2630/​12/​8/​083039.

[8] Sergey Bravyi, Bernhard Leemhuis, and Barbara M Terhal. Topological order in an exactly solvable 3D spin model. Annals of Physics, 326 (4): 839–866, 2011. 10.1016/​j.aop.2010.11.002.

[9] Nikolas P. Breuckmann and Jens N. Eberhardt. Balanced product quantum codes. IEEE Transactions on Information Theory, 67 (10): 6653–6674, 2021a. 10.1109/​TIT.2021.3097347.

[10] Nikolas P. Breuckmann and Jens Niklas Eberhardt. Quantum low-density parity-check codes. PRX Quantum, 2: 040101, Oct 2021b. 10.1103/​PRXQuantum.2.040101.

[11] Benjamin J Brown, Daniel Loss, Jiannis K Pachos, Chris N Self, and James R Wootton. Quantum memories at finite temperature. Reviews of Modern Physics, 88 (4): 045005, 2016. 10.1103/​RevModPhys.88.045005.

[12] A Robert Calderbank and Peter W Shor. Good quantum error-correcting codes exist. Physical Review A, 54 (2): 1098, 1996. 10.1103/​PhysRevA.54.1098.

[13] Earl T Campbell. A theory of single-shot error correction for adversarial noise. Quantum Science and Technology, 4 (2): 025006, feb 2019. 10.1088/​2058-9565/​aafc8f.

[14] Claudio Chamon. Quantum glassiness in strongly correlated clean systems: an example of topological overprotection. Physical Review Letters, 94 (4): 040402, 2005. 10.1103/​PhysRevLett.94.040402.

[15] Shai Evra, Tali Kaufman, and Gilles Zémor. Decodable quantum LDPC codes beyond the square root distance barrier using high dimensional expanders. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 218–227. IEEE, 2020. 10.1109/​FOCS46700.2020.00029.

[16] Omar Fawzi, Antoine Grospellier, and Anthony Leverrier. Constant overhead quantum fault-tolerance with quantum expander codes. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 743–754. IEEE Computer Society, 2018. 10.1109/​FOCS.2018.00076.

[17] Michael H Freedman and Matthew B Hastings. Quantum systems on non-$k$-hyperfinite complexes: a generalization of classical statistical mechanics on expander graphs. Quantum Information & Computation, 14 (1-2): 144–180, 2014.

[18] Michael H Freedman, David A Meyer, and Feng Luo. Z2-systolic freedom and quantum codes. Mathematics of quantum computation, Chapman & Hall/​CRC, pages 287–320, 2002.

[19] Feliks Ruvimovich Gantmacher. The theory of matrices, volume 131. American Mathematical Society, 1959.

[20] Daniel Gottesman. Stabilizer codes and quantum error correction. PhD thesis, California Institute of Technology, 1997.

[21] Jeongwan Haah. Local stabilizer codes in three dimensions without string logical operators. Physical Review A, 83 (4): 042330, 2011. 10.1103/​PhysRevA.83.042330.

[22] Mathew B Hastings. Weight reduction for quantum codes. Quantum Information & Computation, 17 (15-16): 1307–1334, 2017.

[23] Matthew B. Hastings, Jeongwan Haah, and Ryan O'Donnell. Fiber bundle codes: breaking the $n^{1/​2} polylog(n)$ barrier for quantum LDPC codes. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 1276–1288. ACM, 2021. 10.1145/​3406325.3451005. URL https:/​/​doi.org/​10.1145/​3406325.3451005.

[24] Tali Kaufman and Ran J. Tessler. New cosystolic expanders from tensors imply explicit Quantum LDPC codes with $\Omega(n \log^k n)$ distance. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 1317–1329. ACM, 2021. 10.1145/​3406325.3451029. URL https:/​/​doi.org/​10.1145/​3406325.3451029.

[25] Tali Kaufman, David Kazhdan, and Alexander Lubotzky. Isoperimetric inequalities for Ramanujan complexes and topological expanders. Geometric and Functional Analysis, 26 (1): 250–287, 2016. 10.1007/​s00039-016-0362-y.

[26] A Yu Kitaev. Fault-tolerant quantum computation by anyons. Annals of Physics, 303 (1): 2–30, 2003. 10.1016/​S0003-4916(02)00018-0.

[27] Alexey A Kovalev and Leonid P Pryadko. Quantum Kronecker sum-product low-density parity-check codes with finite rate. Physical Review A, 88 (1): 012311, 2013. 10.1103/​PhysRevA.88.012311.

[28] Anthony Leverrier, Jean-Pierre Tillich, and Gilles Zémor. Quantum expander codes. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 810–824. IEEE Computer Society, 2015. 10.1109/​FOCS.2015.55. URL https:/​/​doi.org/​10.1109/​FOCS.2015.55.

[29] Denise Maurice. Codes correcteurs quantiques pouvant se décoder itérativement. PhD thesis, Université Paris 6, 2014.

[30] Pavel Panteleev and Gleb Kalachev. Degenerate quantum LDPC codes with good finite length performance. Quantum, 5: 585, 2021a. 10.22331/​q-2021-11-22-585.

[31] Pavel Panteleev and Gleb Kalachev. Quantum LDPC codes with almost linear minimum distance. IEEE Transactions on Information Theory, 68 (1): 213–229, 2021b. 10.1109/​TIT.2021.3119384.

[32] Armanda O. Quintavalle, Michael Vasmer, Joschka Roffe, and Earl T. Campbell. Single-shot error correction of three-dimensional homological product codes. PRX Quantum, 2: 020340, 2021. 10.1103/​PRXQuantum.2.020340.

[33] Denis Serre. Matrices: Theory and Applications, volume 216. Springer Science & Business Media, 2002.

[34] Michael Sipser and Daniel A Spielman. Expander codes. IEEE transactions on Information Theory, 42 (6): 1710–1722, 1996. 10.1109/​18.556667.

[35] Andrew Steane. Multiple-particle interference and quantum error correction. Proc. R. Soc. Lond. A, 452 (1954): 2551–2577, 1996a. 10.1098/​rspa.1996.0136.

[36] Andrew M Steane. Error correcting codes in quantum theory. Physical Review Letters, 77 (5): 793, 1996b. 10.1103/​PhysRevLett.77.793.

[37] Barbara M Terhal. Quantum error correction for quantum memories. Reviews of Modern Physics, 87 (2): 307, 2015. 10.1103/​RevModPhys.87.307.

[38] Jean-Pierre Tillich and Gilles 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, 2013. 10.1109/​TIT.2013.2292061.

[39] Christophe Vuillot and Nikolas P. Breuckmann. Quantum pin codes. IEEE Transactions on Information Theory, 2022. 10.1109/​TIT.2022.3170846.

[40] Chuan-Kun Wu and Ed Dawson. Existence of generalized inverse of linear transformations over finite fields. Finite Fields and Their Applications, 4 (4): 307–315, 1998. 10.1006/​ffta.1998.0215.

[41] Weilei Zeng and Leonid P. Pryadko. Higher-dimensional quantum hypergraph-product codes with finite rates. Phys. Rev. Lett., 122: 230501, Jun 2019. 10.1103/​PhysRevLett.122.230501. URL https:/​/​link.aps.org/​doi/​10.1103/​PhysRevLett.122.230501.

[42] Weilei Zeng and Leonid P. Pryadko. Minimal distances for certain quantum product codes and tensor products of chain complexes. Phys. Rev. A, 102: 062402, 2020. 10.1103/​PhysRevA.102.062402.

Cited by

[1] Nikolas P. Breuckmann and Jens Niklas Eberhardt, "Quantum Low-Density Parity-Check Codes", PRX Quantum 2 4, 040101 (2021).

[2] Aurélie Denys, Peter Brown, and Anthony Leverrier, "Explicit asymptotic secret key rate of continuous-variable quantum key distribution with an arbitrary modulation", arXiv:2103.13945.

[3] Nouédyn Baspin and Anirudh Krishna, "Connectivity constrains quantum codes", arXiv:2106.00765.

The above citations are from SAO/NASA ADS (last updated successfully 2022-08-13 16:16:48). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2022-08-13 16:16:46).