A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery

Daniel Litinski

Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, Arnimallee 14, 14195 Berlin, Germany

Given a quantum gate circuit, how does one execute it in a fault-tolerant architecture with as little overhead as possible? In this paper, we discuss strategies for surface-code quantum computing on small, intermediate and large scales. They are strategies for space-time trade-offs, going from slow computations using few qubits to fast computations using many qubits. Our schemes are based on surface-code patches, which not only feature a low space cost compared to other surface-code schemes, but are also conceptually simple~--~simple enough that they can be described as a tile-based game with a small set of rules. Therefore, no knowledge of quantum error correction is necessary to understand the schemes in this paper, but only the concepts of qubits and measurements.

Video of the QIP talk about this paper:

Useful, classically intractable quantum computations can be very long, potentially consisting of billions of quantum gates. Some of these computations use as few as 100 qubits, but these need to be logical error-corrected qubits, rather than physical qubits, as the coherence times of currently available physical qubits are many orders of magnitude shorter than the execution times of these computations. With logical qubits, the set of available operation is determined by the error-correcting code, independently of the underlying physical hardware. For full-scale quantum computations on hundreds of logical qubits (i.e., potentially hundreds of thousands of physical qubits), it is useful to have a framework that describes logical qubits and operations without keeping track of the details of the physical hardware and error-correction protocols. This paper introduces such a framework with a focus on surface codes, but can also be applied to other topological codes. It uses lattice surgery to describe all logical operations via the easy-to-understand concepts of qubits and measurements, avoiding anyons and topological braiding diagrams. Using this framework, a complete full-scale quantum computer is constructed, consisting of qubit blocks that perform magic state distillation and blocks that consume magic states to advance the computation. Finally, space-time trade-offs are discussed, i.e., how to use more qubits to compute faster.

► BibTeX data

► References

[1] M. Reiher, N. Wiebe, K. M. Svore, D. Wecker, and M. Troyer, Elucidating reaction mechanisms on quantum computers, PNAS 114, 7555 (2017).
https://doi.org/10.1073/pnas.1619152114

[2] R. Babbush, C. Gidney, D. W. Berry, N. Wiebe, J. McClean, A. Paler, A. Fowler, and H. Neven, Encoding electronic spectra in quantum circuits with linear T complexity, Phys. Rev. X 8, 041015 (2018a).
https://doi.org/10.1103/PhysRevX.8.041015

[3] J. Preskill, Reliable quantum computers, Proc. Roy. Soc. Lond. A 454, 385 (1998).
https://doi.org/10.1098/rspa.1998.0167

[4] B. M. Terhal, Quantum error correction for quantum memories, Rev. Mod. Phys. 87, 307 (2015).
https://doi.org/10.1103/RevModPhys.87.307

[5] E. T. Campbell, B. M. Terhal, and C. Vuillot, Roads towards fault-tolerant universal quantum computation, Nature 549, 172 (2017).
https://doi.org/10.1038/nature23460

[6] A. Y. Kitaev, Fault-tolerant quantum computation by anyons, Ann. Phys. 303, 2 (2003).
https://doi.org/10.1016/S0003-4916(02)00018-0

[7] A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, Surface codes: Towards practical large-scale quantum computation, Phys. Rev. A 86, 032324 (2012).
https://doi.org/10.1103/PhysRevA.86.032324

[8] H. Bombin, Topological order with a twist: Ising anyons from an abelian model, Phys. Rev. Lett. 105, 030403 (2010).
https://doi.org/10.1103/PhysRevLett.105.030403

[9] C. Horsman, A. G. Fowler, S. Devitt, and R. V. Meter, Surface code quantum computing by lattice surgery, New J. Phys. 14, 123011 (2012).
https://doi.org/10.1088/1367-2630/14/12/123011

[10] B. J. Brown, K. Laubscher, M. S. Kesselring, and J. R. Wootton, Poking holes and cutting corners to achieve Clifford gates with the surface code, Phys. Rev. X 7, 021029 (2017).
https://doi.org/10.1103/PhysRevX.7.021029

[11] D. Litinski and F. v. Oppen, Lattice Surgery with a Twist: Simplifying Clifford Gates of Surface Codes, Quantum 2, 62 (2018).
https://doi.org/10.22331/q-2018-05-04-62

[12] A. G. Fowler and C. Gidney, Low overhead quantum computation using lattice surgery, arXiv:1808.06709 (2018).
arXiv:1808.06709

[13] A. J. Landahl and C. Ryan-Anderson, Quantum computing by color-code lattice surgery, arXiv:1407.5103 (2014).
arXiv:1407.5103

[14] Y. Li, A magic state’s fidelity can be superior to the operations that created it, New J. Phys. 17, 023037 (2015).
https://doi.org/10.1088/1367-2630/17/2/023037

