Kitaev surface code

Kitaev surface code[1][2][3]

Description

A family of abelian topological CSS stabilizer codes whose generators are few-body $X$-type and $Z$-type Pauli strings associated to the stars and plaquettes, respectively, of a cellulation of a two-dimensional surface (with a qubit located at each edge of the cellulation). Toric code often either refers to the construction on the two-dimensional torus or is an alternative name for the general construction. The construction on surfaces with boundaries is often called the planar code [4].

The original construction can be naturally extended to arbitrary $D$-dimensional manifolds [5][6]. Given a cellulation, qubits are put on $i$-dimensional faces, $X$-type stabilizers are associated with $(i-1)$-faces, while $Z$-type stabilizers are associated with $i+1$-faces. Such extensions are often called the $D$-dimensional surface or $D$-dimensional toric codes.

The stabilizers of the surface code on the 2-dimensional torus are generated by star operators $A_v$ and plaquette operators $B_p$. Each star operator is a product of four Pauli-$X$ operators on the edges adjacent to a vertex $v$ of the lattice; each plaquette operator is a product of four Pauli-$Z$ operators applied to the edges adjacent to a face, or plaquette, $p$ of the lattice (Figure I).

Figure I: Stabilizer generators and logical operators of the 2D surface code on a torus. The star operators $A_v$ and the plaquette operators $B_p$ generate the stabilizer group of the toric code. The logical operators are strings that wrap around the torus.

The two-dimensional toric code encodes two logical qubits. We denote by $\overline{X}_i,\overline{Z}_i$ the logical Pauli-$X$ and Pauli-$Z$ operator of the $i$-th logical qubit. They can are represented by strings of Pauli-$X$ operators or Pauli-$Z$ operators that wrap around the torus as shown in Figure I.

Protection

Toric code on an $L\times L$ torus is a $[[2L^2,2,L]]$ CSS code, and there exists a planar code with $[[L^2,1,L]]$ [7]. More generally, the code distance is related to the homology of the cellulation [8].

Coherent physical errors are expected to become incoherent logical errors after MWPM decoding; see corroborating numerical studies performed via the Majorana mapping [9] as well as analytical bounds [10].

Rate

Rate depends on the underlying cellulation and manifold. For general 2D manifolds, $kd^2\leq c(\log k)^2 n$ for some constant $c$ [11], meaning that (1) 2D surface codes with bounded geometry have distance scaling at most as $O(\sqrt{n})$ [12][13], and (2) surface codes with finite rate can only achieve an asymptotic minimum distance that is logarithmic in $n$. Higher-dimensional hyperbolic manifolds (see code children below) yield distances scaling more favorably. Loewner's theorem provides an upper bound for any bounded-geometry surface code [5].

Encoding

For an $L\times L$ lattice, deterministic state preparation can be done with a geometrically local unitary $O(L)$-depth circuit [14][15] or an $O(\log{L})$-depth unitary circuit with non-local two-qubit gates [16][17] (matching a lower bound in Ref. [18]).Lindbladian-based dissipative encoding for the toric code [19] that does not give a speedup relative to circuit-based encoders [20].Stabilizer measurement-based circuit of linear depth [8][21].

Transversal Gates

Transversal Pauli gates exist and are based on non-trivial loops on surface. Transversal Clifford gates can be done on folded surface codes [22].

Gates

Clifford gates can be implemented via lattice surgery [7][23][24][25], twist-based lattice surgery [26], or braiding defects [27][28][29][30]. Non-Clifford gates require magic state distillation [31], Dehn twists [32], or just-in-time decoding [33].

Decoding

