Skip to content

Logical gates with the surface code

Rough overview (in words)

The ability to implement an arbitrary unitary operation, either exactly or approximately, is a prerequisite for performing quantum computation. It can be achieved with unitary gates that form a universal gate set [1, 2]. A commonly considered gate set contains two Clifford gates, the Hadamard gate \(H\) and the controlled-\(X\) gate \(CX\) (also known as the controlled NOT gate), and one non-Clifford gate, the \(T = Z^{1/4}\) gate. One can consider other non-Clifford gates, such as the Toffoli gate \(CCX\). Note that non-Clifford gates are essential for quantum computation, as any quantum circuit comprising only Clifford gates, state preparation, and measurement in the computational basis can be simulated in polynomial time on a probabilistic classical computer [3, 4].

Since we are interested in fault-tolerant quantum computation, we would like to implement a universal set of logical gates \(\overline H\), \(\overline{CX}\), and \(\overline T\) on information encoded in some QEC code, such as the surface code. We can implement these gates with a planar layout of qubits and nearest-neighbor entangling gates. To be more precise, we consider a simple architecture [5] that comprises \(N\) surface code patches, each encoding a logical qubit into the surface code with code distance \(d\), and the routing space in between; see Fig. 1(a). In such an architecture, the total number of data and ancilla qubits is \(\mathcal O(N d^2)\).

Figure 1(a): A planar layout of qubits comprises surface code patches (shaded), each using the layout depicted in Quantum error correction with the surface code Fig. 1(a) and encoding a logical qubit, and the routing space in between.

Figure 1(b): Logical Pauli measurement \(\overline{M_{XX}}\) is implemented by preparing the routing space qubits (turquoise dots) in the state \(\ket 0\) and repeatedly measuring parity checks (lightly shaded) in the routing space spanning between the two surface code patches. Other logical Pauli measurements, e.g., \(\overline{M_{ZZ}}\) and \(\overline{M_{YZ}}\), require connecting different boundaries of the two patches.

Rough overview (in math)

The logical \(\overline H\) does not pose any challenges. From a practical standpoint, it is transversal, since it can be realized by applying the Hadamard gate \(H\) to every data qubit in the surface code patch, followed by swapping of the roles of Pauli \(Z\)- and \(X\)-type parity checks in the subsequent QEC rounds. As such, the logical \(\overline H\) takes constant time and the surface code patch is effectively rotated (which may alter how subsequent operations are implemented).

The logical \(\overline{CX}\) is more challenging than the logical \(\overline H\), since it is impossible to implement it transversally with the planar layout of qubits and nearest-neighbor entangling gates shown in Fig. 1(a). Instead, one can use the following quantum circuit, where the first qubit (top wire) is the control and the third qubit (bottom wire) is the target of the logical \(\overline{CX}\) gate

It is straightforward to fault-tolerantly realize preparation of the logical state \(\ket{\overline{+}}\), logical Pauli measurement \(\overline{M_Z}\), and logical Pauli operators \(\overline{Z}\) and \(\overline{X}\). In addition, the required logical Pauli measurements \(\overline{M_{ZZ}}\) and \(\overline{M_{XX}}\) can be implemented fault-tolerantly via "lattice surgery" techniques [5]; see Fig. 1(b) for an illustration of how to realize \(\overline{M_{XX}}\). Unlike the logical \(\overline H\), logical Pauli measurements \(\overline{M_{ZZ}}\) and \(\overline{M_{XX}}\) and, subsequently, the logical \(\overline{CX}\) cannot be realized in constant time; rather, due to the need to account for measurement errors, they typically incur time overhead of \(\mathcal{O}\left( d \right)\).

The logical \(\overline T\) can be implemented using gate teleportation [6] via the following quantum circuit

Figure 2

