Universal logical gates with constant overhead: instantaneous Dehn twists for hyperbolic quantum codes

Ali Lavasani, Guanyu Zhu, and Maissam Barkeshli

Department of Physics, Condensed Matter Theory Center, University of Maryland, College Park, Maryland 20742, USA and Joint Quantum Institute, University of Maryland, College Park, Maryland 20742, USA

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


A basic question in the theory of fault-tolerant quantum computation is to understand the fundamental resource costs for performing a universal logical set of gates on encoded qubits to arbitrary accuracy. Here we consider qubits encoded with constant space overhead (i.e. finite encoding rate) in the limit of arbitrarily large code distance $d$ through the use of topological codes associated to triangulations of hyperbolic surfaces. We introduce explicit protocols to demonstrate how Dehn twists of the hyperbolic surface can be implemented on the code through constant depth unitary circuits, without increasing the space overhead. The circuit for a given Dehn twist consists of a permutation of physical qubits, followed by a constant depth local unitary circuit, where locality here is defined with respect to a hyperbolic metric that defines the code. Applying our results to the hyperbolic Fibonacci Turaev-Viro code implies the possibility of applying universal logical gate sets on encoded qubits through constant depth unitary circuits and with constant space overhead. Our circuits are inherently protected from errors as they map local operators to local operators while changing the size of their support by at most a constant factor; in the presence of noisy syndrome measurements, our results suggest the possibility of universal fault tolerant quantum computation with constant space overhead and time overhead of $\mathcal{O}(d/\log d)$. For quantum circuits that allow parallel gate operations, this yields the optimal scaling of space-time overhead known to date.

► BibTeX data

► References

[1] Christopher J. Axline, Luke D. Burkhart, Wolfgang Pfaff, Mengzhen Zhang, Kevin Chou, Philippe Campagne-Ibarcq, Philip Reinhold, Luigi Frunzio, S. M. Girvin, Liang Jiang, M. H. Devoret, and R. J. Schoelkopf. On-demand quantum state transfer and entanglement between remote microwave cavity memories. Nature Physics, 14 (7): 705–710, apr 2018. 10.1038/​s41567-018-0115-y.

[2] Maissam Barkeshli and Michael Freedman. Modular transformations through sequences of topological charge projections. Physical Review B, 94 (16), oct 2016. 10.1103/​physrevb.94.165108.

[3] John W. Barrett and Bruce W. Westbury. Invariants of piecewise-linear 3-manifolds. Trans. Amer. Math. Soc., 348: 3997–4022, 1996. 10.1090/​S0002-9947-96-01660-1.

[4] Michael E Beverland, Oliver Buerschaper, Robert Koenig, Fernando Pastawski, John Preskill, and Sumit Sijher. Protected gates for topological quantum field theories. Journal of Mathematical Physics, 57 (2): 022201–40, February 2016. 10.1063/​1.4939783.

[5] Mikhail Bogdanov and Monique Teillaud. Delaunay triangulations and cycles on closed hyperbolic surfaces. [Research Report] RR-8434, INRIA, December 2013.

[6] Mikhail Bogdanov, Olivier Devillers, Monique Teillaud, and Olivier Devillers. Hyperbolic delaunay complexes and voronoi diagrams made practical. JoCG 5(1), 56–85, December 2014. 10.1145/​2462356.2462365.

[7] Hector Bombin. Single-Shot Fault-Tolerant Quantum Error Correction. Physical Review X, 5 (3): 181–26, September 2015. 10.1103/​PhysRevX.5.031043.

[8] Parsa Bonderson, Michael Freedman, and Chetan Nayak. Measurement-only topological quantum computation via anyonic interferometry. Annals of Physics, 324 (4): 787 – 826, 2009. 10.1016/​j.aop.2008.09.009.

[9] N E Bonesteel and D P DiVincenzo. Quantum circuits for measuring Levin-Wen operators. Physical Review B, 86 (16): 165113, 2012. 10.1103/​PhysRevB.86.165113.

