Kitaev surface code[1–3]  

Also known as Kitaev toric code.

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). Codewords correspond to ground states of the surface code Hamiltonian, and error operators create or annihilate pairs of anyonic charges or vortices.

Toric code often either refers to the construction on the two-dimensional torus or is an alternative name for the general construction. Twisted toric code [4; Fig. 8] refers to the construction on a torus with twisted (a.k.a. shifted) boundary conditions. The construction on surfaces with boundaries is often called the planar code [5,6]. There are two types of stabilizers one can put on edges, yielding open (a.k.a. rough) and closed (a.k.a. smooth) boundaries. A mixed boundary consists of an interleaving of the two stabilizer types [7].

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. The original planar code on a square-lattice patch with different boundary conditions on the vertical and horizontal edges is a \([[L^2+(L-1)^2,1,L]]\) CSS code [5]. Code size \(k = 2^{2g}\) for a torus of genus \(g\), and such higher genus surfaces have been investigated [8].

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

Rate

Both the planar and toric codes saturate the BPT bound, which states that \(k d^2 = O(L^2)\) for codes on a 2D lattice of length \(O(L)\).

Encoding

A depth-\(L^2\) circuit that grows the code out of a small patch on an \(L\times L\) square lattice using CNOT gates (i.e., "local moves") [11,12].Graph-state based adaptive circuit [13,14].For an \(L\times L\) lattice, deterministic state preparation can be done with a geometrically local unitary \(O(L)\)-depth circuit [15,16] or an \(O(\log{L})\)-depth unitary circuit with non-local two-qubit gates [12,17,18] (matching lower bounds [19,20]).Lindbladian-based dissipative encoding for the toric code [21] that does not give a speedup relative to circuit-based encoders [22].Stabilizer measurement-based circuit of linear depth [11,23].Any geometrically local unitary circuit on a lattice \(\Lambda\) that prepares a state whose energy density with respect to the surface code Hamiltonian is \(\epsilon\) must have depth of order \(\Omega(\min(\sqrt{|\Lambda|},1/\epsilon^{\frac{1-\alpha}{2}}))\) for any \(\alpha>0\) [24].Single-shot state preparation [25].

Transversal Gates

For the toric code, transversal logical Pauli gates correspond to Pauli strings on non-trivial loops of the torus.Transversal Clifford gates can be done on folded surface codes [26].

Gates

Clifford gates can be implemented via lattice surgery [27–30]. Non-Clifford gates require magic state distillation [31], Dehn twists [32,33], or just-in-time decoding [34]. Non-stabilizer surface-code states can be prepared by augmenting the code with a quantum double model [35]. ZX calculus [36,37] can be used to reduce the complexity of surface-code lattice surgery diagrams [38] and to reduce T-gate counts in magic-state distillation protocols [39,40]. Transversal injection method to prepare non-stabilizer states [41].

Decoding