where the logical resource state \(\ket{\overline{T}} = \left(\ket{\overline{0}} + e^{i\pi/4}\ket{\overline{1}}\right)/\sqrt{2}\), the logical gate \(\overline{S} = \overline{Z}^{\,1/2}\), and the first qubit (top wire) is the control and the second qubit (bottom wire) is the target of the logical \(\overline{CX}\) gate. Even though the logical \(\overline{S}\) is a Clifford gate, its fault-tolerant implementation with the surface code may not be effortless [7] (unless one uses nonlocal entangling gates [8, 9]) Moreover, the need to apply the logical \(\overline{S}\) conditioned on the measurement outcome of \(\overline{M_Z}\) may slow down quantum computation. For that reason, it may be beneficial to use the following quantum circuit from [10, Fig. 17(b)]

Figure 3

which is an alternative to the one in Fig. 2 that uses one additional logical qubit but requires only logical Pauli corrections, rather than logical Clifford corrections. In either case, given the logical resource state \(\ket{\overline T}\), the logical \(\overline T\) typically incurs time overhead of \(\mathcal{O}\left( d \right)\). We conclude that implementing the logical \(\overline T\) reduces to the problem of preparing the logical state \(\ket{\overline{T}}\), which, in turn, can be realized via state distillation [11, 12]; see [13] for a brief overview of state distillation.

Dominant resource cost (gates/qubits)

State distillation provides a fault-tolerant method to prepare high-fidelity logical resource states, such as the logical state \(\ket{\overline T}\). The basic idea is to convert some number of noisy resource states into fewer but, crucially, less noisy resource states. Importantly, this task can be accomplished with quantum circuits comprising only Clifford gates (together with state preparation and measurement in the computational basis) and postselection. Typically, state distillation circuits are based on some QEC code, e.g., the 15-qubit Reed–Muller code.

State distillation is often described as a resource-intensive method that contributes the most to the resource overhead of fault-tolerant quantum computation with the surface code [14] and, for that reason, many efforts have been devoted to finding possible alternatives [15, 16, 17, 18, 13]. However, recent results indicate that state distillation may not be as costly as one may think [10, 19], especially when one optimizes it for specific quantum hardware and noise that exhibits some bias [20]. In the task of estimating the ground state energy density of the Fermi–Hubbard model, state distillation of logical Toffoli resource states injected one at a time uses less than \(10\%\) of the total resources and is never a bottleneck on runtime of the quantum algorithm [21].