[10] Sergey Bravyi and Matthew B. Hastings. Homological product codes. Proc. of the 46th ACM Symposium on Theory of Computing (STOC 2014), pages 273–282, 2014. 10.1145/​2591796.2591870.

[11] Sergey Bravyi and Alexei Kitaev. Universal quantum computation with ideal clifford gates and noisy ancillas. Phys. Rev. A, 71: 022316, Feb 2005. 10.1103/​PhysRevA.71.022316.

[12] Sergey Bravyi and Robert König. Classification of Topologically Protected Gates for Local Stabilizer Codes. Phys. Rev. Lett., 110 (17): 170503–5, April 2013. 10.1103/​PhysRevLett.110.170503.

[13] Sergey Bravyi, David Poulin, and Barbara Terhal. Tradeoffs for reliable quantum information storage in 2d systems. Physical review letters, 104 (5): 050503, 2010. 10.1103/​PhysRevLett.104.050503.

[14] Nikolas P. Breuckmann and Barbara M. Terhal. Constructions and noise threshold of hyperbolic surface codes. IEEE Transactions on Information Theory, 62, 2016. 10.1109/​TIT.2016.2555700.

[15] Nikolas P Breuckmann, Christophe Vuillot, Earl Campbell, Anirudh Krishna, and Barbara M Terhal. Hyperbolic and semi-hyperbolic surface codes for quantum storage. Quantum Science and Technology, 2 (3): 035007–21, August 2017. 10.1088/​2058-9565/​aa7d3b.

[16] Simon Burton, Courtney G Brell, and Steven T Flammia. Classical simulation of quantum error correction in a Fibonacci anyon code. Physical Review A, 95 (2): 580–10, February 2017. 10.1103/​PhysRevA.95.022309.

[17] A. R. Calderbank and Peter W. Shor. Good quantum error-correcting codes exist. Phys. Rev. A, 54: 1098–1105, Aug 1996. 10.1103/​PhysRevA.54.1098.

[18] P. Campagne-Ibarcq, E. Zalys-Geller, A. Narla, S. Shankar, P. Reinhold, L. Burkhart, C. Axline, W. Pfaff, L. Frunzio, R. J. Schoelkopf, and M. H. Devoret. Deterministic remote entanglement of superconducting circuits through microwave two-photon transitions. Phys. Rev. Lett., 120: 200501, May 2018. 10.1103/​PhysRevLett.120.200501.

[19] K S Chou, J Z Blumoff, C S Wang, Reinhold, P. C., C J Axline, Y Y Gao, L Frunzio, M H Devoret, Liang Jiang, and R J Schoelkopf. Deterministic teleportation of a quantum gate between two logical qubits. January 2018. 10.1038/​s41586-018-0470-y.

[20] Daniel Comparat and Pierre Pillet. Dipole blockade in a cold Rydberg atomic sample [Invited]. Journal of the Optical Society of America B, 27 (6): A208–A232, June 2010. 10.1364/​JOSAB.27.00A208.

[21] Guillaume Dauphinais and David Poulin. Fault-Tolerant Quantum Error Correction for non-Abelian Anyons. Communications in Mathematical Physics, 355 (2): 519–560, July 2017. 10.1007/​s00220-017-2923-9.

[22] Max Dehn. Papers on group theory and topology. Springer Science & Business Media, 2012. 10.1007/​978-1-4612-4668-8.

[23] Benson Farb and Dan Margalit. A primer on mapping class groups (pms-49). Princeton University Press, 2011. 10.23943/​princeton/​9780691147949.001.0001.

[24] Weibo Feng. Non-abelian quantum error correction. Ph.D. Thesis, The Florida State University, 2015.

[25] M H Freedman, M Larsen, and Z H Wang. A modular functor which is universal for quantum computation. Communications in Mathematical Physics, 227 (3): 605–622, June 2002a. 10.1007/​s002200200645.

[26] 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, 2002b.

[27] Robert Fricke and Felix Klein. Vorlesungen uber die Theorie der automorphen Funktionen. Johnson Reprint, 1897. 10.1007/​BF01699777.