Maximum-likelihood (ML) [8], which takes time of order $O(n^2)$ for independent $X,Z$ noise [34].Minimum weight perfect-matching (MWPM) [8][35] (based on work by Edmonds on finding a matching in a graph [36][37]). Pipeline MWPM [38][39] - a modification accounting for correlations between events. A modification utilizing the continuous signal obtained in the physical implementation of the stabilizer measurement (as opposed to discretizing the signal into a syndrome bit) [40]. Correlated matching modifies MWPM to include correlations between $X$ and $Z$-type errors [38]. Belief perfect matching is a combination of belief-propagation and MWPM [41].Renormalization group (RG) [42][43][44].Markov-chain Monte Carlo [45].Tensor network [34].Cellular automaton [46].Neural network [47][48][49][50].Union-find [51]. A subsequent modification utilizes the continuous signal obtained in the physical implementation of the stabilizer measurement (as opposed to discretizing the signal into a syndrome bit) [40]. Belief union find is a combination of belief-propagation and union-find [41].Decoders can be augmented with a pre-decoder [52][53], which can allow for some processing to be done inside the cryogenic environment of the quantum system [54].Sliding-window [55][56] and parallel-window [55] parallelizable decoders can be combined with many inner decoders, such as MWPM or union-find.

Fault Tolerance

Transversal (non-Clifford) CCZ gate by bringing 2D surface codes together and using just-in-time decoding [33]. Gate can be simulated by taking 2D slices out of 3D surface codes [57].

Code Capacity Threshold

Independent $X,Z$ noise: $10.31\%$ under MWPM decoding [58] (see also Ref. [34]). The threshold under ML decoding corresponds to the value of critical point of the two-dimensional random-bond Ising model on the Nishimori line [8], calculated to be $10.94 \pm 0.02\%$ in Ref. [59], $10.93(2)\%$ in Ref. [60], and estimated to be between $10.9\%$ and $11\%$ in Ref. [34].Depolarizing noise: between $17\%$ and $18.5\%$ under tensor-network decoding [34], and between $15\%$ and $16\%$ under RG [42], Markov-chain [45], or MWPM [61] decoding. The threshold under ML decoding corresponds to the value of critical point in the disordered eight-vertex Ising model, calculated to be $18.9(3)\%$ [62] (see also APS Physics viewpoint [63]).Erasure noise: $50\%$ for square tiling [64]. There is an inverse relationship between coordination number of the syndrome graph, with the threshold corresponding to a percolation transition [65].Phenomenological noise: $3.3\%$ for square tiling [66].

Threshold

$0.57\%$ for depolarizing noise on data and syndrome qubits as well initialization, gate, and measurement errors under MPWM decoding [29]. For this model, a logical qubit with a $10^{-14}$ logical error rate requires between $10^3$ to $10^4$ physical qubits and a target gate fidelity above $99.9\%$. Later work showed that arbitrarily large computations are possible for a physical error rate of approximately $10^{-4}$ [67].$0.5-2.9\%$ for various noise models [68] (see also Refs. [58][69]).

Realizations

One cycle of syndrome readout on 19-qubit planar and 24-qubit toric codes realized in two-dimensional Rydberg atomic arrays [70]. Signatures of corresponding topological phase of matter detected in superconducting circuits [71] and two-dimensional Rydberg atomic arrays [72].

Notes

Surfmap framework provides a way to stitch the surface code to various superconducting-circuit geometries by assigning each superconducting qubit to be either a physical or ancilla qubit, designing stabilizer measurement circuits, and scheduling stabilizer measurements [73].2D and 3D surface code visualization tool. Tutorials from error-correction perspective by J. Haah and condensed-matter perspective by M. Levin and C. Nayak.

Parents

Calderbank-Shor-Steane (CSS) stabilizer code
Clifford-deformed surface code (CDSC) — CDSC codes are deformations of the surface code via constant-depth Clifford circuits that may not be CSS.
Abelian topological code — When treated as ground states of the code Hamiltonian, the code states realize $\mathbb{Z}_2$ topological order, a topological phase of matter that also exists in $\mathbb{Z}_2$ lattice gauge theory [74]. Codewords correspond to ground state of the code Hamiltonian, and error operators correspond to spontaneous creation and annihilation of pairs of charges or vortices.

Children

Fractal surface code
Higher-dimensional surface code
Hyperbolic surface code
Projective-plane surface code
$[[4,2,2]]$ CSS code — $[[4,2,2]]$ code is the smallest toric code.

Cousins