Using data from multiple syndrome measurements prior to decoding allows for correcting syndrome measurement errors. The surface code requires order \(O(d)\) extraction rounds in order to gain a reliable estimate. Syndrome measurements are distance-preserving because syndrome extraction circuits can be designed to avoid hook errors [11].Expanding diamonds decoder correcting errors of some maximum fractal dimension [42]. The sub-threshold failure probability scales as \((p/p_{\text{th}})^{d^\beta}\), where \(p_{\text{th}}\) is the threshold and \(\beta = \log_3 2\).Minimum weight perfect-matching (MWPM) [11,43] (based on work by Edmonds on finding a matching in a graph [44,45]), which takes time up to polynomial in \(n\) for the surface code. For the case of the surface code, minimum-weight decoding reduces to MWPM [11,44,46]. MWPM solves the MPE decoding problem exactly for independent \(X\) and \(Z\) noise. MPE decoding is \(NP\)-hard in general for the surface code [47].Tensor network decoder [48] approximately solves the ML decoding problem under independent \(X,Z\) noise for the surface code and takes time of order \(O(n^2)\) [48]. ML decoding [11] is \(\#P\)-hard in general for the surface code [47].Union-find decoder [49] uses the union-find data structure [50–52], solving the MPE decoding problem exactly for low-weight errors under depolarizing noise. 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) [53]. Belief union find is a combination of belief-propagation and union-find [54]. Strictly local (as opposed to partially local) union find [55] has a worst-case runtime of order \(O(d^3)\) in the distance \(d\).Modified MWPM decoders: pipeline MWPM (accounting for correlations between events) [56,57]; modification tailored to asymmetric noise [58]; parity blossom MWPM and fusion blossom MWPM [59], 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) [53]; belief perfect matching (a combination of belief-propagation and MWPM) [54]. Combinining, or harmonizing, various decoders can improve performance [60].Renormalization group (RG) [61–63]; see Ref. [64] for the planar surface code.Linear-time ML erasure decoder [65].Markov-chain Monte Carlo [66].Cellular automaton decoders [67–69]; see also [70].Neural network [71–73], reinforcement learning [74,75], and transformer-based [76] decoders.Decoders can be augmented with a pre-decoder [77,78], which can allow for some processing to be done inside the cryogenic environment of the quantum system [79].Sliding-window [80,81] and parallel-window [80] parallelizable decoders, designed to overcome the backlog problem, can be combined with many inner decoders, such as MWPM or union-find.Modifications of BP: generalized belief propagation (GBP) [82], based on a classical version [83]; AMBP4, a quaternary version [84] of the MBP decoder [85] of complexity \(O(n\log\log n)\); blockBP, a combination of BP and tensor-network decoders [86]. See Ref. [87] for a review of BP decoders.A color-code decoder can be used for the surface code [88].Progressive-Proximity Bit-Flipping (PPBF) decoder [89].

Fault Tolerance

Transversal (non-Clifford) CCZ gate by bringing 2D surface codes together and using just-in-time decoding [34]. Gate can be simulated by taking 2D slices out of 3D surface codes [90].Homomorphic measurement protocols for arbitrary surface codes [91].Non-geometrically local connectivity can reduce overhead cost [92].Fault-tolerant post-selection framework yields magic states with low overhead [93].Framework of fault tolerance utilizing ZX calculus [36,37] that is applicable to MBQC, FBQC, and conventional computation versions of the surface code [94].Single-shot state preparation [25] and MWPM decoding [95].Syndrome extraction circuits consisting of CNOT gates and ancillary measurements [96]. Circuits can be optimized to specific architectures [97] using spacetime circuit codes and ZX calculus [36,37].Inspired by the honeycomb Floquet code, various two-body measurement schemes have been designed [98–100].

Code Capacity Threshold

Independent \(X,Z\) noise: \(p_X = 10.31\%\) under MWPM decoding [101] (see also Ref. [48]), \(9.9\%\) under BP-OSD decoding [102], and \(8.9\%\) under GBP decoding [82]. The threshold under ML decoding corresponds to the value of critical point of the two-dimensional random-bond two-body Ising model on the Nishimori line [11,103], calculated to be \(10.94 \pm 0.02\%\) in Ref. [104], \(10.93(2)\%\) in Ref. [105], \(10.9187\%\) in Ref. [106], \(10.917(3)\%\) in Ref. [107], \(10.939(6)\%\) in Ref. [108], and estimated to be between \(10.9\%\) and \(11\%\) in Ref. [48]. Above values are for one type of noise only, and the ML threshold for combined \(X\) and \(Z\) noise is \(2p_X - p_X^2 \approx 20.6\%\).Depolarizing noise: between \(17\%\) and \(18.5\%\) under tensor-network decoding [48], \(14\%\) under GBP decoding [82], \(16.5\%\) under recursive MWPM [109], between \(16\%\) and \(17.5\%\) under AMBP4 (depending on whether surface or toric code is considered) [85], and between \(15\%\) and \(16\%\) under RG [61], Markov-chain [66], or MWPM [110] 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)\%\) [111] (see also APS Physics viewpoint [112]).Erasure noise: \(50\%\) for square tiling [113]. There is an inverse relationship between coordination number of the syndrome graph, with the threshold corresponding to a percolation transition [114].Correlated noise: \(10.04(6)\%\) under mildly correlated bit-flip noise [115].

Threshold

Circuit-level noise: \(1.8\%\) under correlated CNOT-gate errors and single-qubit-gate depolarizing noise [110] with optimal decoder [116], and \(0.35\%\) under independent \(X,Z\) noise with optimal decoder [116]. Also, \(0.57\%\) for depolarizing noise on data and syndrome qubits as well initialization, gate, and measurement errors under MPWM decoding [96]. 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}\) [117]. Thresholds of \(0.5-2.9\%\) have been observed for various noise models [101,106,116,118–121]. A threshold of \(0.41\%\) when concatenated with the \([[4,2,2]]\) code [122].Phenomenological noise: \(3.3\%\) for square tiling [123], and \(2.93(2)\%\) using several rounds of syndrome measurement [101].Quasistatic phase damping and readout noise: \(2.85\%\) [124].Numerical study of concatenated thresholds of logical CNOT gates for various codes against depolarizing noise [125].The toric code has a measurement threshold of one [126].

Realizations

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

Notes

Hardware requirements for implementing surface code QEC can be reduced by utilizing structure in the time slices of the QEC circuits [130]. 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 [131].Tutorials from error-correction perspective by A. Kubica and J. Haah and condensed-matter perspective by M. Levin and C. Nayak. Review of surface code decoders [132].

Parents

Children

  • \([[4,2,2]]\) CSS code — The \([[4,2,2]]\) code is the smallest toric code. Concatenating the \([[4,2,2]]\) code with the surface code is equivalent to removing stabilizer generators from the 4.8.8 color code [122].
  • Rotated surface code — The lattice of the rotated surface code can be obtained by taking the medial graph of the surface code lattice (treated as a graph) and applying a similar procedure to construct the check operators [7,134][135; Fig. 8]. Applying the quantum Tanner transformation to the surface code yields the rotated surface code [136,137].
  • 2D hyperbolic surface code

