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:
 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).
 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).
 H. Bombin, Topological order with a twist: Ising anyons from an abelian model, Phys. Rev. Lett. 105, 030403 (2010).
 C. Horsman, A. G. Fowler, S. Devitt, and R. V. Meter, Surface code quantum computing by lattice surgery, New J. Phys. 14, 123011 (2012).
 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).
 Y. Li, A magic state’s fidelity can be superior to the operations that created it, New J. Phys. 17, 023037 (2015).
 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).
 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).
 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).
 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).
 A. Lavasani and M. Barkeshli, Low overhead Clifford gates from joint measurements in surface, color, and hyperbolic codes, Phys. Rev. A 98, 052319 (2018).
 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.
 E. T. Campbell and J. O'Gorman, An efficient magic state approach to small angle rotations, Quantum Sci. Technol. 1, 015007 (2016).
 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).
 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).
 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).
 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).
 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).
 G. H. Low and I. L. Chuang, Optimal Hamiltonian simulation by quantum signal processing, Phys. Rev. Lett. 118, 010501 (2017).
 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).
 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).
 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).
 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).
 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).
 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).
 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.
 Narayanan Rengaswamy, Robert Calderbank, Swanand Kadhe, and Henry D. Pfister, "Logical Clifford Synthesis for Stabilizer Codes", arXiv:1907.00310, IEEE Transactions on Quantum Engineering 1, 1 (2020).
 Christopher Chamberland and Earl T. Campbell, "Universal Quantum Computing with Twist-Free and Temporally Encoded Lattice Surgery", PRX Quantum 3 1, 010331 (2022).
 Arne L. Grimsmo and Shruti Puri, "Quantum Error Correction with the Gottesman-Kitaev-Preskill Code", PRX Quantum 2 2, 020101 (2021).
 Hiroto Mukai, Keiichi Sakata, Simon J Devitt, Rui Wang, Yu Zhou, Yukito Nakajima, and Jaw-Shen Tsai, "Pseudo-2D superconducting quantum computing circuit for the surface code: proposal and preliminary tests", New Journal of Physics 22 4, 043013 (2020).
 Christopher Chamberland and Earl T. Campbell, "Circuit-level protocol and analysis for twist-based lattice surgery", Physical Review Research 4 2, 023090 (2022).
 Alexandre Blais, Steven M. Girvin, and William D. Oliver, "Quantum information processing and quantum optics with circuit quantum electrodynamics", Nature Physics 16 3, 247 (2020).
 Sorin Hoară, Roxana-Mariana Beiu, and Valeriu Beiu, Advances in Intelligent Systems and Computing 1243, 57 (2021) ISBN:978-3-030-53650-3.
 Alexandru Paler, Oumarou Oumarou, and Robert Basmadjian, "On the Realistic Worst-Case Analysis of Quantum Arithmetic Circuits", IEEE Transactions on Quantum Engineering 3, 1 (2022).
 Alexandru Paler and Robert Basmadjian, "Energy Cost of Quantum Circuit Optimisation: Predicting That Optimising Shor’s Algorithm Circuit Uses 1 GWh", ACM Transactions on Quantum Computing 3 1, 1 (2022).
 Bob Coecke, Dominic Horsman, Aleks Kissinger, and Quanlong Wang, "Kindergarden quantum mechanics graduates ...or how I learned to stop gluing LEGO together and love the ZX-calculus", Theoretical Computer Science 897, 1 (2022).
 Joonho Lee, Dominic W. Berry, Craig Gidney, William J. Huggins, Jarrod R. McClean, Nathan Wiebe, and Ryan Babbush, "Even More Efficient Quantum Computations of Chemistry Through Tensor Hypercontraction", PRX Quantum 2 3, 030305 (2021).
 Sam McArdle, "Learning from Physics Experiments with Quantum Computers: Applications in Muon Spectroscopy", PRX Quantum 2 2, 020349 (2021).
 Michael Vasmer and Dan E. Browne, "Three-dimensional surface codes: Transversal gates and fault-tolerant architectures", Physical Review A 100 1, 012312 (2019).
 Iskren Vankov, Daniel Mills, Petros Wallden, and Elham Kashefi, "Methods for classically simulating noisy networked quantum architectures", Quantum Science and Technology 5 1, 014001 (2020).
 Casey Duckering, Jonathan M. Baker, David I. Schuster, and Frederic T. Chong, 2020 53rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO) 173 (2020) ISBN:978-1-7281-7383-2.
 Shilin Huang, Michael Newman, and Kenneth R. Brown, "Fault-tolerant weighted union-find decoding on the toric code", Physical Review A 102 1, 012419 (2020).
 Dominic W. Berry, Craig Gidney, Mario Motta, Jarrod R. McClean, and Ryan Babbush, "Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization", Quantum 3, 208 (2019).
 Ian D. Kivlichan, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Wei Sun, Zhang Jiang, Nicholas Rubin, Austin Fowler, Alán Aspuru-Guzik, Hartmut Neven, and Ryan Babbush, "Improved Fault-Tolerant Quantum Simulation of Condensed-Phase Correlated Electrons via Trotterization", Quantum 4, 296 (2020).
 Christopher Chamberland, Kyungjoo Noh, Patricio Arrangoiz-Arriola, Earl T. Campbell, Connor T. Hann, Joseph Iverson, Harald Putterman, Thomas C. Bohdanowicz, Steven T. Flammia, Andrew Keller, Gil Refael, John Preskill, Liang Jiang, Amir H. Safavi-Naeini, Oskar Painter, and Fernando G.S.L. Brandão, "Building a Fault-Tolerant Quantum Computer Using Concatenated Cat Codes", PRX Quantum 3 1, 010329 (2022).
 Christopher Chamberland and Andrew W. Cross, "Fault-tolerant magic state preparation with flag qubits", Quantum 3, 143 (2019).
 Benjamin J. Brown and Sam Roberts, "Universal fault-tolerant measurement-based quantum computation", Physical Review Research 2 3, 033305 (2020).
 Ivan Djordjevic, "Surface-Codes-Based Quantum Communication Networks", Entropy 22 9, 1059 (2020).
 J. Eli Bourassa, Rafael N. Alexander, Michael Vasmer, Ashlesha Patil, Ilan Tzitrin, Takaya Matsuura, Daiqin Su, Ben Q. Baragiola, Saikat Guha, Guillaume Dauphinais, Krishna K. Sabapathy, Nicolas C. Menicucci, and Ish Dhand, "Blueprint for a Scalable Photonic Fault-Tolerant Quantum Computer", Quantum 5, 392 (2021).
 Sam McArdle, Suguru Endo, Alán Aspuru-Guzik, Simon C. Benjamin, and Xiao Yuan, "Quantum computational chemistry", Reviews of Modern Physics 92 1, 015003 (2020).
 Olivia Di Matteo, Vlad Gheorghiu, and Michele Mosca, "Fault-Tolerant Resource Estimation of Quantum Random-Access Memories", arXiv:1902.01329, IEEE Transactions on Quantum Engineering 1, 1 (2020).
 Jonathan M. Baker, Casey Duckering, David I. Schuster, and Frederic T. Chong, "Virtual Logical Qubits: A Compact Architecture for Fault-Tolerant Quantum Computing", IEEE Micro 41 3, 95 (2021).
 Antonio D. Corcoles, Abhinav Kandala, Ali Javadi-Abhari, Douglas T. McClure, Andrew W. Cross, Kristan Temme, Paul D. Nation, Matthias Steffen, and Jay M. Gambetta, "Challenges and Opportunities of Near-Term Quantum Computing Systems", Proceedings of the IEEE 108 8, 1338 (2020).
 John van de Wetering, "Constructing quantum circuits with global gates", New Journal of Physics 23 4, 043015 (2021).
 Tomas Jochym-O'Connor and Theodore J. Yoder, "Four-dimensional toric code with non-Clifford transversal gates", Physical Review Research 3 1, 013118 (2021).
 Alexander Erhard, Hendrik Poulsen Nautrup, Michael Meth, Lukas Postler, Roman Stricker, Martin Stadler, Vlad Negnevitsky, Martin Ringbauer, Philipp Schindler, Hans J. Briegel, Rainer Blatt, Nicolai Friis, and Thomas Monz, "Entangling logical qubits with lattice surgery", Nature 589 7841, 220 (2021).
 Mark Webber, Vincent Elfving, Sebastian Weidt, and Winfried K. Hensinger, "The impact of hardware specifications on reaching quantum advantage in the fault tolerant regime", AVS Quantum Science 4 1, 013801 (2022).
 Daniel Litinski, "Magic State Distillation: Not as Costly as You Think", Quantum 3, 205 (2019).
 Isaac H. Kim, Ye-Hua Liu, Sam Pallister, William Pol, Sam Roberts, and Eunseok Lee, "Fault-tolerant resource estimate for quantum chemical simulations: Case study on Li-ion battery electrolyte molecules", Physical Review Research 4 2, 023019 (2022).
 Jonathan M. Baker and Frederic T. Chong, "Emerging Technologies for Quantum Computing", IEEE Micro 41 5, 41 (2021).
 Alexander Cowtan, Silas Dilkes, Ross Duncan, Will Simmons, and Seyon Sivarajah, "Phase Gadget Synthesis for Shallow Circuits", Electronic Proceedings in Theoretical Computer Science 318, 213 (2020).
 Alexander Jahn and Jens Eisert, "Holographic tensor network models and quantum error correction: a topical review", Quantum Science and Technology 6 3, 033002 (2021).
 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, 2172 (2021).
 William J. Huggins, Sam McArdle, Thomas E. O’Brien, Joonho Lee, Nicholas C. Rubin, Sergio Boixo, K. Birgitta Whaley, Ryan Babbush, and Jarrod R. McClean, "Virtual Distillation for Quantum Error Mitigation", Physical Review X 11 4, 041036 (2021).
 Michael Hanks, Marta P. Estarellas, William J. Munro, and Kae Nemoto, "Effective Compression of Quantum Braided Circuits Aided by ZX-Calculus", Physical Review X 10 4, 041030 (2020).
 Yi-Hao Kang, Ye-Hong Chen, Xin Wang, Jie Song, Yan Xia, Adam Miranowicz, Shi-Biao Zheng, and Franco Nori, "Nonadiabatic geometric quantum computation with cat-state qubits via invariant-based reverse engineering", Physical Review Research 4 1, 013233 (2022).
 Niel de Beaudrap and Dominic Horsman, "The ZX calculus is a language for surface code lattice surgery", Quantum 4, 218 (2020).
 Craig Gidney and Austin G. Fowler, "Efficient magic state factories with a catalyzed|CCZ⟩to2|T⟩transformation", Quantum 3, 135 (2019).
 J. Haferkamp, D. Hangleiter, A. Bouland, B. Fefferman, J. Eisert, and J. Bermejo-Vega, "Closing Gaps of a Quantum Advantage with Short-Time Hamiltonian Dynamics", Physical Review Letters 125 25, 250501 (2020).
 Sergey Bravyi, David Gosset, Robert König, and Marco Tomamichel, "Quantum advantage with noisy shallow circuits", Nature Physics 16 10, 1040 (2020).
 Austin G. Fowler and Craig Gidney, "Low overhead quantum computation using lattice surgery", arXiv:1808.06709.
 Ryan Sweke, Markus S. Kesselring, Evert P. L. van Nieuwenburg, and Jens Eisert, "Reinforcement Learning Decoders for Fault-Tolerant Quantum Computation", arXiv:1810.07207.
 Guang Hao Low, Vadym Kliuchnikov, and Luke Schaeffer, "Trading T-gates for dirty qubits in state preparation and unitary synthesis", arXiv:1812.00954.
 Vlad Gheorghiu and Michele Mosca, "Benchmarking the quantum cryptanalysis of symmetric, public-key and hash-based cryptographic schemes", arXiv:1902.02332.
 Niel de Beaudrap, Xiaoning Bian, and Quanlong Wang, "Fast and effective techniques for T-count reduction via spider nest identities", arXiv:2004.05164.
 Alexandru Paler, "SurfBraid: A concept tool for preparing and resource estimating quantum circuits protected by the surface code", arXiv:1902.02417.
 Niel de Beaudrap, Xiaoning Bian, and Quanlong Wang, "Techniques to Reduce $\pi/4$-Parity-Phase Circuits, Motivated by the ZX Calculus", arXiv:1911.09039.
 Craig Gidney and Austin G. Fowler, "Flexible layout of surface code computations using AutoCCZ states", arXiv:1905.08916.
 Andrew J. Landahl and Benjamin C. A. Morrison, "Logical Majorana fermions for fault-tolerant quantum simulation", arXiv:2110.10280.
 Michael Vasmer and Aleksander Kubica, "Morphing quantum codes", arXiv:2112.01446.
 Alexandru Paler and Austin G. Fowler, "OpenSurgery for Topological Assemblies", arXiv:1906.07994.
 Daniel Herr, Alexandru Paler, Simon J. Devitt, and Franco Nori, "Time versus Hardware: Reducing Qubit Counts with a (Surface Code) Data Bus", arXiv:1902.08117.
The above citations are from Crossref's cited-by service (last updated successfully 2022-05-17 12:51:56) and SAO/NASA ADS (last updated successfully 2022-05-17 12:51:57). 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.