Oftentimes, a quantum algorithm is expressed as a quantum circuit \(\mathcal C\) comprising Clifford and \(T\) gates. Thus, by using the aforementioned logical gates \(\overline H\), \(\overline{CX}\), and \(\overline{T}\), we can fault-tolerantly implement the logical quantum circuit \(\overline{\mathcal C}\) with the surface code of code distance \(d\) and a planar layout of qubits in Fig. 1(a). However, from the perspective of reducing the resource overheads, it may be beneficial to consider a quantum circuit \(\mathcal C'\) equivalent to the circuit \(\mathcal C\), which is obtained from \(\mathcal C\) by commuting all Clifford gates to the end of \(\mathcal C\) [10]. As a result, the circuit \(\mathcal C'\) only comprises multiqubit Pauli \(\pi/8\) rotations (which are a generalization of the \(T\) gate and can be realized via, e.g., quantum circuits analogous to the one in Fig. 3. Consequently, fault-tolerant implementation of the logical circuit \(\overline{\mathcal{C}'}\) incurs the qubit overhead of \(\mathcal{O}\left( Nd^2 \right)\) and time overhead of \(\mathcal{O}\left( Md \right)\), where \(N\) and \(M\) are the number of, respectively, qubits and \(T\) gates in \(\mathcal C\). We remark that the time overhead can be reduced at the expense of increased qubit overhead—first by distilling more resource states and being able to use them faster, then by implementing them in parallel [10].

Caveats

Lattice surgery is not necessary to realize fault-tolerant quantum computation with a planar layout of qubits and nearest-neighbor gates. An alternative approach (which actually preceded the development of lattice surgery) relies on the surface code with defects and braiding [22, 23, 14, 7]. However, resource overhead estimates strongly suggest that this approach is not competitive with lattice surgery [24].

A simple architecture depicted in Fig. 1(a) can be improved in a couple ways to reduce the qubit overhead. First, it is possible to pack surface code patches more densely, resulting in more logical qubits for the given total number of qubits and target code distance [25, 10] Second, one can designate certain regions, commonly referred to as magic state factories, to solely produce resource states, such as the logical state \(\ket{\overline T}\), and optimize their design [26, 10, 19].

To simplify implementation of logical gates, one can consider other QEC codes, e.g., the three-dimensional color code [27, 28]. The gauge color code has redundant degrees of freedom, commonly referred to as gauge qubits. For different states of its gauge qubits, the gauge color code admits transversal implementation of different logical gates, which, combined, form a universal gate set (thus circumventing the Eastin–Knill theorem [29, 30]). Importantly, changing the state of gauge qubits can be done fault-tolerantly in constant time. However, to realize this construction one needs, for instance, a three-dimensional layout of qubits with nearest-neighbor gates or a planar layout of qubits with a limited number of nonlocal gates, which are more challenging to engineer compared to the simple architecture in Fig. 1(a). To achieve code distance \(d\) with the gauge color code one incurs qubit overhead of \(\mathcal{O}\left( d^3 \right)\) (compared to qubit overhead of \(\mathcal{O}\left( d^2 \right)\) for the surface code), so, similarly to single-shot QEC described in Quantum error correction with the surface code, this approach trades time overhead for qubit overhead.

Example use cases

  • Lattice surgery techniques developed for the surface code can be straightforwardly adapted to, e.g., the color code [31] or the surface code with a twist [32], leading to fault-tolerant quantum computation with potentially reduced qubit overhead. In addition, lattice surgery techniques can also be used for the fault-tolerant transfer of encoded information between arbitrary topological quantum codes [33].
  • Now, we are ready to present a rough, order-of-magnitude estimate of the resource overheads needed to realize fault-tolerant quantum computation in the architecture based on the surface code and lattice surgery. For concreteness, we consider the circuit noise of strength \(p=0.001\), where each basic operation, including state preparation, CNOT gate, and measurement, can fail with probability \(p\). Assume that we want to implement a quantum circuit \(\mathcal C\) comprising \(N=10^3\) qubits and a certain number \(M=10^{10}\) of \(T\) gates. These resource counts are in the ballpark of estimates for various quantum algorithms in the application areas of quantum chemistry, hyperref[appl:CondensedMatter]condensed matter physics, and cryptanalysis. First, following the procedure from [10], we compile \(\mathcal C\) into a new circuit \(\mathcal C'\) of depth \(M\) that comprises \(N\) qubits and \(M\) multiqubit Pauli \(\pi/8\)-rotations implemented one at a time. Since there are \(NM\) possible fault locations in the circuit \(\mathcal C'\), the error rate for each qubit of \(\mathcal C'\) should not exceed than
    \[\begin{equation} \epsilon \approx 1/(N M). \end{equation}\]

    Since each qubit of \(\mathcal C'\) is realized as a logical qubit of the surface code with distance \(d\), then its logical error rate \(p_\text{fail}\) can be approximated by

    \[\begin{equation} p_\text{fail} \approx \alpha (p/p_\text{th})^{d/2}, \end{equation}\]

    where we can crudely set \(\alpha = 0.05\) and \(p_\text{th} = 0.01\); see quantum error correction with the surface code for more details. Note that these values are empirical and depend heavily on the choice of the decoder; in our case—the belief-matching algorithm [34]. Thus, in order for the logical error rate \(p_\text{fail}\) to reach the target error rate \(\epsilon\) we need the surface code distance at least

    \[\begin{equation} d \approx \left\lceil 2 \log(\alpha N M)/\log(p_\mathrm{th}/p) \right\rceil. \end{equation}\]

    Assuming that half of all required qubits is devoted to realizing \(N\) surface code patches (each comprising \(2d^2-1\) data and ancilla qubits), with the other half used for resource state distillation and routing, we obtain that the fault-tolerant implementation of \(\mathcal C'\) incurs qubit overhead of

    \[\begin{equation} n_{\mathcal C'} \approx 4Nd^2 \end{equation}\]

    and time overhead of

    \[\begin{equation} t_{\mathcal C'} \approx Md\tau, \end{equation}\]

    where we crudely set \(\tau = 1\ \!\mu s\) to be the time needed to implement one syndrome measurement round with the superconducting circuits architecture. Finally, our order-of-magnitude resource estimate gives \(2.3\times 10^6\) physical qubits and \(67\) hours of runtime. This general approach to resource estimation has been applied to a number of specific quantum algorithms in a variety of application areas; see, e.g., [35, 36, 37, 38, 39]. These references often go beyond a back-of-the-envelope calculation and provide a more meticulous analysis that accounts for exact qubit layouts and the physical footprint of resource state distillation factories. They also pursue optimizations to how the circuit is implemented (e.g. exploiting space-time tradeoffs) in light of these considerations.

Further reading

  • An accessible overview of fault-tolerant quantum computation based on the surface code and lattice surgery can be found in [10].
  • A convenient way to describe and optimize lattice surgery operations is via the ZX calculus, which is a diagrammatic language for quantum computing [40, 41].
  • A direct comparison of the resource overhead associated with preparation of the logical resource state \(\ket{\overline T}\) using either state distillation or transversal gates (with the three-dimensional color code) can be found in [13].
  • To read about a framework for estimating resources required to realize large-scale fault-tolerant quantum computation, see [38].

Bibliography

  1. A Yu Kitaev. Quantum computations: algorithms and error correction. Russian Mathematical Surveys, 52(6):1191, 1997. doi:10.1070/RM1997v052n06ABEH002155.

  2. Michael A. Nielsen and Isaac L. Chuang. Quantum computation and quantum information. Cambridge University Press, 2000. doi:10.1017/CBO9780511976667.

  3. Daniel Gottesman. The heisenberg representation of quantum computers. arXiv: https://arxiv.org/abs/quant-ph/9807006, 1998.

  4. Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70:052328, 2004. arXiv: https://arxiv.org/abs/quant-ph/0406196. doi:10.1103/PhysRevA.70.052328.

  5. Dominic Horsman, Austin G Fowler, Simon Devitt, and Rodney Van Meter. Surface code quantum computing by lattice surgery. New Journal of Physics, 14(12):123011, 2012. arXiv: https://arxiv.org/abs/1111.4022. doi:10.1088/1367-2630/14/12/123011.

  6. Daniel Gottesman and Isaac L. Chuang. Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations. Nature, 402(6760):390–393, 1999. doi:10.1038/46503.

  7. Benjamin J. Brown, Katharina Laubscher, Markus S. Kesselring, and James R. Wootton. Poking holes and cutting corners to achieve clifford gates with the surface code. Physical Review X, 7:021029, 2017. arXiv: https://arxiv.org/abs/1609.04673. doi:10.1103/PhysRevX.7.021029.

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

  9. Jonathan E. Moussa. Transversal clifford gates on folded surface codes. Physical Review A, 94:042316, 2016. arXiv: https://arxiv.org/abs/1603.02286. doi:10.1103/PhysRevA.94.042316.

  10. Daniel Litinski. A game of surface codes: large-scale quantum computing with lattice surgery. Quantum, 3:128, 3 2019. arXiv: https://arxiv.org/abs/1808.02892. URL: https://doi.org/10.22331/q-2019-03-05-128, doi:10.22331/q-2019-03-05-128.

  11. E. Knill. Fault-tolerant postselected quantum computation: schemes. arXiv: https://arxiv.org/abs/quant-ph/0402171, 2004.

  12. Sergey Bravyi and Alexei Kitaev. Universal quantum computation with ideal clifford gates and noisy ancillas. Physical Review A, 71(2):022316, 2005. arXiv: https://arxiv.org/abs/quant-ph/0403025. doi:10.1103/physreva.71.022316.

  13. Michael E. Beverland, Aleksander Kubica, and Krysta M. Svore. Cost of universality: a comparative study of the overhead of state distillation and code switching with color codes. PRX Quantum, 2:020341, 2021. arXiv: https://arxiv.org/abs/2101.02211. doi:10.1103/PRXQuantum.2.020341.

  14. Austin G. Fowler, Matteo Mariantoni, John M. Martinis, and Andrew N. Cleland. Surface codes: towards practical large-scale quantum computation. Physical Review A, 86:032324, 9 2012. arXiv: https://arxiv.org/abs/1208.0928. URL: https://link.aps.org/doi/10.1103/PhysRevA.86.032324, doi:10.1103/PhysRevA.86.032324.

  15. Sergey Bravyi and Andrew Cross. Doubled color codes. arXiv: https://arxiv.org/abs/1509.03239, 2015.

  16. Tomas Jochym-O'Connor and Stephen D. Bartlett. Stacked codes: universal fault-tolerant quantum computation in a two-dimensional layout. Physical Review A, 93:022323, 2016. arXiv: https://arxiv.org/abs/1509.04255. doi:10.1103/PhysRevA.93.022323.

  17. Héctor Bombín. 2d quantum computation with 3d topological codes. arXiv: https://arxiv.org/abs/1810.09571, 2018.

  18. Christopher Chamberland and Andrew W. Cross. Fault-tolerant magic state preparation with flag qubits. Quantum, 3:143, 2019. arXiv: https://arxiv.org/abs/1811.00566. doi:10.22331/q-2019-05-20-143.

  19. Daniel Litinski. Magic state distillation: not as costly as you think. Quantum, 3:205, 12 2019. arXiv: https://arxiv.org/abs/1905.06903. URL: https://doi.org/10.22331/q-2019-12-02-205, doi:10.22331/q-2019-12-02-205.

  20. Daniel Litinski and Naomi Nickerson. Active volume: an architecture for efficient fault-tolerant quantum computers with limited non-local connections. arXiv: https://arxiv.org/abs/2211.15465, 2022.

  21. 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:010329, 2022. arXiv: https://arxiv.org/abs/2012.04108. doi:10.1103/PRXQuantum.3.010329.

  22. Robert Raussendorf and Jim Harrington. Fault-tolerant quantum computation with high threshold in two dimensions. Physical Review Letters, 98:190504, 2007. arXiv: https://arxiv.org/abs/quant-ph/0610082. doi:10.1103/PhysRevLett.98.190504.

  23. R Raussendorf, J Harrington, and K Goyal. Topological fault-tolerance in cluster state quantum computation. New Journal of Physics, 9(6):199–199, 2007. arXiv: https://arxiv.org/abs/quant-ph/0703143. doi:10.1088/1367-2630/9/6/199.

  24. Austin G. Fowler and Craig Gidney. Low overhead quantum computation using lattice surgery. arXiv: https://arxiv.org/abs/1808.06709, 2018.

  25. 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 Science and Technology, 4(1):015005, 2018. arXiv: https://arxiv.org/abs/1805.11127. doi:10.1088/2058-9565/aadd1a.

  26. Joe O'Gorman and Earl T. Campbell. Quantum computation with realistic magic-state factories. Physical Review A, 95:032338, 2017. arXiv: https://arxiv.org/abs/1605.07197. doi:10.1103/PhysRevA.95.032338.

  27. Héctor Bombín. Gauge color codes: optimal transversal gates and gauge fixing in topological stabilizer codes. New Journal of Physics, 17(8):083002, 2015. arXiv: https://arxiv.org/abs/1311.0879. doi:10.1088/1367-2630/17/8/083002.

  28. Aleksander Kubica and Michael E. Beverland. Universal transversal gates with color codes: a simplified approach. Physical Review A, 91:032330, 2015. arXiv: https://arxiv.org/abs/1410.0069. doi:10.1103/PhysRevA.91.032330.

  29. Bryan Eastin and Emanuel Knill. Restrictions on transversal encoded quantum gate sets. Physical Review Letters, 102(11):110502, 2009. arXiv: https://arxiv.org/abs/0811.4262. doi:10.1103/physrevlett.102.110502.

  30. Bei Zeng, Andrew Cross, and Isaac L. Chuang. Transversality versus universality for additive quantum codes. IEEE Transactions on Information Theory, 57(9):6272–6284, 2011. arXiv: https://arxiv.org/abs/0706.1382. doi:10.1109/tit.2011.2161917.

  31. Andrew J. Landahl and Ciaran Ryan-Anderson. Quantum computing by color-code lattice surgery. arXiv: https://arxiv.org/abs/1407.5103, 2014.

  32. Theodore J. Yoder and Isaac H. Kim. The surface code with a twist. Quantum, 1:2, 2017. arXiv: https://arxiv.org/abs/1612.04795. doi:10.22331/q-2017-04-25-2.

  33. Hendrik Poulsen Nautrup, Nicolai Friis, and Hans J. Briegel. Fault-tolerant interface between quantum memories and quantum processors. Nature Communications, 2017. arXiv: https://arxiv.org/abs/1609.08062. doi:10.1038/s41467-017-01418-2.

  34. Oscar Higgott, Thomas C. Bohdanowicz, Aleksander Kubica, Steven T. Flammia, and Earl T. Campbell. Improved decoding of circuit noise and fragile boundaries of tailored surface codes. Physical Review X, 13:031007, 7 2023. arXiv: https://arxiv.org/abs/2203.04948. URL: https://link.aps.org/doi/10.1103/PhysRevX.13.031007, doi:10.1103/PhysRevX.13.031007.

  35. 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. arXiv: https://arxiv.org/abs/2011.03494. doi:10.1103/PRXQuantum.2.030305.

  36. Craig Gidney and Martin Ekerå. How to factor 2048 bit rsa integers in 8 hours using 20 million noisy qubits. Quantum, 5:433, 4 2021. arXiv: https://arxiv.org/abs/1905.09749. URL: https://doi.org/10.22331/q-2021-04-15-433, doi:10.22331/q-2021-04-15-433.

  37. 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, 7 2020. arXiv: https://arxiv.org/abs/1902.10673. URL: https://doi.org/10.22331/q-2020-07-16-296, doi:10.22331/q-2020-07-16-296.

  38. Michael E. Beverland, Prakash Murali, Matthias Troyer, Krysta M. Svore, Torsten Hoeffler, Vadym Kliuchnikov, Guang Hao Low, Mathias Soeken, Aarthi Sundaram, and Alexander Vaschillo. Assessing requirements to scale to practical quantum advantage. arXiv: https://arxiv.org/abs/2211.07629, 2022. URL: http://arxiv.org/abs/2211.07629.

  39. Yuval R. Sanders, Dominic W. Berry, Pedro C.S. Costa, Louis W. Tessler, Nathan Wiebe, Craig Gidney, Hartmut Neven, and Ryan Babbush. Compilation of fault-tolerant quantum heuristics for combinatorial optimization. PRX Quantum, 1(2):020312, 11 2020. arXiv: https://arxiv.org/abs/2007.07391. doi:10.1103/PRXQuantum.1.020312.

  40. Bob Coecke and Aleks Kissinger. Picturing Quantum Processes. Cambridge University Press, 2017. doi:10.1017/9781316219317.

  41. Niel de Beaudrap and Dominic Horsman. The zx calculus is a language for surface code lattice surgery. Quantum, 4:218, 2020. arXiv: https://arxiv.org/abs/1704.08670. doi:10.22331/q-2020-01-09-218.