Fault-tolerant gates via homological product codes

Tomas Jochym-O'Connor

doi:10.22331/q-2019-02-04-120

Fault-tolerant gates via homological product codes

Walter Burke Institute for Theoretical Physics, Institute for Quantum Information & Matter, California Institute of Technology, Pasadena, CA 91125, USA

Published:	2019-02-04, volume 3, page 120
Eprint:	arXiv:1807.09783v2
Doi:	https://doi.org/10.22331/q-2019-02-04-120
Citation:	Quantum 3, 120 (2019).

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

Abstract

A method for the implementation of a universal set of fault-tolerant logical gates is presented using homological product codes. In particular, it is shown that one can fault-tolerantly map between different encoded representations of a given logical state, enabling the application of different classes of transversal gates belonging to the underlying quantum codes. This allows for the circumvention of no-go results pertaining to universal sets of transversal gates and provides a general scheme for fault-tolerant computation while keeping the stabilizer generators of the code sparse.

Popular summary

Quantum error correction provides a means to combat errors present in a physical realization of a quantum computer. However, one must also prevent errors from proliferating when computing on the stored quantum data. This is the central goal of fault tolerance. Unfortunately, there is no simple method to both protect and manipulate the data of a single code in a universal manner, that is exploit the full power of the quantum computer. Rather, additional tricks or resources are required.

We present a method to cross between different codes in a fault-tolerant manner, allowing one to exploit the desirable properties of both codes. The path between different codes may spread errors, but importantly it does so in a controlled manner that allows for the resulting code to clean up any noise that has propagated. Moreover, the method keeps the code simple and does not rely on preparing special resource states or measuring complicated objects. This provides a potential fruitful alternative to universal fault tolerance.

► BibTeX data