Hypergraph product code — Planar (toric) code can be obtained from hypergraph product of two repetition (cyclic) codes ([75], Ex. 6).
Quantum-double code — A quantum-double model with $G=\mathbb{Z}_2$ is the surface code.
String-net code — String-net model reduces to the surface code when the category is the group $\mathbb{Z}_2$.
Majorana stabilizer code — The Majorana mapping can be used to construct efficient algorithms for simulating rounds of error correction for the surface code [9].
Color code — Color code is equivalent to surface code in several ways [76][77]. For example, the color code on a $D$-dimensional closed manifold is equivalent to multiple decoupled copies of the $D-1$-dimensional surface code.
Double-semion code — There is a logical basis for the toric and double-semion codes where each codeword is a superposition of states corresponding to all noncontractible loops of a particular homotopy type. The superposition is equal for the toric code, whereas some loops appear with a $-1$ coefficient for the double semion.
Galois-qudit topological code — Surface code has been extended to Galois qudits.
Haah cubic code — The energy of any partial implementation of code 1 is proportional to the boundary length similar to the 4D toric code, which can potentially surpress the effects of thermal errors, but it is currently an open problem.
Heavy-hexagon code — Surface code stabilizers are used to measure the Z-type stabilizers of the code.
Honeycomb code — Measurement of each check operator involves two qubits and projects the state of the two qubits to a two-dimensional subspace, which we regard as an effective qubit. These effective qubits form a surface code on a hexagonal superlattice. Electric and magnetic operators on the embedded surface code correspond to outer logical operators of the Floquet code. In fact, outer logical operators transition back and forth from magnetic to electric surface code operators under the measurement dynamics. Inspired by this code, stabilizer measurement circuits consisting of two-body measurements have been designed for the surface code [78][79].
Lifted-product (LP) code — A lifted product code for the ring $R=\mathbb{F}_2[x,y]/(x^L-1,y^L-1)$ is the toric code.
Modular-qudit surface code — The qudit surface code with $q=2$ is the surface code.
Raussendorf-Bravyi-Harrington (RBH) code — Without symmetry protection, one of 2D boundaries of the cubic RBH code is effectively a 2D toric code.
Translationally-invariant stabilizer code — Translation-invariant 2D qubit topological stabilizer codes are equivalent to several copies of the Kitaev surface code via a local constant-depth Clifford circuit [80][81][82].

References