[15] D. Herr, F. Nori, and S. J. Devitt, Optimization of lattice surgery is NP-hard, npj Quant. Inf. 3, 35 (2017a).
https://doi.org/10.1038/s41534-017-0035-1

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

[17] J. Haah and M. B. Hastings, Codes and Protocols for Distilling $T$, controlled-$S$, and Toffoli Gates, Quantum 2, 71 (2018).
https://doi.org/10.22331/q-2018-06-07-71

[18] S. Bravyi and J. Haah, Magic-state distillation with low overhead, Phys. Rev. A 86, 052329 (2012).
https://doi.org/10.1103/PhysRevA.86.052329

[19] C. Jones, Multilevel distillation of magic states for quantum computing, Phys. Rev. A 87, 042305 (2013a).
https://doi.org/10.1103/PhysRevA.87.042305

[20] A. G. Fowler, S. J. Devitt, and C. Jones, Surface code implementation of block code state distillation, Scientific Rep. 3, 1939 (2013).
https://doi.org/10.1038/srep01939

[21] A. G. Fowler, Time-optimal quantum computation, arXiv:1210.4626 (2012).
arXiv:1210.4626

[22] D. Gottesman, The Heisenberg representation of quantum computers, Proc. XXII Int. Coll. Group. Th. Meth. Phys. 1, 32 (1999).
arXiv:quant-ph/9807006

[23] V. Kliuchnikov, D. Maslov, and M. Mosca, Fast and efficient exact synthesis of single-qubit unitaries generated by Clifford and $T$ gates, Quantum Info. Comput. 13, 607 (2013a).
http:/​/​dl.acm.org/​citation.cfm?id=2535649.2535653

[24] V. Kliuchnikov, D. Maslov, and M. Mosca, Asymptotically optimal approximation of single qubit unitaries by Clifford and $T$ circuits using a constant number of ancillary qubits, Phys. Rev. Lett. 110, 190502 (2013b).
https://doi.org/10.1103/PhysRevLett.110.190502

[25] D. Gosset, V. Kliuchnikov, M. Mosca, and V. Russo, An algorithm for the $T$-count, arXiv:1308.4134 (2013).
arXiv:1308.4134

[26] L. E. Heyfron and E. T. Campbell, An efficient quantum compiler that reduces $T$ count, Quantum Sci. Technol. 4, 015004 (2018).
https://doi.org/10.1088/2058-9565/aad604

[27] M. Amy, D. Maslov, M. Mosca, and M. Roetteler, A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 32, 818 (2013).
https://doi.org/10.1109/TCAD.2013.2244643

[28] P. Selinger, Quantum circuits of $T$-depth one, Phys. Rev. A 87, 042302 (2013).
https://doi.org/10.1103/PhysRevA.87.042302

[29] M. Amy, D. Maslov, and M. Mosca, Polynomial-time $T$-depth optimization of Clifford+$T$ circuits via matroid partitioning, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 33, 1476 (2014).
https://doi.org/10.1109/TCAD.2014.2341953

[30] D. Litinski and F. von Oppen, Quantum computing with Majorana fermion codes, Phys. Rev. B 97, 205404 (2018).
https://doi.org/10.1103/PhysRevB.97.205404

[31] A. Lavasani and M. Barkeshli, Low overhead Clifford gates from joint measurements in surface, color, and hyperbolic codes, Phys. Rev. A 98, 052319 (2018).
https://doi.org/10.1103/PhysRevA.98.052319

[32] J. I. Hall, Notes on Coding Theory Chapter 6: Modifying Codes, https:/​/​users.math.msu.edu/​users/​jhall/​classes/​ codenotes/​Mod.pdf, accessed: 2019-01-30.
https:/​/​users.math.msu.edu/​users/​jhall/​classes/​codenotes/​Mod.pdf

[33] E. T. Campbell and M. Howard, Magic state parity-checker with pre-distilled components, Quantum 2, 56 (2018).
https://doi.org/10.22331/q-2018-03-14-56

[34] A. M. Meier, B. Eastin, and E. Knill, Magic-state distillation with the four-qubit code, Quant. Inf. Comp. 13, 195 (2013).
arXiv:1204.4221

[35] E. T. Campbell and J. O'Gorman, An efficient magic state approach to small angle rotations, Quantum Sci. Technol. 1, 015007 (2016).
https://doi.org/10.1088/2058-9565/1/1/015007

[36] D. Herr, F. Nori, and S. J. Devitt, Lattice surgery translation for quantum computation, New J. Phys. 19, 013034 (2017b).
https://doi.org/10.1088/1367-2630/aa5709

[37] A. G. Fowler and S. J. Devitt, A bridge to lower overhead quantum computation, arXiv:1209.0510 (2012).
arXiv:1209.0510