@article{JochymOConnor2019faulttolerantgates,
  doi = {10.22331/q-2019-02-04-120},
  url = {https://doi.org/10.22331/q-2019-02-04-120},
  title = {Fault-tolerant gates via homological product codes},
  author = {Jochym-O'Connor, Tomas},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {3},
  pages = {120},
  month = feb,
  year = {2019}
}

► References

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

[2] Austin G. Fowler, Matteo Mariantoni, John M. Martinis, and Andrew N. Cleland. Surface codes: Towards practical large-scale quantum computation. Phys. Rev. A, 86: 032324, 2012. 10.1103/PhysRevA.86.032324.
https://doi.org/10.1103/PhysRevA.86.032324

[3] R. Barends, J. Kelly, A. Megrant, A. Veitia, D. Sank, E. Jeffrey, T. C. White, J. Mutus, A. G. Fowler, B. Campbell, et al. Superconducting quantum circuits at the surface code threshold for fault tolerance. Nature, 508 (7497): 500–503, 2014. 10.1038/nature13171.
https://doi.org/10.1038/nature13171

[4] Jerry M. Chow, Jay M. Gambetta, Easwar Magesan, David W. Abraham, Andrew W. Cross, B. R. Johnson, Nicholas A. Masluk, Colm A. Ryan, John A. Smolin, Srikanth J. Srinivasan, et al. Implementing a strand of a scalable fault-tolerant quantum computing fabric. Nature communications, 5, 2014. 10.1038/ncomms5015.
https://doi.org/10.1038/ncomms5015

[5] Daniel Nigg, Markus Mueller, Esteban A Martinez, Philipp Schindler, Markus Hennrich, Thomas Monz, Miguel A Martin-Delgado, and Rainer Blatt. Quantum computations on a topologically encoded qubit. Science, page 1253742, 2014. 10.1126/science.1253742.
https://doi.org/10.1126/science.1253742

[6] J. Kelly, R. Barends, A. G. Fowler, A. Megrant, E. Jeffrey, T. C. White, D. Sank, J. Y. Mutus, B. Campbell, Yu Chen, et al. State preservation by repetitive error detection in a superconducting quantum circuit. Nature, 519 (7541): 66–69, 2015. 10.1038/nature14270.
https://doi.org/10.1038/nature14270

[7] Maika Takita, Antonio D Córcoles, Easwar Magesan, Baleegh Abdo, Markus Brink, Andrew Cross, Jerry M Chow, and Jay M Gambetta. Demonstration of weight-four parity measurements in the surface code architecture. Phy. Rev. Lett., 117 (21): 210505, 2016. 10.1103/PhysRevLett.117.210505.
https://doi.org/10.1103/PhysRevLett.117.210505

[8] Héctor Bombín. Gauge color codes: optimal transversal gates and gauge fixing in topological stabilizer codes. New J. Phys., 17 (8): 083002, 2015a. 10.1088/1367-2630/17/8/083002.
https://doi.org/10.1088/1367-2630/17/8/083002

[9] Aleksander Kubica and Michael E. Beverland. Universal transversal gates with color codes: A simplified approach. Phys. Rev. A, 91: 032330, 2015. 10.1103/PhysRevA.91.032330.
https://doi.org/10.1103/PhysRevA.91.032330

[10] Sergey Bravyi and Robert König. Classification of topologically protected gates for local stabilizer codes. Phys. Rev. Lett., 110 (17): 170503, 2013. 10.1103/PhysRevLett.110.170503.
https://doi.org/10.1103/PhysRevLett.110.170503

[11] Fernando Pastawski and Beni Yoshida. Fault-tolerant logical gates in quantum error-correcting codes. Phys. Rev. A, 91: 012305, 2015. 10.1103/PhysRevA.91.012305.
https://doi.org/10.1103/PhysRevA.91.012305

[12] Aleksander Kubica, Beni Yoshida, and Fernando Pastawski. Unfolding the color code. New Journal of Physics, 17 (8): 083026, 2015. 10.1088/1367-2630/17/8/083026.
https://doi.org/10.1088/1367-2630/17/8/083026

[13] Tomas Jochym-O'Connor, Aleksander Kubica, and Theodore J Yoder. Disjointness of stabilizer codes and limitations on fault-tolerant logical gates. Phys. Rev. X, 8 (2): 021047, 2018. 10.1103/PhysRevX.8.021047.
https://doi.org/10.1103/PhysRevX.8.021047

[14] DJC MacKay, G Mitchison, and PL McFadden. Sparse-graph codes for quantum error correction. IEEE Transactions on Information Theory, 50 (10): 2315–2330, 2004. 10.1109/TIT.2004.834737.
https://doi.org/10.1109/TIT.2004.834737

[15] Alexey A Kovalev and Leonid P Pryadko. Improved quantum hypergraph-product ldpc codes. In 2012 IEEE International Symposium on Information Theory Proceedings, pages 348–352. IEEE, 2012. 10.1109/ISIT.2012.6284206.
https://doi.org/10.1109/ISIT.2012.6284206

[16] 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.
https://doi.org/10.1145/2591796.2591870

[17] Michael H Freedman and Matthew B Hastings. Quantum systems on non-k-hyperfinite complexes: a generalization of classical statistical mechanics on expander graphs. Quant. Inf. Comput., 14 (1-2): 144–180, 2014. 10.26421/QIC14.1-2.
https://doi.org/10.26421/QIC14.1-2

[18] 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, 2014. 10.1109/TIT.2013.2292061.
https://doi.org/10.1109/TIT.2013.2292061

[19] Mathew B. Hastings. Weight reduction for quantum codes. Quantum Information & Computation, 17 (15-16): 1307–1334, 2017. 10.26421/QIC17.15-16.
https://doi.org/10.26421/QIC17.15-16

[20] Daniel Gottesman. Fault-tolerant quantum computation with constant overhead. Quantum Information & Computation, 14 (15-16): 1338–1372, 2014. 10.26421/QIC14.15-16.
https://doi.org/10.26421/QIC14.15-16

[21] Anthony Leverrier, Jean-Pierre Tillich, and Gilles Zémor. Quantum expander codes. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 810–824. IEEE, 2015. 10.1109/FOCS.2015.55.
https://doi.org/10.1109/FOCS.2015.55

[22] Omar Fawzi, Antoine Grospellier, and Anthony Leverrier. Efficient decoding of random errors for quantum expander codes. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 521–534. ACM, 2018a. 10.1145/3188745.3188886.
https://doi.org/10.1145/3188745.3188886

[23] Omar Fawzi, Antoine Grospellier, and Anthony Leverrier. Constant overhead quantum fault-tolerance with quantum expander codes. arXiv:1808.03821, 2018b. URL https://arxiv.org/abs/1808.03821.
arXiv:1808.03821

[24] Bryan Eastin and Emanuel Knill. Restrictions on transversal encoded quantum gate sets. Phys. Rev. Lett., 102: 110502, 2009. 10.1103/PhysRevLett.102.110502.
https://doi.org/10.1103/PhysRevLett.102.110502

[25] Bei Zeng, Andrew W. Cross, and Isaac L. Chuang. Transversality Versus Universality for Additive Quantum Codes. IEEE Transactions on Information Theory, 57: 6272–6284, 2011. 10.1109/TIT.2011.2161917.
https://doi.org/10.1109/TIT.2011.2161917

[26] Peter W. Shor. Fault-tolerant quantum computation. Proceedings of the 37th Annual Symposium on Foundations of Computer Science, pages 56–65, 1996. 10.1109/SFCS.1996.548464.
https://doi.org/10.1109/SFCS.1996.548464

[27] Emanuel Knill, Raymond Laflamme, and Wojciech H. Zurek. Threshold accuracy for quantum computation. arXiv: quant-ph/9610011, 1996. URL https://arxiv.org/abs/quant-ph/9610011.
arXiv:quant-ph/9610011

[28] Sergey Bravyi and Alexei Kitaev. Universal quantum computation with ideal Clifford gates and noisy ancillas. Phys. Rev. A, 71: 022316, 2005. 10.1103/PhysRevA.71.022316.
https://doi.org/10.1103/PhysRevA.71.022316

[29] Adam Paetznick and Ben W. Reichardt. Universal fault-tolerant quantum computation with only transversal gates and error correction. Phys. Rev. Lett., 111: 090505, 2013. 10.1103/PhysRevLett.111.090505.
https://doi.org/10.1103/PhysRevLett.111.090505

[30] Tomas Jochym-O'Connor and Raymond Laflamme. Using concatenated quantum codes for universal fault-tolerant quantum gates. Phys. Rev. Lett., 112: 010505, 2014. 10.1103/PhysRevLett.112.010505.
https://doi.org/10.1103/PhysRevLett.112.010505

[31] Jonas T. Anderson, Guillaume Duclos-Cianci, and David Poulin. Fault-tolerant conversion between the steane and reed-muller quantum codes. Phys. Rev. Lett., 113: 080501, 2014. 10.1103/PhysRevLett.113.080501.
https://doi.org/10.1103/PhysRevLett.113.080501

[32] Héctor Bombín. Dimensional jump in quantum error correction. New J. Phys., 18 (4): 043038, 2015b. 10.1088/1367-2630/18/4/043038.
https://doi.org/10.1088/1367-2630/18/4/043038

[33] Sergey Bravyi and Andrew Cross. Doubled color codes. arXiv:1509.03239, 2015. URL https://arxiv.org/abs/1509.03239.
arXiv:1509.03239

[34] Tomas Jochym-O'Connor and Stephen D. Bartlett. Stacked codes: Universal fault-tolerant quantum computation in a two-dimensional layout. Phys. Rev. A, 93: 022323, 2016. 10.1103/PhysRevA.93.022323.
https://doi.org/10.1103/PhysRevA.93.022323

[35] Cody Jones, Peter Brooks, and Jim Harrington. Gauge color codes in two dimensions. Phys. Rev. A, 93 (5): 052332, 2016. 10.1103/PhysRevA.93.052332.
https://doi.org/10.1103/PhysRevA.93.052332

[36] Theodore J. Yoder, Ryuji Takagi, and Isaac L. Chuang. Universal fault-tolerant gates on concatenated stabilizer codes. Phys. Rev. X, 6: 031039, Sep 2016. 10.1103/PhysRevX.6.031039.
https://doi.org/10.1103/PhysRevX.6.031039

[37] Héctor Bombín and Miguel A. Martin-Delgado. Topological quantum distillation. Phys. Rev. Lett., 97: 180501, 2006. 10.1103/PhysRevLett.97.180501.
https://doi.org/10.1103/PhysRevLett.97.180501

[38] Alexey A. Kovalev and Leonid P. Pryadko. Fault tolerance of quantum low-density parity check codes with sublinear distance scaling. Phys. Rev. A, 87: 020304, Feb 2013. 10.1103/PhysRevA.87.020304.
https://doi.org/10.1103/PhysRevA.87.020304

[39] A. Robert Calderbank and Peter W. Shor. Good quantum error-correcting codes exist. Phys. Rev. A, 54: 1098–1105, 1996. 10.1103/PhysRevA.54.1098.
https://doi.org/10.1103/PhysRevA.54.1098

[40] Andrew W. Steane. Multiple-Particle Interference and Quantum Error Correction. Proc. Roy. Soc. Lond., 452: 2551–2577, 1996. 10.1098/rspa.1996.0136.
https://doi.org/10.1098/rspa.1996.0136

[41] Daniel Gottesman. Stabilizer Codes and Quantum Error Correction. PhD thesis, California Institute of Technology, 1997.

[42] Emanuel Knill and Raymond Laflamme. Theory of quantum error-correcting codes. Phys. Rev. A, 55: 900–911, 1997. 10.1103/PhysRevA.55.900.
https://doi.org/10.1103/PhysRevA.55.900

[43] Benjamin J Brown, Wonmin Son, Christina V Kraus, Rosario Fazio, and Vlatko Vedral. Generating topological order from a two-dimensional cluster state using a duality mapping. New J. Phys., 13 (6): 065010, 2011. 10.1088/1367-2630/13/6/065010.
https://doi.org/10.1088/1367-2630/13/6/065010

[44] Héctor Bombín. Single-shot fault-tolerant quantum error correction. Phys. Rev. X, 5: 031043, 2015c. 10.1103/PhysRevX.5.031043.
https://doi.org/10.1103/PhysRevX.5.031043

[45] Earl Campbell. A theory of single-shot error correction for adversarial noise. Quantum Sci. Technol., 2019. 10.1088/2058-9565/aafc8f.
https://doi.org/10.1088/2058-9565/aafc8f

[46] Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, and Harald Weinfurter. Elementary gates for quantum computation. Phys. Rev. A, 52 (5): 3457, 1995. 10.1103/PhysRevA.52.3457.
https://doi.org/10.1103/PhysRevA.52.3457

[47] Christopher Chamberland, Tomas Jochym-O'Connor, and Raymond Laflamme. Thresholds for universal concatenated quantum codes. Phys. Rev. Lett., 117: 010501, 2016. 10.1103/PhysRevLett.117.010501.
https://doi.org/10.1103/PhysRevLett.117.010501

[48] Christopher Chamberland, Tomas Jochym-O'Connor, and Raymond Laflamme. Overhead analysis of universal concatenated quantum codes. Phys. Rev. A, 95: 022313, Feb 2017. 10.1103/PhysRevA.95.022313.
https://doi.org/10.1103/PhysRevA.95.022313

[49] Christopher Chamberland and Tomas Jochym-O'Connor. Error suppression via complementary gauge choices in reed-muller codes. Quantum Sci. Technol., 2 (3): 035008, 2017. 10.1088/2058-9565/aa7c4a.
https://doi.org/10.1088/2058-9565/aa7c4a

[50] Alexei Kitaev. Anyons in an exactly solved model and beyond. Annals of Physics, 321 (1): 2–111, 2006. 10.1016/j.aop.2005.10.005.
https://doi.org/10.1016/j.aop.2005.10.005

[51] Sergey Bravyi, Barbara M Terhal, and Bernhard Leemhuis. Majorana fermion codes. New J. Phys., 12 (8): 083039, 2010. 10.1088/1367-2630/12/8/083039.
https://doi.org/10.1088/1367-2630/12/8/083039

Cited by

[1] Simon Burton and Dan Browne, "Limitations on Transversal Gates for Hypergraph Product Codes", IEEE Transactions on Information Theory 68 3, 1772 (2022).

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

[3] Daryus Chandra, Zunaira Babar, Hung Viet Nguyen, Dimitrios Alanis, Panagiotis Botsinis, Soon Xin Ng, and Lajos Hanzo, "Quantum Topological Error Correction Codes are Capable of Improving the Performance of Clifford Gates", IEEE Access 7, 121501 (2019).

[4] Anirudh Krishna and David Poulin, "Fault-Tolerant Gates on Hypergraph Product Codes", Physical Review X 11 1, 011023 (2021).

[5] Paul Webster, Michael Vasmer, Thomas R. Scruby, and Stephen D. Bartlett, "Universal fault-tolerant quantum computing with stabilizer codes", Physical Review Research 4 1, 013092 (2022).

[6] Christopher Chamberland and Kyungjoo Noh, "Very low overhead fault-tolerant magic state preparation using redundant ancilla encoding and flag qubits", npj Quantum Information 6 1, 91 (2020).

[7] Michael Newman, Leonardo Andreta de Castro, and Kenneth R. Brown, "Generating Fault-Tolerant Cluster States from Crystal Structures", Quantum 4, 295 (2020).

[8] Maxime A. Tremblay, Nicolas Delfosse, and Michael E. Beverland, "Constant-Overhead Quantum Error Correction with Thin Planar Connectivity", Physical Review Letters 129 5, 050504 (2022).

[9] Diego Ristè, Luke C. G. Govia, Brian Donovan, Spencer D. Fallek, William D. Kalfus, Markus Brink, Nicholas T. Bronn, and Thomas A. Ohki, "Real-time processing of stabilizer measurements in a bit-flip code", npj Quantum Information 6 1, 71 (2020).

[10] Shilin Huang, Tomas Jochym-O’Connor, and Theodore J. Yoder, "Homomorphic Logical Measurements", PRX Quantum 4 3, 030301 (2023).

[11] Armanda O. Quintavalle, Paul Webster, and Michael Vasmer, "Partitioning qubits in hypergraph product codes to implement logical gates", Quantum 7, 1153 (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2023-11-29 19:57:49) and SAO/NASA ADS (last updated successfully 2023-11-29 19:57:50). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.