[28] Daniel Gottesman. Fault-Tolerant Quantum Computation with Constant Overhead. Quantum Information & Computation, 14 (15-16): 1338–1371, November 2014.

[29] Larry Guth and Alexander Lubotzky. Quantum error correcting codes and 4-dimensional arithmetic hyperbolic manifolds. Journal of Mathematical Physics, 55 (8): 082202, August 2014. 10.1063/​1.4891487.

[30] David A Herrera-Martí, Austin G Fowler, David Jennings, and Terry Rudolph. Photonic implementation for the topological cluster-state quantum computer. Physical Review A, 82 (3): 032332–6, September 2010. 10.1103/​PhysRevA.82.032332.

[31] Ø Hjelle and M Dæhlen. Triangulations and applications. Springer; 2006 edition (September 19, 2006). 10.1007/​3-540-33261-8.

[32] Linda Keen. Canonical polygons for finitely generated fuchsian groups. Acta Mathematica, 115 (1): 1–16, 1966. 10.1007/​BF02392200.

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

[34] Robert Koenig, Greg Kuperberg, and Ben W Reichardt. Quantum computation with Turaev-Viro codes. Annals of Physics, 325 (12): 2707–2749, December 2010. 10.1016/​j.aop.2010.08.001.

[35] Alicia J. Kollár, Mattias Fitzpatrick, and Andrew A. Houck. Hyperbolic lattices in circuit quantum electrodynamics. Nature, 571 (7763): 45–50, 2019. 10.1038/​s41586-019-1348-3.

[36] 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.

[37] Philipp Kurpiers, Paul Magnard, Theo Walter, Baptiste Royer, Marek Pechal, Johannes Heinsoo, Yves Salathé, Abdulkadir Akin, Simon Storz, J-C Besse, et al. Deterministic quantum state transfer and remote entanglement using microwave photons. Nature, 558 (7709): 264, 2018. 10.1038/​s41586-018-0195-y.

[38] Ali Lavasani and Maissam Barkeshli. Low overhead clifford gates from joint measurements in surface, color, and hyperbolic codes. 2018. 10.1103/​PhysRevA.98.052319.

[39] Bjoern Lekitsch, Sebastian Weidt, Austin G. Fowler, Klaus Mølmer, Simon J. Devitt, Christof Wunderlich, and Winfried K. Hensinger. Blueprint for a microwave trapped ion quantum computer. Science Advances, 3 (2), 2017. 10.1126/​sciadv.1601540.

[40] Anthony Leverrier, Jean-Pierre Tillich, and Gilles Zémor. Quantum expander codes. pages 810–824, 2015. 10.1109/​FOCS.2015.55.

[41] Michael A. Levin and Xiao-Gang Wen. String-net condensation: A physical mechanism for topological phases. Phys. Rev. B, 71: 045110, Jan 2005. 10.1103/​PhysRevB.71.045110.

[42] N M Linke, D Maslov, M Roetteler, S Debnath, C Figgatt, K A Landsman, K Wright, and C Monroe. Experimental Comparison of Two Quantum Computing Architectures. PNAS 13, 3305–3310, February 2017. 10.1073/​pnas.1618020114.

[43] K M Maller, M T Lichtman, T Xia, Y Sun, M J Piotrowicz, A W Carr, L Isenhower, and M Saffman. Rydberg-blockade controlled-not gate and entanglement in a two-dimensional array of neutral-atom qubits. Physical Review A, 92 (2): 022336–12, August 2015. 10.1103/​PhysRevA.92.022336.

[44] James Munkres. Obstructions to the smoothing of piecewise-differentiable homeomorphisms. Annals of Mathematics, pages 521–554, 1960. 10.2307/​1970228.

[45] Chetan Nayak, Steven H. Simon, Ady Stern, Michael Freedman, and Sankar Das Sarma. Non-abelian anyons and topological quantum computation. 80: 1083, 2008. 10.1103/​RevModPhys.80.1083.