[38] C. Gidney and A. G. Fowler, Efficient magic state factories with a catalyzed $|CCZ\rangle$ to $2|T\rangle$ transformation, arXiv:1812.01238 (2018).
arXiv:1812.01238

[39] C. H. Bennett, G. Brassard, S. Popescu, B. Schumacher, J. A. Smolin, and W. K. Wootters, Purification of noisy entanglement and faithful teleportation via noisy channels, Phys. Rev. Lett. 76, 722 (1996a).
https://doi.org/10.1103/PhysRevLett.76.722

[40] C. H. Bennett, H. J. Bernstein, S. Popescu, and B. Schumacher, Concentrating partial entanglement by local operations, Phys. Rev. A 53, 2046 (1996b).
https://doi.org/10.1103/PhysRevA.53.2046

[41] C. Dickel, J. J. Wesdorp, N. K. Langford, S. Peiter, R. Sagastizabal, A. Bruno, B. Criger, F. Motzoi, and L. DiCarlo, Chip-to-chip entanglement of transmon qubits using engineered measurement fields, Phys. Rev. B 97, 064508 (2018).
https://doi.org/10.1103/PhysRevB.97.064508

[42] 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 (2018).
https://doi.org/10.1103/PhysRevLett.120.200501

[43] C. J. Axline, L. D. Burkhart, W. Pfaff, M. Zhang, K. Chou, P. Campagne-Ibarcq, P. Reinhold, L. Frunzio, S. Girvin, L. Jiang, et al., On-demand quantum state transfer and entanglement between remote microwave cavity memories, Nat. Phys. 14, 705 (2018).
https://doi.org/10.1038/s41567-018-0115-y

[44] N. J. Ross and P. Selinger, Optimal ancilla-free Clifford+T approximation of z-rotations, arXiv:1403.2975 (2014).
arXiv:1403.2975

[45] G. Duclos-Cianci and D. Poulin, Reducing the quantum-computing overhead with complex gate distillation, Phys. Rev. A 91, 042315 (2015).
https://doi.org/10.1103/PhysRevA.91.042315

[46] A. W. Harrow, B. Recht, and I. L. Chuang, Efficient discrete approximations of quantum gates, Journal of Mathematical Physics 43, 4445 (2002).
https://doi.org/10.1063/1.1495899

[47] G. Duclos-Cianci and K. M. Svore, Distillation of nonstabilizer states for universal quantum computation, Phys. Rev. A 88, 042325 (2013).
https://doi.org/10.1103/PhysRevA.88.042325

[48] A. Bocharov, Y. Gurevich, and K. M. Svore, Efficient decomposition of single-qubit gates into $v$ basis circuits, Phys. Rev. A 88, 012313 (2013).
https://doi.org/10.1103/PhysRevA.88.012313

[49] N. C. Jones, J. D. Whitfield, P. L. McMahon, M.-H. Yung, R. V. Meter, A. Aspuru-Guzik, and Y. Yamamoto, Faster quantum chemistry simulation on fault-tolerant quantum computers, New J. Phys. 14, 115023 (2012).
https://doi.org/10.1088/1367-2630/14/11/115023

[50] G. H. Low and I. L. Chuang, Hamiltonian simulation by qubitization, arXiv:1610.06546 (2016).
arXiv:1610.06546

[51] G. H. Low and I. L. Chuang, Optimal Hamiltonian simulation by quantum signal processing, Phys. Rev. Lett. 118, 010501 (2017).
https://doi.org/10.1103/PhysRevLett.118.010501

[52] R. Babbush, D. W. Berry, J. R. McClean, and H. Neven, Quantum simulation of chemistry with sublinear scaling to the continuum, arXiv:1807.09802 (2018b).
arXiv:1807.09802

[53] C. Jones, Low-overhead constructions for the fault-tolerant Toffoli gate, Phys. Rev. A 87, 022328 (2013b).
https://doi.org/10.1103/PhysRevA.87.022328

[54] C. Gidney, Halving the cost of quantum addition, Quantum 2, 74 (2018).
https://doi.org/10.22331/q-2018-06-18-74

[55] E. T. Campbell and M. Howard, Unified framework for magic state distillation and multiqubit gate synthesis with reduced resource cost, Phys. Rev. A 95, 022316 (2017).
https://doi.org/10.1103/PhysRevA.95.022316

[56] J. O'Gorman and E. T. Campbell, Quantum computation with realistic magic-state factories, Phys. Rev. A 95, 032338 (2017).
https://doi.org/10.1103/PhysRevA.95.032338

[57] K. K. Likharev and V. K. Semenov, RSFQ logic/​memory family: A new Josephson-junction technology for sub-terahertz-clock-frequency digital systems, IEEE Transactions on Applied Superconductivity 1, 3 (1991).
https://doi.org/10.1109/77.80745