[1]: A. Y. Kitaev, “Quantum computations: algorithms and error correction”, Russian Mathematical Surveys 52, 1191 (1997). DOI
[2]: A. Y. Kitaev, “Quantum Error Correction with Imperfect Gates”, Quantum Communication, Computing, and Measurement 181 (1997). DOI
[3]: A. Y. Kitaev, “Fault-tolerant quantum computation by anyons”, Annals of Physics 303, 2 (2003). DOI; quant-ph/9707021
[4]: S. B. Bravyi and A. Yu. Kitaev, “Quantum codes on a lattice with boundary”. quant-ph/9811052
[5]: “Z2-systolic freedom and quantum codes”, Mathematics of Quantum Computation 303 (2002). DOI
[6]: G. Zémor, “On Cayley Graphs, Surface Codes, and the Limits of Homological Coding for Quantum Error Correction”, Lecture Notes in Computer Science 259 (2009). DOI
[7]: C. Horsman et al., “Surface code quantum computing by lattice surgery”, New Journal of Physics 14, 123011 (2012). DOI; 1111.4022
[8]: E. Dennis et al., “Topological quantum memory”, Journal of Mathematical Physics 43, 4452 (2002). DOI; quant-ph/0110143
[9]: S. Bravyi et al., “Correcting coherent errors with surface codes”, npj Quantum Information 4, (2018). DOI; 1710.02270
[10]: J. K. Iverson and J. Preskill, “Coherence in logical quantum channels”, New Journal of Physics 22, 073066 (2020). DOI; 1912.04319
[11]: N. Delfosse, “Tradeoffs for reliable quantum information storage in surface codes and color codes”, 2013 IEEE International Symposium on Information Theory (2013). DOI; 1301.6588
[12]: S. Bravyi, D. Poulin, and B. Terhal, “Tradeoffs for Reliable Quantum Information Storage in 2D Systems”, Physical Review Letters 104, (2010). DOI; 0909.5200
[13]: E. Fetaya, “Bounding the distance of quantum surface codes”, Journal of Mathematical Physics 53, 062202 (2012). DOI
[14]: O. Higgott et al., “Optimal local unitary encoding circuits for the surface code”, Quantum 5, 517 (2021). DOI; 2002.00362
[15]: Yu-Jie Liu et al., “Methods for simulating string-net states and anyons on a digital quantum computer”. 2110.02020
[16]: M. Aguado and G. Vidal, “Entanglement Renormalization and Topological Order”, Physical Review Letters 100, (2008). DOI; 0712.0348
[17]: J. Joo et al., “Generating and verifying graph states for fault-tolerant topological measurement-based quantum computing in two-dimensional optical lattices”, Physical Review A 88, (2013). DOI; 1207.0253
[18]: Dorit Aharonov and Yonathan Touati, “Quantum Circuit Depth Lower Bounds For Homological Codes”. 1810.03912
[19]: J. Dengis, R. König, and F. Pastawski, “An optimal dissipative encoder for the toric code”, New Journal of Physics 16, 013023 (2014). DOI; 1310.1036
[20]: R. König and F. Pastawski, “Generating topological order: No speedup by dissipation”, Physical Review B 90, (2014). DOI; 1310.1037
[21]: J. Łodyga et al., “Simple scheme for encoding and decoding a qubit in unknown state for various topological codes”, Scientific Reports 5, (2015). DOI; 1404.2495
[22]: J. E. Moussa, “Transversal Clifford gates on folded surface codes”, Physical Review A 94, (2016). DOI; 1603.02286
[23]: D. Litinski and F. von . Oppen, “Lattice Surgery with a Twist: Simplifying Clifford Gates of Surface Codes”, Quantum 2, 62 (2018). DOI; 1709.02318
[24]: D. Litinski, “A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery”, Quantum 3, 128 (2019). DOI; 1808.02892
[25]: C. Chamberland and E. T. Campbell, “Universal Quantum Computing with Twist-Free and Temporally Encoded Lattice Surgery”, PRX Quantum 3, (2022). DOI; 2109.02746
[26]: C. Chamberland and E. T. Campbell, “Circuit-level protocol and analysis for twist-based lattice surgery”, Physical Review Research 4, (2022). DOI; 2201.05678
[27]: R. Raussendorf and J. Harrington, “Fault-Tolerant Quantum Computation with High Threshold in Two Dimensions”, Physical Review Letters 98, (2007). DOI; quant-ph/0610082
[28]: R. Raussendorf, J. Harrington, and K. Goyal, “Topological fault-tolerance in cluster state quantum computation”, New Journal of Physics 9, 199 (2007). DOI; quant-ph/0703143
[29]: A. G. Fowler et al., “Surface codes: Towards practical large-scale quantum computation”, Physical Review A 86, (2012). DOI; 1208.0928
[30]: B. J. Brown et al., “Poking Holes and Cutting Corners to Achieve Clifford Gates with the Surface Code”, Physical Review X 7, (2017). DOI; 1609.04673
[31]: D. Litinski, “Magic State Distillation: Not as Costly as You Think”, Quantum 3, 205 (2019). DOI; 1905.06903
[32]: G. Zhu, A. Lavasani, and M. Barkeshli, “Instantaneous braids and Dehn twists in topologically ordered states”, Physical Review B 102, (2020). DOI; 1806.06078
[33]: B. J. Brown, “A fault-tolerant non-Clifford gate for the surface code in two dimensions”, Science Advances 6, (2020). DOI; 1903.11634
[34]: S. Bravyi, M. Suchara, and A. Vargo, “Efficient algorithms for maximum likelihood decoding in the surface code”, Physical Review A 90, (2014). DOI; 1405.4883
[35]: Austin G. Fowler, “Minimum weight perfect matching of fault-tolerant topological quantum error correction in average $O(1)$ parallel time”. 1307.1740
[36]: J. Edmonds, “Paths, Trees, and Flowers”, Canadian Journal of Mathematics 17, 449 (1965). DOI
[37]: J. Edmonds, “Maximum matching and a polyhedron with 0,1-vertices”, Journal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics 69B, 125 (1965). DOI
[38]: Austin G. Fowler, “Optimal complexity correction of correlated errors in the surface code”. 1310.0863
[39]: Alexandru Paler and Austin G. Fowler, “Pipelined correlated minimum weight perfect matching of the surface code”. 2205.09828
[40]: Christopher A. Pattison et al., “Improved quantum error correction using soft information”. 2107.13589
[41]: Oscar Higgott et al., “Fragile boundaries of tailored surface codes and improved decoding of circuit-level noise”. 2203.04948
[42]: G. Duclos-Cianci and D. Poulin, “Fast Decoders for Topological Quantum Codes”, Physical Review Letters 104, (2010). DOI; 0911.0581
[43]: Guillaume Duclos-Cianci and David Poulin, “Fault-Tolerant Renormalization Group Decoder for Abelian Topological Codes”. 1304.6100
[44]: F. H. E. Watson, H. Anwar, and D. E. Browne, “Fast fault-tolerant decoder for qubit and qudit surface codes”, Physical Review A 92, (2015). DOI; 1411.3028
[45]: A. Hutter, J. R. Wootton, and D. Loss, “Efficient Markov chain Monte Carlo algorithm for the surface code”, Physical Review A 89, (2014). DOI; 1302.2669
[46]: M. Herold et al., “Cellular automaton decoders of topological quantum memories in the fault tolerant setting”, New Journal of Physics 19, 063012 (2017). DOI; 1511.05579
[47]: G. Torlai and R. G. Melko, “Neural Decoder for Topological Codes”, Physical Review Letters 119, (2017). DOI; 1610.04238
[48]: C. Chamberland and P. Ronagh, “Deep neural decoders for near term fault-tolerant experiments”, Quantum Science and Technology 3, 044002 (2018). DOI; 1802.06441
[49]: R. Sweke et al., “Reinforcement learning decoders for fault-tolerant quantum computation”, Machine Learning: Science and Technology 2, 025005 (2020). DOI; 1810.07207
[50]: Yosuke Ueno et al., “NEO-QEC: Neural Network Enhanced Online Superconducting Decoder for Surface Codes”. 2208.05758
[51]: N. Delfosse and N. H. Nickerson, “Almost-linear time decoding algorithm for topological codes”, Quantum 5, 595 (2021). DOI; 1709.06218
[52]: Nicolas Delfosse, “Hierarchical decoding to reduce hardware requirements for quantum computing”. 2001.11427
[53]: Samuel C. Smith, Benjamin J. Brown, and Stephen D. Bartlett, “A local pre-decoder to reduce the bandwidth and latency of quantum error correction”. 2208.04660
[54]: Gokul Subramanian Ravi et al., “Have your QEC and Bandwidth too!: A lightweight cryogenic decoder for common / trivial errors, and efficient bandwidth + execution management otherwise”. 2208.08547
[55]: Xinyu Tan et al., “Scalable surface code decoders with parallelization in time”. 2209.09219
[56]: Luka Skoric et al., “Parallel window decoding enables scalable fault tolerant quantum computation”. 2209.08552
[57]: T. R. Scruby et al., “Numerical Implementation of Just-In-Time Decoding in Novel Lattice Slices Through the Three-Dimensional Surface Code”, Quantum 6, 721 (2022). DOI; 2012.08536
[58]: C. Wang, J. Harrington, and J. Preskill, “Confinement-Higgs transition in a disordered gauge theory and the accuracy threshold for quantum memory”, Annals of Physics 303, 31 (2003). DOI; quant-ph/0207088
[59]: O. Derzhko, J. Richter, and O. Zaburannyi, “Spin-Peierls instability in the spin-1/2 transverse XX chain with Dzyaloshinskii-Moriya interaction”. cond-mat/0001014
[60]: F. Merz and J. T. Chalker, “Two-dimensional random-bond Ising model, free fermions, and the network model”, Physical Review B 65, (2002). DOI; cond-mat/0106023
[61]: D. S. Wang et al., “Threshold error rates for the toric and surface codes”. 0905.0531
[62]: H. Bombin et al., “Strong Resilience of Topological Codes to Depolarization”, Physical Review X 2, (2012). DOI; 1202.1852
[63]: D. Gottesman, “Keeping One Step Ahead of Errors”, Physics 5, (2012). DOI
[64]: T. M. Stace, S. D. Barrett, and A. C. Doherty, “Thresholds for Topological Codes in the Presence of Loss”, Physical Review Letters 102, (2009). DOI; 0904.3556
[65]: Naomi Nickerson and Héctor Bombín, “Measurement based fault tolerance beyond foliation”. 1810.09621
[66]: T. Ohno et al., “Phase structure of the random-plaquette gauge model: accuracy threshold for a toric quantum memory”, Nuclear Physics B 697, 462 (2004). DOI; quant-ph/0401101
[67]: A. G. Fowler, “Proof of Finite Surface Code Threshold for Matching”, Physical Review Letters 109, (2012). DOI; 1206.0800
[68]: M. Ohzeki, “Locations of multicritical points for spin glasses on regular lattices”, Physical Review E 79, (2009). DOI; 0811.0464
[69]: A. M. Stephens, “Fault-tolerant thresholds for quantum error correction with the surface code”, Physical Review A 89, (2014). DOI; 1311.5003
[70]: D. Bluvstein et al., “A quantum processor based on coherent transport of entangled atom arrays”, Nature 604, 451 (2022). DOI; 2112.03923
[71]: K. J. Satzinger et al., “Realizing topologically ordered states on a quantum processor”, Science 374, 1237 (2021). DOI; 2104.01180
[72]: G. Semeghini et al., “Probing topological spin liquids on a programmable quantum simulator”, Science 374, 1242 (2021). DOI; 2104.04119
[73]: Anbang Wu et al., “Mapping Surface Code to Superconducting Quantum Processors”. 2111.13729
[74]: F. J. Wegner, “Duality in Generalized Ising Models and Phase Transitions without Local Order Parameters”, Journal of Mathematical Physics 12, 2259 (1971). DOI
[75]: A. A. Kovalev and L. P. Pryadko, “Improved quantum hypergraph-product LDPC codes”, 2012 IEEE International Symposium on Information Theory Proceedings (2012). DOI; 1202.0928
[76]: A. Kubica, B. Yoshida, and F. Pastawski, “Unfolding the color code”, New Journal of Physics 17, 083026 (2015). DOI; 1503.02065
[77]: Arun B. Aloshious, Arjun Nitin Bhagoji, and Pradeep Kiran Sarvepalli, “On the Local Equivalence of 2D Color Codes and Surface Codes with Applications”. 1804.00866
[78]: R. Chao et al., “Optimization of the surface code design for Majorana-based qubits”, Quantum 4, 352 (2020). DOI; 2007.00307
[79]: Craig Gidney, “A Pair Measurement Surface Code on Pentagons”. 2206.12780
[80]: H. Bombin, G. Duclos-Cianci, and D. Poulin, “Universal topological phase of two-dimensional stabilizer codes”, New Journal of Physics 14, 073048 (2012). DOI; 1103.4606
[81]: H. Bombín, “Structure of 2D Topological Stabilizer Codes”, Communications in Mathematical Physics 327, 387 (2014). DOI; 1107.2707
[82]: J. Haah, “Algebraic Methods for Quantum Codes on Lattices”, Revista Colombiana de Matemáticas 50, 299 (2017). DOI; 1607.01387

Page edit log

Victor V. Albert (2022-09-20) — most recent
Victor V. Albert (2022-06-15)
Tony Lau (2022-04-02)
Hassan Shapourian (2022-04-01)
Victor V. Albert (2022-02-15)
Philippe Faist (2022-02-11)
Victor V. Albert (2021-11-05)
Philippe Faist (2021-11-03)
Michael Vasmer (2021-11-02)

Cite as:

“Kitaev surface code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/surface

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/quantum/qubits/topological/surface/surface/surface.yml.