Cousins

  • Layer code — Layer codes are combinations of constant-rate QLDPC codes with surface codes built using lattice surgery.
  • Long-range enhanced surface code (LRESC) — LRESCs reduce to planar surface codes when a trivial LDPC code is used in the hypergraph product.
  • Majorana stabilizer code — The Majorana mapping can be used to construct efficient algorithms for simulating rounds of error correction for the surface code [9].
  • Quantum-double code — A quantum-double model with \(G=\mathbb{Z}_2\) is the surface code. Non-stabilizer surface-code states can be prepared by augmenting the surface code with a quantum double model [35].
  • Hamiltonian-based code — While codewords of the surface code form ground states of the code's stabilizer Hamiltonian, they can also be ground states of other gapless Hamiltonians [138].
  • 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 [139; Appx. B].
  • Balanced product (BP) code — Twisted toric codes can be obtained from balanced products of cyclic graphs over a cyclic group [4; Fig. 8].
  • Asymmetric quantum code — The surface code on a hexagonal lattice is an asymmetric CSS code [140].
  • 2D lattice stabilizer code — Translation-invariant 2D qubit lattice stabilizer codes are equivalent to several copies of the Kitaev surface code via a local constant-depth Clifford circuit [141–143]. There exists an algorithm with which one can determine the fusion and braiding rules of a 2D translationally invariant qubit code, and decompose the given code into copies of the surface code [144].
  • Dynamical automorphism (DA) code — One of the instantaneous stabilizer codes of the 2D DA color code are stacks of toric/surface codes
  • Floquet color code — The ISG of the Floquet color code is the stabilizer group of one of nine realizations of the \(\mathbb{Z}_2\) 2D surface code.
  • X-cube Floquet code — The ISG of the X-cube Floquet code can be that of the X-cube model code or that of several decoupled surface codes.
  • Honeycomb Floquet code — Measurement of each check operator of the honeycomb Floquet code 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 the honeycomb Floquet code, various two-body measurement schemes have been designed [98–100].
  • Spacetime circuit code — Stabilizer generators of a spacetime code are called detectors in Refs. [145,146].
  • Majorana surface code — The Majorana surface code is a Majorana stabilizer analogue of the surface code.
  • Neural network code — Reinforcement learners can be used to optimize the geometry of the surface code to be more suited to a noise channel [147].
  • Raussendorf-Bravyi-Harrington (RBH) cluster-state code — The RBH state encodes the temporal gate operations on the surface code into a third spatial dimension [118,148]. In addition, one of possible 2D boundaries of the RBH code is effectively a 2D toric code.
  • Bivariate bicycle (BB) code — Bivariate bicycle codes are on par with the surface code in terms of threshold, but admit a much higher ancilla-added encoding rate at the expense of having non-geometrically local weight-six check operators.
  • 2D color code — The 2D color code is equivalent to multiple decoupled copies of the 2D surface code via a local constant-depth Clifford circuit [149–151]. Conversely, the 2D color code can condense to form the 2D surface code in nine different ways, i.e., by adding two body hopping terms along one of its three triangular directions to the stabilizer group and then taking the center of the resulting nonabelian group [152]. Both the surface and 2D color codes can be constructed from two distinct types of lattices, namely, 4-valent and 3-valent 3-colorable lattices, respectively [153].
  • Heavy-hexagon code — Surface code stabilizers are used to measure the Z-type stabilizers of the code. There are various ways to embed the surface code into the heavy-hex lattice [154].
  • Generalized five-squares code — Decoding of five-squares codes leads to a mapping of these codes to two copies of the surface code [155,156].
  • Kitaev honeycomb code — The Kitaev honeycomb model can be formulated as a qubit subsystem stabilizer code. This code can be obtained from the square-lattice surface code by gauging out the anyon \(em\) [157; Sec. 7.3]. During this process, the square lattice is effectively expanded to a hexagonal lattice [157; Fig. 12].
  • Three-fermion (3F) subsystem code — One version of the 3F subsystem code can be obtained from two copies of the square-lattice surface code by gauging out the anyons \(e_1m_1e_2\) and \(e_2m_2\) [157; Sec. 7.4].
  • Subsystem surface code
  • Fracton stabilizer code — Foliated type-I fracton phase codes can be grown by foliation, i.e., stacking copies of the 2D surface code; see [158; Eq. (D32)].
  • Double-semion stabilizer code — The double semion phase also has a realization in terms of qubits [159] that can be compared to the qubit surface code. There is a logical basis for both 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 an odd number of loops appear with a \(-1\) coefficient for the double semion.

References