[46] Jakob Nielsen. Untersuchungen zur topologie der geschlossenen zweiseitigen flächen. Acta Mathematica, 50 (1): 189–358, 1927. 10.1007/​BF02421324.

[47] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010. 10.1017/​CBO9780511976667.

[48] Adam Paetznick and Ben W Reichardt. Universal Fault-Tolerant Quantum Computation with Only Transversal Gates and Error Correction. Phys. Rev. Lett., 111 (9): 090505–5, August 2013. 10.1103/​PhysRevLett.111.090505.

[49] Hannes Pichler, Guanyu Zhu, Alireza Seif, Peter Zoller, and Mohammad Hafezi. Measurement Protocol for the Entanglement Spectrum of Cold Atoms. Physical Review X, 6 (4): 041033–12, November 2016. 10.1103/​PhysRevX.6.041033.

[50] M Saffman, T G Walker, and K Mølmer. Quantum information with Rydberg atoms. Rev. Mod. Phys., 82 (3): 2313–2363, August 2010. 10.1103/​RevModPhys.82.2313.

[51] Barbara M Terhal. Quantum error correction for quantum memories. Rev. Mod. Phys., 87 (2): 307–346, April 2015. 10.1103/​RevModPhys.87.307.

[52] J.-P Tillich and Gilles Zémor. Quantum ldpc codes with positive rate and minimum distance proportional to the square root of the blocklength. Information Theory, IEEE Transactions on, 60: 1193–1202, 02 2014. 10.1109/​TIT.2013.2292061.

[53] V.G. Turaev and O.Y. Viro. State sum invariants of 3-manifolds and quantum 6j-symbols. Topology, 31: 865–902, 1992. 10.1016/​0040-9383(92)90015-A.

[54] Zhenghan Wang. Topological Quantum Computation. American Mathematics Society, 2010.

[55] Gilles Zémor. On cayley graphs, surface codes, and the limits of homological coding for quantum error correction. In Yeow Meng Chee, Chao Li, San Ling, Huaxiong Wang, and Chaoping Xing, editors, Coding and Cryptology, pages 259–273, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg. ISBN 978-3-642-01877-0. 10.1007/​978-3-642-01877-0_21.

[56] Guanyu Zhu, Mohammad Hafezi, and Maissam Barkeshli. Quantum Origami: Transversal Gates for Quantum Computation and Measurement of Topological Order. arXiv:1711.05752, November 2017.

[57] Guanyu Zhu, Ali Lavasani, and Maissam Barkeshli. Instantaneous braids and dehn twists in topologically ordered states. arXiv preprint arXiv:1806.06078, 2018a.

[58] Guanyu Zhu, Ali Lavasani, and Maissam Barkeshli. Fast universal logical gates on topologically encoded qubits at arbitrarily large code distances. arXiv preprint arXiv:1806.02358, 2018b.

Cited by

[1] Paul Webster and Stephen D. Bartlett, "Fault-tolerant quantum gates with defects in topological stabilizer codes", Physical Review A 102 2, 022403 (2020).

[2] Christopher Chamberland, Guanyu Zhu, Theodore J. Yoder, Jared B. Hertzberg, and Andrew W. Cross, "Topological and Subsystem Codes on Low-Degree Graphs with Flag Qubits", Physical Review X 10 1, 011022 (2020).

[3] 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).

[4] 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).

[5] Igor Boettcher, Przemyslaw Bienias, Ron Belyansky, Alicia J. Kollár, and Alexey V. Gorshkov, "Quantum simulation of hyperbolic space with circuit quantum electrodynamics: From graphs to geometry", Physical Review A 102 3, 032208 (2020).

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

[7] Sam Cree, Kfir Dolev, Vladimir Calvera, and Dominic J. Williamson, "Fault-tolerant logical gates in holographic stabilizer codes are severely restricted", arXiv:2103.13404.

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

1 thought on “Universal logical gates with constant overhead: instantaneous Dehn twists for hyperbolic quantum codes

  1. Pingback: From Joint Quantum Institute: “Quantum Computers Do the (Instantaneous) Twist” | sciencesprings