[58] A. G. Fowler, S. J. Devitt, and C. Jones, Synthesis of arbitrary quantum circuits to topological assembly: Systematic, online and compact, Scientific Rep. 7, 10414 (2017).
https://doi.org/10.1038/s41598-017-10657-8

[59] A. Paler, I. Polian, K. Nemoto, and S. J. Devitt, Fault-tolerant, high-level quantum circuits: form, compilation and description, Quantum Sci. Technol. 2, 025003 (2017).
https://doi.org/10.1088/2058-9565/aa66eb

[60] L. Lao, B. van Wee, I. Ashraf, J. van Someren, N. Khammassi, K. Bertels, and C. G. Almudever, Mapping of lattice surgery-based quantum circuits on surface code architectures, Quantum Sci. Technol. 4, 015005 (2018).
https://doi.org/10.1088/2058-9565/aadd1a

[61] H. Bombin and M. A. Martin-Delgado, Topological quantum distillation, Phys. Rev. Lett. 97, 180501 (2006).
https://doi.org/10.1103/PhysRevLett.97.180501

[62] M. S. Kesselring, F. Pastawski, J. Eisert, and B. J. Brown, The boundaries and twist defects of the color code and their applications to topological quantum computation, Quantum 2, 101 (2018).
https://doi.org/10.22331/q-2018-10-19-101

[63] H. P. Nautrup, N. Friis, and H. J. Briegel, Fault-tolerant interface between quantum memories and quantum processors, Nat. Commun. 8, 1321 (2017).
https://doi.org/10.1038/s41467-017-01418-2

[64] D. Litinski and F. von Oppen, Braiding by Majorana tracking and long-range CNOT gates with color codes, Phys. Rev. B 96, 205413 (2017).
https://doi.org/10.1103/PhysRevB.96.205413

[65] IBM doubling qubits every 8 months, https:/​/​www.nextbigfuture.com/​2018/​02/​ibm-doubling-qubits-every-8-months-and-ecommerce-cryptography-at-risk-in-7-15-years.html, accessed: 2018-08-01.
https:/​/​www.nextbigfuture.com/​2018/​02/​ibm-doubling-qubits-every-8-months-and-ecommerce-cryptography-at-risk-in-7-15-years.html

Cited by

[1] Christopher Chamberland and Andrew W. Cross, "Fault-tolerant magic state preparation with flag qubits", arXiv:1811.00566 (2018).

[2] Dominic W. Berry, Craig Gidney, Mario Motta, Jarrod R. McClean, and Ryan Babbush, "Qubitization of Arbitrary Basis Quantum Chemistry by Low Rank Factorization", arXiv:1902.02134 (2019).

[3] Ian D. Kivlichan, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Wei Sun, Zhang Jiang, Nicholas Rubin, Austin Fowler, Alán Aspuru-Guzik, Ryan Babbush, and Hartmut Neven, "Improved Fault-Tolerant Quantum Simulation of Condensed-Phase Correlated Electrons via Trotterization", arXiv:1902.10673 (2019).

[4] Olivia Di Matteo, Vlad Gheorghiu, and Michele Mosca, "Fault tolerant resource estimation of quantum random-access memories", arXiv:1902.01329 (2019).

[5] Craig Gidney and Austin G. Fowler, "Efficient magic state factories with a catalyzed |CCZ> to 2|T> transformation", arXiv:1812.01238 (2018).

[6] Alexandru Paler, "SurfBraid: A concept tool for preparing and resource estimating quantum circuits protected by the surface code", arXiv:1902.02417 (2019).

[7] Guang Hao Low, Vadym Kliuchnikov, and Luke Schaeffer, "Trading T-gates for dirty qubits in state preparation and unitary synthesis", arXiv:1812.00954 (2018).

[8] Earl Campbell, Ankur Khurana, and Ashley Montanaro, "Applying quantum algorithms to constraint satisfaction problems", arXiv:1810.05582 (2018).

[9] Austin G. Fowler and Craig Gidney, "Low overhead quantum computation using lattice surgery", arXiv:1808.06709 (2018).

[10] Daniel Herr, Alexandru Paler, and Simon J. Devitt, "Time versus Hardware: Reducing Qubit Counts with a (Surface Code) Data Bus", arXiv:1902.08117 (2019).

[11] Ryan Sweke, Markus S. Kesselring, Evert P. L. van Nieuwenburg, and Jens Eisert, "Reinforcement Learning Decoders for Fault-Tolerant Quantum Computation", arXiv:1810.07207 (2018).

[12] Vlad Gheorghiu and Michele Mosca, "Benchmarking the quantum cryptanalysis of symmetric, public-key and hash-based cryptographic schemes", arXiv:1902.02332 (2019).

The above citations are from SAO/NASA ADS (last updated 2019-03-25 21:12:27). 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 2019-03-25 21:12:26).