[1]
A. Y. Kitaev, “Quantum computations: algorithms and error correction”, Russian Mathematical Surveys 52, 1191 (1997) DOI
[2]
A. Yu. Kitaev, “Quantum Error Correction with Imperfect Gates”, Quantum Communication, Computing, and Measurement 181 (1997) DOI
[3]
A. Yu. Kitaev, “Fault-tolerant quantum computation by anyons”, Annals of Physics 303, 2 (2003) arXiv:quant-ph/9707021 DOI
[4]
N. P. Breuckmann and J. N. Eberhardt, “Balanced Product Quantum Codes”, IEEE Transactions on Information Theory 67, 6653 (2021) arXiv:2012.09271 DOI
[5]
M. H. Freedman and D. A. Meyer, “Projective plane and planar quantum codes”, (1998) arXiv:quant-ph/9810055
[6]
S. B. Bravyi and A. Yu. Kitaev, “Quantum codes on a lattice with boundary”, (1998) arXiv:quant-ph/9811052
[7]
N. Delfosse, P. Iyer, and D. Poulin, “Generalized surface codes and packing of logical qubits”, (2016) arXiv:1606.07116
[8]
G. Rajpoot, K. Kumari, and S. R. Jain, “Quantum error correction beyond the toric code: dynamical systems meet encoding”, The European Physical Journal Special Topics (2023) arXiv:2307.04418 DOI
[9]
S. Bravyi et al., “Correcting coherent errors with surface codes”, npj Quantum Information 4, (2018) arXiv:1710.02270 DOI
[10]
J. K. Iverson and J. Preskill, “Coherence in logical quantum channels”, New Journal of Physics 22, 073066 (2020) arXiv:1912.04319 DOI
[11]
E. Dennis et al., “Topological quantum memory”, Journal of Mathematical Physics 43, 4452 (2002) arXiv:quant-ph/0110143 DOI
[12]
M. Aguado and G. Vidal, “Entanglement Renormalization and Topological Order”, Physical Review Letters 100, (2008) arXiv:0712.0348 DOI
[13]
R. Raussendorf, J. Harrington, and K. Goyal, “Topological fault-tolerance in cluster state quantum computation”, New Journal of Physics 9, 199 (2007) arXiv:quant-ph/0703143 DOI
[14]
B. J. Brown et al., “Generating topological order from a two-dimensional cluster state using a duality mapping”, New Journal of Physics 13, 065010 (2011) arXiv:1105.2111 DOI
[15]
O. Higgott et al., “Optimal local unitary encoding circuits for the surface code”, Quantum 5, 517 (2021) arXiv:2002.00362 DOI
[16]
Y.-J. Liu et al., “Methods for Simulating String-Net States and Anyons on a Digital Quantum Computer”, PRX Quantum 3, (2022) arXiv:2110.02020 DOI
[17]
R. König, B. W. Reichardt, and G. Vidal, “Exact entanglement renormalization for string-net models”, Physical Review B 79, (2009) arXiv:0806.4583 DOI
[18]
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) arXiv:1207.0253 DOI
[19]
S. Bravyi, M. B. Hastings, and F. Verstraete, “Lieb-Robinson Bounds and the Generation of Correlations and Topological Quantum Order”, Physical Review Letters 97, (2006) arXiv:quant-ph/0603121 DOI
[20]
D. Aharonov and Y. Touati, “Quantum Circuit Depth Lower Bounds For Homological Codes”, (2018) arXiv:1810.03912
[21]
J. Dengis, R. König, and F. Pastawski, “An optimal dissipative encoder for the toric code”, New Journal of Physics 16, 013023 (2014) arXiv:1310.1036 DOI
[22]
R. König and F. Pastawski, “Generating topological order: No speedup by dissipation”, Physical Review B 90, (2014) arXiv:1310.1037 DOI
[23]
J. Łodyga et al., “Simple scheme for encoding and decoding a qubit in unknown state for various topological codes”, Scientific Reports 5, (2015) arXiv:1404.2495 DOI
[24]
A. Tikku and I. H. Kim, “Circuit depth versus energy in topologically ordered systems”, (2022) arXiv:2210.06796
[25]
S. Bravyi et al., “Quantum advantage with noisy shallow circuits”, Nature Physics 16, 1040 (2020) arXiv:1904.01502 DOI
[26]
J. E. Moussa, “Transversal Clifford gates on folded surface codes”, Physical Review A 94, (2016) arXiv:1603.02286 DOI
[27]
D. Horsman et al., “Surface code quantum computing by lattice surgery”, New Journal of Physics 14, 123011 (2012) arXiv:1111.4022 DOI
[28]
D. Litinski and F. von Oppen, “Lattice Surgery with a Twist: Simplifying Clifford Gates of Surface Codes”, Quantum 2, 62 (2018) arXiv:1709.02318 DOI
[29]
D. Litinski, “A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery”, Quantum 3, 128 (2019) arXiv:1808.02892 DOI
[30]
C. Chamberland and E. T. Campbell, “Universal Quantum Computing with Twist-Free and Temporally Encoded Lattice Surgery”, PRX Quantum 3, (2022) arXiv:2109.02746 DOI
[31]
D. Litinski, “Magic State Distillation: Not as Costly as You Think”, Quantum 3, 205 (2019) arXiv:1905.06903 DOI
[32]
N. P. Breuckmann et al., “Hyperbolic and semi-hyperbolic surface codes for quantum storage”, Quantum Science and Technology 2, 035007 (2017) arXiv:1703.00590 DOI
[33]
G. Zhu, A. Lavasani, and M. Barkeshli, “Instantaneous braids and Dehn twists in topologically ordered states”, Physical Review B 102, (2020) arXiv:1806.06078 DOI
[34]
B. J. Brown, “A fault-tolerant non-Clifford gate for the surface code in two dimensions”, Science Advances 6, (2020) arXiv:1903.11634 DOI
[35]
K. Laubscher, D. Loss, and J. R. Wootton, “Universal quantum computation in the surface code using non-Abelian islands”, Physical Review A 100, (2019) arXiv:1811.06738 DOI
[36]
B. Coecke and R. Duncan, “Interacting Quantum Observables”, Automata, Languages and Programming 298 DOI
[37]
B. Coecke and R. Duncan, “Interacting quantum observables: categorical algebra and diagrammatics”, New Journal of Physics 13, 043016 (2011) arXiv:0906.4725 DOI
[38]
N. de Beaudrap and D. Horsman, “The ZX calculus is a language for surface code lattice surgery”, Quantum 4, 218 (2020) arXiv:1704.08670 DOI
[39]
C. Gidney and A. G. Fowler, “Efficient magic state factories with a catalyzed|CCZ⟩to2|T⟩transformation”, Quantum 3, 135 (2019) arXiv:1812.01238 DOI
[40]
C. Gidney and A. G. Fowler, “Flexible layout of surface code computations using AutoCCZ states”, (2019) arXiv:1905.08916
[41]
J. Gavriel et al., “Transversal Injection: A method for direct encoding of ancilla states for non-Clifford gates using stabiliser codes”, (2022) arXiv:2211.10046
[42]
Andrew Landahl, private communication, 2023
[43]
A. G. Fowler, “Minimum weight perfect matching of fault-tolerant topological quantum error correction in average \(O(1)\) parallel time”, (2014) arXiv:1307.1740
[44]
J. Edmonds, “Paths, Trees, and Flowers”, Canadian Journal of Mathematics 17, 449 (1965) DOI
[45]
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
[46]
F. Barahona et al., “Morphology of ground states of two-dimensional frustration model”, Journal of Physics A: Mathematical and General 15, 673 (1982) DOI
[47]
A. Fischer and A. Miyake, “Hardness results for decoding the surface code with Pauli noise”, (2024) arXiv:2309.10331
[48]
S. Bravyi, M. Suchara, and A. Vargo, “Efficient algorithms for maximum likelihood decoding in the surface code”, Physical Review A 90, (2014) arXiv:1405.4883 DOI
[49]
N. Delfosse and N. H. Nickerson, “Almost-linear time decoding algorithm for topological codes”, Quantum 5, 595 (2021) arXiv:1709.06218 DOI
[50]
B. A. Galler and M. J. Fisher, “An improved equivalence algorithm”, Communications of the ACM 7, 301 (1964) DOI
[51]
J. E. Hopcroft and J. D. Ullman, “Set Merging Algorithms”, SIAM Journal on Computing 2, 294 (1973) DOI
[52]
R. E. Tarjan and J. van Leeuwen, “Worst-case Analysis of Set Union Algorithms”, Journal of the ACM 31, 245 (1984) DOI
[53]
C. A. Pattison et al., “Improved quantum error correction using soft information”, (2021) arXiv:2107.13589
[54]
O. Higgott et al., “Improved decoding of circuit noise and fragile boundaries of tailored surface codes”, (2023) arXiv:2203.04948
[55]
T. Chan and S. C. Benjamin, “Actis: A Strictly Local Union–Find Decoder”, Quantum 7, 1183 (2023) arXiv:2305.18534 DOI
[56]
A. G. Fowler, “Optimal complexity correction of correlated errors in the surface code”, (2013) arXiv:1310.0863
[57]
A. Paler and A. G. Fowler, “Pipelined correlated minimum weight perfect matching of the surface code”, Quantum 7, 1205 (2023) arXiv:2205.09828 DOI
[58]
X. Xu et al., “High-Threshold Code for Modular Hardware With Asymmetric Noise”, Physical Review Applied 12, (2019) arXiv:1812.01505 DOI
[59]
Y. Wu and L. Zhong, “Fusion Blossom: Fast MWPM Decoders for QEC”, (2023) arXiv:2305.08307
[60]
N. Shutty, M. Newman, and B. Villalonga, “Efficient near-optimal decoding of the surface code through ensembling”, (2024) arXiv:2401.12434
[61]
G. Duclos-Cianci and D. Poulin, “Fast Decoders for Topological Quantum Codes”, Physical Review Letters 104, (2010) arXiv:0911.0581 DOI
[62]
G. Duclos-Cianci and D. Poulin, “Fault-Tolerant Renormalization Group Decoder for Abelian Topological Codes”, (2013) arXiv:1304.6100
[63]
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) arXiv:1411.3028 DOI
[64]
J. Wootton, “A Simple Decoder for Topological Codes”, Entropy 17, 1946 (2015) arXiv:1310.2393 DOI
[65]
N. Delfosse and G. Zémor, “Linear-time maximum likelihood decoding of surface codes over the quantum erasure channel”, Physical Review Research 2, (2020) arXiv:1703.01517 DOI
[66]
A. Hutter, J. R. Wootton, and D. Loss, “Efficient Markov chain Monte Carlo algorithm for the surface code”, Physical Review A 89, (2014) arXiv:1302.2669 DOI
[67]
J. W. Harrington, Analysis of Quantum Error-Correcting Codes: Symplectic Lattice Codes and Toric Codes, California Institute of Technology, 2004 DOI
[68]
M. Herold et al., “Cellular-automaton decoders for topological quantum memories”, npj Quantum Information 1, (2015) arXiv:1406.2338 DOI
[69]
M. Herold et al., “Cellular automaton decoders of topological quantum memories in the fault tolerant setting”, New Journal of Physics 19, 063012 (2017) arXiv:1511.05579 DOI
[70]
C.-E. Bardyn and T. Karzig, “Exponential lifetime improvement in topological quantum memories”, Physical Review B 94, (2016) arXiv:1512.04528 DOI
[71]
G. Torlai and R. G. Melko, “Neural Decoder for Topological Codes”, Physical Review Letters 119, (2017) arXiv:1610.04238 DOI
[72]
C. Chamberland and P. Ronagh, “Deep neural decoders for near term fault-tolerant experiments”, Quantum Science and Technology 3, 044002 (2018) arXiv:1802.06441 DOI
[73]
Y. Ueno et al., “NEO-QEC: Neural Network Enhanced Online Superconducting Decoder for Surface Codes”, (2022) arXiv:2208.05758
[74]
R. Sweke et al., “Reinforcement learning decoders for fault-tolerant quantum computation”, Machine Learning: Science and Technology 2, 025005 (2020) arXiv:1810.07207 DOI
[75]
E. S. Matekole et al., “Decoding surface codes with deep reinforcement learning and probabilistic policy reuse”, (2022) arXiv:2212.11890
[76]
H. Wang et al., “Transformer-QEC: Quantum Error Correction Code Decoding with Transferable Transformers”, (2023) arXiv:2311.16082
[77]
N. Delfosse, “Hierarchical decoding to reduce hardware requirements for quantum computing”, (2020) arXiv:2001.11427
[78]
S. C. Smith, B. J. Brown, and S. D. Bartlett, “Local Predecoder to Reduce the Bandwidth and Latency of Quantum Error Correction”, Physical Review Applied 19, (2023) arXiv:2208.04660 DOI
[79]
G. S. Ravi et al., “Better Than Worst-Case Decoding for Quantum Error Correction”, (2022) arXiv:2208.08547
[80]
X. Tan et al., “Scalable surface code decoders with parallelization in time”, (2022) arXiv:2209.09219
[81]
L. Skoric et al., “Parallel window decoding enables scalable fault tolerant quantum computation”, (2023) arXiv:2209.08552
[82]
J. Old and M. Rispler, “Generalized Belief Propagation Algorithms for Decoding of Surface Codes”, Quantum 7, 1037 (2023) arXiv:2212.03214 DOI
[83]
J. S. Yedidia, W. T. Freeman, and Y. Weiss, Generalized belief propagation, in NIPS, Vol. 13 (2000) pp. 689–695.
[84]
K.-Y. Kuo and C.-Y. Lai, “Comparison of 2D topological codes and their decoding performances”, 2022 IEEE International Symposium on Information Theory (ISIT) (2022) arXiv:2202.06612 DOI
[85]
K.-Y. Kuo and C.-Y. Lai, “Exploiting degeneracy in belief propagation decoding of quantum codes”, npj Quantum Information 8, (2022) arXiv:2104.13659 DOI
[86]
A. Kaufmann and I. Arad, “A blockBP decoder for the surface code”, (2024) arXiv:2402.04834
[87]
H. D. Pfister et al., “Belief Propagation for Classical and Quantum Systems: Overview and Recent Results”, IEEE BITS the Information Theory Magazine 1 (2023) DOI
[88]
A. Benhemou et al., “Minimising surface-code failures using a color-code decoder”, (2023) arXiv:2306.16476
[89]
M. Pacenti et al., “Progressive-Proximity Bit-Flipping for Decoding Surface Codes”, (2024) arXiv:2402.15924
[90]
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) arXiv:2012.08536 DOI
[91]
S. Huang, T. Jochym-O’Connor, and T. J. Yoder, “Homomorphic Logical Measurements”, (2022) arXiv:2211.03625
[92]
D. Litinski and N. Nickerson, “Active volume: An architecture for efficient fault-tolerant quantum computers with limited non-local connections”, (2022) arXiv:2211.15465
[93]
H. Bombín et al., “Fault-Tolerant Postselection for Low-Overhead Magic State Preparation”, PRX Quantum 5, (2024) arXiv:2212.00813 DOI
[94]
H. Bombin et al., “Unifying flavors of fault tolerance with the ZX calculus”, (2023) arXiv:2303.08829
[95]
S. H. Choe and R. Koenig, “Long-range data transmission in a fault-tolerant quantum bus architecture”, (2022) arXiv:2209.09774
[96]
A. G. Fowler et al., “Surface codes: Towards practical large-scale quantum computation”, Physical Review A 86, (2012) arXiv:1208.0928 DOI
[97]
M. McEwen, D. Bacon, and C. Gidney, “Relaxing Hardware Requirements for Surface Code Circuits using Time-dynamics”, Quantum 7, 1172 (2023) arXiv:2302.02192 DOI
[98]
R. Chao et al., “Optimization of the surface code design for Majorana-based qubits”, Quantum 4, 352 (2020) arXiv:2007.00307 DOI
[99]
C. Gidney, “A Pair Measurement Surface Code on Pentagons”, Quantum 7, 1156 (2023) arXiv:2206.12780 DOI
[100]
L. Grans-Samuelsson et al., “Improved Pairwise Measurement-Based Surface Code”, (2023) arXiv:2310.12981
[101]
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) arXiv:quant-ph/0207088 DOI
[102]
J. Roffe et al., “Decoding across the quantum low-density parity-check code landscape”, Physical Review Research 2, (2020) arXiv:2005.07016 DOI
[103]
H. Nishimori, “Geometry-Induced Phase Transition in the ±JIsing Model”, Journal of the Physical Society of Japan 55, 3305 (1986) DOI
[104]
A. Honecker, M. Picco, and P. Pujol, “Universality Class of the Nishimori Point in the 2D±JRandom-Bond Ising Model”, Physical Review Letters 87, (2001) arXiv:cond-mat/0010143 DOI
[105]
F. Merz and J. T. Chalker, “Two-dimensional random-bond Ising model, free fermions, and the network model”, Physical Review B 65, (2002) arXiv:cond-mat/0106023 DOI
[106]
M. Ohzeki, “Locations of multicritical points for spin glasses on regular lattices”, Physical Review E 79, (2009) arXiv:0811.0464 DOI
[107]
F. Parisen Toldin, A. Pelissetto, and E. Vicari, “Strong-Disorder Paramagnetic-Ferromagnetic Fixed Point in the Square-Lattice ±J Ising Model”, Journal of Statistical Physics 135, 1039 (2009) arXiv:0811.2101 DOI
[108]
S. L. A. de Queiroz, “Location and properties of the multicritical point in the Gaussian and±JIsing spin glasses”, Physical Review B 79, (2009) arXiv:0902.4153 DOI
[109]
A. deMarti iOlius et al., “Performance enhancement of surface codes via recursive minimum-weight perfect-match decoding”, Physical Review A 108, (2023) arXiv:2212.11632 DOI
[110]
D. S. Wang et al., “Threshold error rates for the toric and surface codes”, (2009) arXiv:0905.0531
[111]
H. Bombin et al., “Strong Resilience of Topological Codes to Depolarization”, Physical Review X 2, (2012) arXiv:1202.1852 DOI
[112]
D. Gottesman, “Keeping One Step Ahead of Errors”, Physics 5, (2012) DOI
[113]
T. M. Stace, S. D. Barrett, and A. C. Doherty, “Thresholds for Topological Codes in the Presence of Loss”, Physical Review Letters 102, (2009) arXiv:0904.3556 DOI
[114]
N. Nickerson and H. Bombín, “Measurement based fault tolerance beyond foliation”, (2018) arXiv:1810.09621
[115]
C. T. Chubb and S. T. Flammia, “Statistical mechanical models for quantum codes with correlated noise”, Annales de l’Institut Henri Poincaré D 8, 269 (2021) arXiv:1809.10704 DOI
[116]
B. Heim, K. M. Svore, and M. B. Hastings, “Optimal Circuit-Level Decoding for Surface Codes”, (2016) arXiv:1609.06373
[117]
A. G. Fowler, “Proof of Finite Surface Code Threshold for Matching”, Physical Review Letters 109, (2012) arXiv:1206.0800 DOI
[118]
R. Raussendorf and J. Harrington, “Fault-Tolerant Quantum Computation with High Threshold in Two Dimensions”, Physical Review Letters 98, (2007) arXiv:quant-ph/0610082 DOI
[119]
A. G. Fowler, A. M. Stephens, and P. Groszkowski, “High-threshold universal quantum computation on the surface code”, Physical Review A 80, (2009) arXiv:0803.0272 DOI
[120]
D. S. Wang, A. G. Fowler, and L. C. L. Hollenberg, “Surface code quantum computing with error rates over 1%”, Physical Review A 83, (2011) arXiv:1009.3686 DOI
[121]
A. M. Stephens, “Fault-tolerant thresholds for quantum error correction with the surface code”, Physical Review A 89, (2014) arXiv:1311.5003 DOI
[122]
B. Criger and B. Terhal, “Noise thresholds for the [4,2,2]-concatenated toric code”, Quantum Information and Computation 16, 1261 (2016) arXiv:1604.04062 DOI
[123]
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) arXiv:quant-ph/0401101 DOI
[124]
D. Pataki et al., “Coherent errors in stabilizer codes caused by quasistatic phase damping”, (2024) arXiv:2401.04530
[125]
A. W. Cross, D. P. DiVincenzo, and B. M. Terhal, “A comparative code study for quantum fault-tolerance”, (2009) arXiv:0711.1556
[126]
D. Lee and B. Yoshida, “Randomly Monitored Quantum Codes”, (2024) arXiv:2402.00145
[127]
D. Bluvstein et al., “A quantum processor based on coherent transport of entangled atom arrays”, Nature 604, 451 (2022) arXiv:2112.03923 DOI
[128]
K. J. Satzinger et al., “Realizing topologically ordered states on a quantum processor”, Science 374, 1237 (2021) arXiv:2104.01180 DOI
[129]
G. Semeghini et al., “Probing topological spin liquids on a programmable quantum simulator”, Science 374, 1242 (2021) arXiv:2104.04119 DOI
[130]
A. Goswami, M. Mhalla, and V. Savin, “Fault-Tolerant Preparation of Quantum Polar Codes Encoding One Logical Qubit”, (2023) arXiv:2209.06673
[131]
A. Wu et al., “Mapping Surface Code to Superconducting Quantum Processors”, (2021) arXiv:2111.13729
[132]
A. deMarti iOlius et al., “Decoding algorithms for surface codes”, (2024) arXiv:2307.14989
[133]
A. A. Kovalev and L. P. Pryadko, “Improved quantum hypergraph-product LDPC codes”, 2012 IEEE International Symposium on Information Theory Proceedings (2012) arXiv:1202.0928 DOI
[134]
H. Bombin and M. A. Martin-Delgado, “Optimal resources for topological two-dimensional stabilizer codes: Comparative study”, Physical Review A 76, (2007) arXiv:quant-ph/0703272 DOI
[135]
R. Sarkar and T. J. Yoder, “A graph-based formalism for surface codes and twists”, (2023) arXiv:2101.09349
[136]
Nikolas P. Breuckmann, private communication, 2022
[137]
Anthony Leverrier, Mapping the toric code to the rotated toric code, 2022.
[138]
C. Fernández-González et al., “Gapless Hamiltonians for the Toric Code Using the Projected Entangled Pair State Formalism”, Physical Review Letters 109, (2012) arXiv:1111.5817 DOI
[139]
P. Panteleev and G. Kalachev, “Asymptotically Good Quantum and Locally Testable Classical LDPC Codes”, (2022) arXiv:2111.03654
[140]
C. D. de Albuquerque et al., “Euclidean and Hyperbolic Asymmetric Topological Quantum Codes”, (2021) arXiv:2105.01144
[141]
H. Bombin, G. Duclos-Cianci, and D. Poulin, “Universal topological phase of two-dimensional stabilizer codes”, New Journal of Physics 14, 073048 (2012) arXiv:1103.4606 DOI
[142]
H. Bombín, “Structure of 2D Topological Stabilizer Codes”, Communications in Mathematical Physics 327, 387 (2014) arXiv:1107.2707 DOI
[143]
J. Haah, “Algebraic Methods for Quantum Codes on Lattices”, Revista Colombiana de Matemáticas 50, 299 (2017) arXiv:1607.01387 DOI
[144]
Z. Liang et al., “Extracting topological orders of generalized Pauli stabilizer codes in two dimensions”, (2023) arXiv:2312.11170
[145]
C. Gidney, “Stim: a fast stabilizer circuit simulator”, Quantum 5, 497 (2021) arXiv:2103.02202 DOI
[146]
N. Delfosse and A. Paetznick, “Spacetime codes of Clifford circuits”, (2023) arXiv:2304.05943
[147]
H. P. Nautrup et al., “Optimizing Quantum Error Correction Codes with Reinforcement Learning”, Quantum 3, 215 (2019) arXiv:1812.08451 DOI
[148]
R. Raussendorf, J. Harrington, and K. Goyal, “A fault-tolerant one-way quantum computer”, Annals of Physics 321, 2242 (2006) arXiv:quant-ph/0510135 DOI
[149]
B. Yoshida, “Classification of quantum phases and topology of logical operators in an exactly solved model of quantum codes”, Annals of Physics 326, 15 (2011) arXiv:1007.4601 DOI
[150]
A. Kubica, B. Yoshida, and F. Pastawski, “Unfolding the color code”, New Journal of Physics 17, 083026 (2015) arXiv:1503.02065 DOI
[151]
A. B. Aloshious, A. N. Bhagoji, and P. K. Sarvepalli, “On the Local Equivalence of 2D Color Codes and Surface Codes with Applications”, (2018) arXiv:1804.00866
[152]
M. S. Kesselring et al., “Anyon Condensation and the Color Code”, PRX Quantum 5, (2024) arXiv:2212.00042 DOI
[153]
J. T. Anderson, “Homological Stabilizer Codes”, (2011) arXiv:1107.3502
[154]
C. Benito et al., “Comparative study of quantum error correction strategies for the heavy-hexagonal lattice”, (2024) arXiv:2402.02185
[155]
M. Suchara, S. Bravyi, and B. Terhal, “Constructions and noise threshold of topological subsystem codes”, Journal of Physics A: Mathematical and Theoretical 44, 155301 (2011) arXiv:1012.0425 DOI
[156]
V. V. Gayatri and P. K. Sarvepalli, “Decoding Algorithms for Hypergraph Subsystem Codes and Generalized Subsystem Surface Codes”, (2018) arXiv:1805.12542
[157]
T. D. Ellison et al., “Pauli topological subsystem codes from Abelian anyon theories”, Quantum 7, 1137 (2023) arXiv:2211.03798 DOI
[158]
A. Dua et al., “Sorting topological stabilizer models in three dimensions”, Physical Review B 100, (2019) arXiv:1908.08049 DOI
[159]
M. A. Levin and X.-G. Wen, “String-net condensation: A physical mechanism for topological phases”, Physical Review B 71, (2005) arXiv:cond-mat/0404617 DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: surface

Cite as:
“Kitaev surface code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/surface
BibTeX:
@incollection{eczoo_surface, title={Kitaev surface code}, booktitle={The Error Correction Zoo}, year={2023}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/surface} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/surface

Cite as:

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

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/quantum/qubits/stabilizer/topological/surface/2d_surface/surface/surface.yml.