"Non UBC"@en . "DSpace"@en . "University of British Columbia. Department of Physics and Astronomy"@en . "Workshop on Quantum Algorithms, Computational Models and Foundations of Quantum Mechanics"@en . "Pacific Institute for the Mathematical Sciences"@en . "Summer School on Quantum Information (10th : 2010 : Vancouver, B.C.)"@en . "Duclos-Cianci, Guillaume"@en . "2016-11-22T14:05:24"@en . "2010-07-25"@en . "Topological quantum computation and topological error correcting codes attracted a lot of interest recently because they require realistic nearest neighbors couplings and, by encoding the information in non-local topological degrees of freedom, they offer a very high resilience to local noise. I will present a family of algorithms, combining real-space renormalization methods and belief propagation, to estimate the free energy of a topologically ordered system in the presence of defects (Phys. Rev. Lett. 104, 050504 (2010)). Such an algorithm is needed to preserve the quantum information stored in the ground space of a topologically ordered system and to decode topological error-correcting codes. For a system of linear size L, our algorithm runs in time log L compared to L^6 needed for the minimum-weight perfect matching algorithm previously used in this context and achieves a higher depolarizing error threshold (16.5% vs 15.5%). I will introduce the intuitions behind the m! ethod and present new developments."@en . "https://circle.library.ubc.ca/rest/handle/2429/30068?expand=metadata"@en . "Fast Decoders for Topological Quantum Codes Fast Decoders for Topological Quantum Codes Guillaume Duclos-Cianci1 David Poulin1 1De\u00CC\u0081partement de Physique, Universite\u00CC\u0081 de Sherbrooke, Qc, Ca July 25th, 2010 Workshop on Quantum Algorithms, Computational Models, and Foundations of Quantum Mechanics University of British Columbia, Vancouver, Ca Fast Decoders for Topological Quantum Codes Motivation Topological Codes Logical subspace \u00E2\u0086\u0092 linked to the topology of the system Operators highly non-local \u00E2\u0086\u0092 tailored to resist local noise Error correction requires local measurements and operations Kitaev\u00E2\u0080\u0099s toric code \u00E2\u0086\u0092 useful toy model Quantum error-correction (QEC) \u00E2\u0086\u0092 fast decoding algorithms Fast Decoders for Topological Quantum Codes Motivation Topological Codes Logical subspace \u00E2\u0086\u0092 linked to the topology of the system Operators highly non-local \u00E2\u0086\u0092 tailored to resist local noise Error correction requires local measurements and operations Kitaev\u00E2\u0080\u0099s toric code \u00E2\u0086\u0092 useful toy model Quantum error-correction (QEC) \u00E2\u0086\u0092 fast decoding algorithms Fast Decoders for Topological Quantum Codes Motivation Topological Codes Logical subspace \u00E2\u0086\u0092 linked to the topology of the system Operators highly non-local \u00E2\u0086\u0092 tailored to resist local noise Error correction requires local measurements and operations Kitaev\u00E2\u0080\u0099s toric code \u00E2\u0086\u0092 useful toy model Quantum error-correction (QEC) \u00E2\u0086\u0092 fast decoding algorithms Fast Decoders for Topological Quantum Codes Motivation Topological Codes Logical subspace \u00E2\u0086\u0092 linked to the topology of the system Operators highly non-local \u00E2\u0086\u0092 tailored to resist local noise Error correction requires local measurements and operations Kitaev\u00E2\u0080\u0099s toric code \u00E2\u0086\u0092 useful toy model Quantum error-correction (QEC) \u00E2\u0086\u0092 fast decoding algorithms Fast Decoders for Topological Quantum Codes Motivation Topological Codes Logical subspace \u00E2\u0086\u0092 linked to the topology of the system Operators highly non-local \u00E2\u0086\u0092 tailored to resist local noise Error correction requires local measurements and operations Kitaev\u00E2\u0080\u0099s toric code \u00E2\u0086\u0092 useful toy model Quantum error-correction (QEC) \u00E2\u0086\u0092 fast decoding algorithms Fast Decoders for Topological Quantum Codes Motivation 1 Kitaev\u00E2\u0080\u0099s Toric Code 2 Concatenation 3 Topological Codes Decoding Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code 1 Kitaev\u00E2\u0080\u0099s Toric Code Stabilizer generators Logical Operators Topology 2 Concatenation 3 Topological Codes Decoding Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Stabilizer generators Stabilizer Generators Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Stabilizer generators Lattice l l 2D square lattice Periodic boundary conditions Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Stabilizer generators Lattice l l 2D square lattice Periodic boundary conditions Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Stabilizer generators Lattice + Qubits l l 2D square lattice Periodic boundary conditions A qubit per edge \u00E2\u0087\u0092 2`2 qubits Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Stabilizer generators Lattice + Qubits l l 2D square lattice Periodic boundary conditions A qubit per edge \u00E2\u0087\u0092 2`2 qubits Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Stabilizer generators Lattice + Qubits l l 2D square lattice Periodic boundary conditions A qubit per edge \u00E2\u0087\u0092 2`2 qubits Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Stabilizer generators Lattice + Qubits l l 2D square lattice Periodic boundary conditions A qubit per edge \u00E2\u0087\u0092 2`2 qubits Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Stabilizer generators Stabilizer Generators X X X Z Z Z Z X Site (vertex) operator : As = \u00E2\u0088\u008F i\u00E2\u0088\u0088v(s)Xi Plaquette operator : Bp = \u00E2\u0088\u008F i\u00E2\u0088\u0088v(p) Zi `2 site and plaquette operators Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Stabilizer generators Stabilizer Generators X X X Z Z Z Z X Site (vertex) operator : As = \u00E2\u0088\u008F i\u00E2\u0088\u0088v(s)Xi Plaquette operator : Bp = \u00E2\u0088\u008F i\u00E2\u0088\u0088v(p) Zi `2 site and plaquette operators Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Stabilizer generators Stabilizer Generators X X X Z Z Z Z X Site (vertex) operator : As = \u00E2\u0088\u008F i\u00E2\u0088\u0088v(s)Xi Plaquette operator : Bp = \u00E2\u0088\u008F i\u00E2\u0088\u0088v(p) Zi `2 site and plaquette operators Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Stabilizer generators Stabilizer Generators X X X Z Z Z Z Z Z Z X X X Z XX Z Z Z Z X X XX [As, As\u00E2\u0080\u00B2 ] = [Bp, Bp\u00E2\u0080\u00B2 ] = 0 [As, Bp] = 0 The code is spanned by the simultaneous +1 eigenstates of all these C = {|\u00CF\u0088\u00E3\u0080\u0089 : As |\u00CF\u0088\u00E3\u0080\u0089 = |\u00CF\u0088\u00E3\u0080\u0089 , Bp |\u00CF\u0088\u00E3\u0080\u0089 = |\u00CF\u0088\u00E3\u0080\u0089 (\u00E2\u0088\u0080s, p)} Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Stabilizer generators Stabilizer Generators X X X Z Z Z Z Z Z Z X X X Z XX Z Z Z Z X X XX [As, As\u00E2\u0080\u00B2 ] = [Bp, Bp\u00E2\u0080\u00B2 ] = 0 [As, Bp] = 0 The code is spanned by the simultaneous +1 eigenstates of all these C = {|\u00CF\u0088\u00E3\u0080\u0089 : As |\u00CF\u0088\u00E3\u0080\u0089 = |\u00CF\u0088\u00E3\u0080\u0089 , Bp |\u00CF\u0088\u00E3\u0080\u0089 = |\u00CF\u0088\u00E3\u0080\u0089 (\u00E2\u0088\u0080s, p)} Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Stabilizer generators Stabilizer Generators X X X Z Z Z Z Z Z Z X X X Z XX Z Z Z Z X X XX [As, As\u00E2\u0080\u00B2 ] = [Bp, Bp\u00E2\u0080\u00B2 ] = 0 [As, Bp] = 0 The code is spanned by the simultaneous +1 eigenstates of all these C = {|\u00CF\u0088\u00E3\u0080\u0089 : As |\u00CF\u0088\u00E3\u0080\u0089 = |\u00CF\u0088\u00E3\u0080\u0089 , Bp |\u00CF\u0088\u00E3\u0080\u0089 = |\u00CF\u0088\u00E3\u0080\u0089 (\u00E2\u0088\u0080s, p)} Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Stabilizer generators Stabilizer Generators X X X Z Z Z Z X Z Z Z Z X X XX \u00E2\u0088\u008F sAs = I \u00E2\u0088\u008F pBp = I \u00E2\u0087\u0092 2`2 \u00E2\u0088\u0092 2 independent generators \u00E2\u0087\u0092 2 logical qubits Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Stabilizer generators Stabilizer Generators X X X Z Z Z Z X Z Z Z Z X X XX \u00E2\u0088\u008F sAs = I\u00E2\u0088\u008F pBp = I \u00E2\u0087\u0092 2`2 \u00E2\u0088\u0092 2 independent generators \u00E2\u0087\u0092 2 logical qubits Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Stabilizer generators Stabilizer Generators X X X Z Z Z Z X Z Z Z Z X X XX \u00E2\u0088\u008F sAs = I\u00E2\u0088\u008F pBp = I \u00E2\u0087\u0092 2`2 \u00E2\u0088\u0092 2 independent generators \u00E2\u0087\u0092 2 logical qubits Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Stabilizer generators Stabilizer Generators X X X Z Z Z Z X Z Z Z Z X X XX \u00E2\u0088\u008F sAs = I\u00E2\u0088\u008F pBp = I \u00E2\u0087\u0092 2`2 \u00E2\u0088\u0092 2 independent generators \u00E2\u0087\u0092 2 logical qubits Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Logical Operators Logical Operators Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Logical Operators First Logical Qubit Z1 = \u00E2\u0088\u008F i\u00E2\u0088\u0088\u00CE\u00B31 Zi [Z1, Bp] = 0 [Z1, As] = 0 \u00E2\u0088\u0080s \u00E2\u0088\u0088 S [Z1, s] = 0 Z1 \u00CE\u00B31 Z Z Z Z Z Z Z Z Z Z Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Logical Operators First Logical Qubit Z1 = \u00E2\u0088\u008F i\u00E2\u0088\u0088\u00CE\u00B31 Zi [Z1, Bp] = 0 [Z1, As] = 0 \u00E2\u0088\u0080s \u00E2\u0088\u0088 S [Z1, s] = 0 Z1 \u00CE\u00B31 Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Logical Operators First Logical Qubit Z1 = \u00E2\u0088\u008F i\u00E2\u0088\u0088\u00CE\u00B31 Zi [Z1, Bp] = 0 [Z1, As] = 0 \u00E2\u0088\u0080s \u00E2\u0088\u0088 S [Z1, s] = 0 Z1 \u00CE\u00B31 X X XX Z Z Z Z Z Z Z Z Z Z X X X X Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Logical Operators First Logical Qubit Z1 = \u00E2\u0088\u008F i\u00E2\u0088\u0088\u00CE\u00B31 Zi [Z1, Bp] = 0 [Z1, As] = 0 \u00E2\u0088\u0080s \u00E2\u0088\u0088 S [Z1, s] = 0 Z1 \u00CE\u00B31 Z Z Z Z Z Z Z Z Z Z Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Logical Operators First Logical Qubit X1 = \u00E2\u0088\u008F i\u00E2\u0088\u0088\u00CE\u00B31 Xi [X1, Bp] = 0 [X1, As] = 0 \u00E2\u0088\u0080s \u00E2\u0088\u0088 S [X1, s] = 0 {X1, Z1} = 0 X1 \u00CE\u00B3\u00E2\u0080\u00B21 X X X X X X X X X X Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Logical Operators First Logical Qubit X1 = \u00E2\u0088\u008F i\u00E2\u0088\u0088\u00CE\u00B31 Xi [X1, Bp] = 0 [X1, As] = 0 \u00E2\u0088\u0080s \u00E2\u0088\u0088 S [X1, s] = 0 {X1, Z1} = 0 X1 \u00CE\u00B3\u00E2\u0080\u00B21 X X X X X X X X X X Z Z Z Z Z Z Z Z Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Logical Operators First Logical Qubit X1 = \u00E2\u0088\u008F i\u00E2\u0088\u0088\u00CE\u00B31 Xi [X1, Bp] = 0 [X1, As] = 0 \u00E2\u0088\u0080s \u00E2\u0088\u0088 S [X1, s] = 0 {X1, Z1} = 0 X1 \u00CE\u00B3\u00E2\u0080\u00B21 X X X X X X X X X X X X XX X X XX Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Logical Operators First Logical Qubit X1 = \u00E2\u0088\u008F i\u00E2\u0088\u0088\u00CE\u00B31 Xi [X1, Bp] = 0 [X1, As] = 0 \u00E2\u0088\u0080s \u00E2\u0088\u0088 S [X1, s] = 0 {X1, Z1} = 0 X1 \u00CE\u00B3\u00E2\u0080\u00B21 X X X X X X X X X X Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Logical Operators First Logical Qubit X1 = \u00E2\u0088\u008F i\u00E2\u0088\u0088\u00CE\u00B31 Xi [X1, Bp] = 0 [X1, As] = 0 \u00E2\u0088\u0080s \u00E2\u0088\u0088 S [X1, s] = 0 {X1, Z1} = 0 Z1 X1 Z Z Z Z Z Z Z Z Z Z X X X X X X X X X X Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Logical Operators Second Logical Qubit By reflecting around the diagonal {X2, Z2} = 0 [X2, Z1] = 0 [X1, Z2] = 0 [X1, X2] = 0 [Z1, Z2] = 0 Z2 X2\u00CE\u00B3 \u00E2\u0080\u00B2 2 \u00CE\u00B32 Z Z Z Z Z Z Z Z Z Z XXXXXXXXXX Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Logical Operators Second Logical Qubit By reflecting around the diagonal {X2, Z2} = 0 [X2, Z1] = 0 [X1, Z2] = 0 [X1, X2] = 0 [Z1, Z2] = 0 Z2 X2\u00CE\u00B3 \u00E2\u0080\u00B2 2 \u00CE\u00B32 Z Z Z Z Z Z Z Z Z Z XXXXXXXXXX Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Logical Operators Second Logical Qubit By reflecting around the diagonal {X2, Z2} = 0 [X2, Z1] = 0 [X1, Z2] = 0 [X1, X2] = 0 [Z1, Z2] = 0 Z1 X2 Z Z Z Z Z Z Z Z Z Z XXXXXXXXXX Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Logical Operators Second Logical Qubit By reflecting around the diagonal {X2, Z2} = 0 [X2, Z1] = 0 [X1, Z2] = 0 [X1, X2] = 0 [Z1, Z2] = 0 Z1 X2 Z Z Z Z Z Z Z Z Z Z XXXXXXXXXX Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Logical Operators Second Logical Qubit By reflecting around the diagonal {X2, Z2} = 0 [X2, Z1] = 0 [X1, Z2] = 0 [X1, X2] = 0 [Z1, Z2] = 0 Z1 X2 Z Z Z Z Z Z Z Z Z Z XXXXXXXXXX Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Logical Operators New Basis A1, . . . , An/2\u00E2\u0088\u00921, B1, . . . , Bn/2\u00E2\u0088\u00921, Z\u00CC\u00841, Z\u00CC\u00842 tA1 , . . . , tAn/2\u00E2\u0088\u00921 , tB1 , . . . , tBn/2\u00E2\u0088\u00921 , X\u00CC\u00841, X\u00CC\u00842 Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Topology Topology ? Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Topology Trivial Cycles Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Topology Trivial Cycles Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Topology Trivial Cycles Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Topology Trivial Cycles Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Topology Trivial Cycles All As, Bp are trivial cycles They act as the identity on the code space : As |\u00CF\u0088\u00E3\u0080\u0089 = Bp |\u00CF\u0088\u00E3\u0080\u0089 = +1 |\u00CF\u0088\u00E3\u0080\u0089 Topologically and logically trivial X X XX Z Z Z Z Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Topology Trivial Cycles All As, Bp are trivial cycles They act as the identity on the code space : As |\u00CF\u0088\u00E3\u0080\u0089 = Bp |\u00CF\u0088\u00E3\u0080\u0089 = +1 |\u00CF\u0088\u00E3\u0080\u0089 Topologically and logically trivial X X XX Z Z Z Z Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Topology Trivial Cycles All As, Bp are trivial cycles They act as the identity on the code space : As |\u00CF\u0088\u00E3\u0080\u0089 = Bp |\u00CF\u0088\u00E3\u0080\u0089 = +1 |\u00CF\u0088\u00E3\u0080\u0089 Topologically and logically trivial X X XX Z Z Z Z Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Topology Trivial Cycles {As, Bp} span the set of trivial cycles \u00E2\u0087\u0092 all trivial cycles are equivalent to the identity on the code space X X XX Z Z Z Z X X XX Z Z Z Z Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Topology Trivial Cycles {As, Bp} span the set of trivial cycles \u00E2\u0087\u0092 all trivial cycles are equivalent to the identity on the code space X X X Z Z Z X X X Z Z Z Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Topology Trivial Cycles {As, Bp} span the set of trivial cycles \u00E2\u0087\u0092 all trivial cycles are equivalent to the identity on the code space X X X X X X X X X X Z Z Z Z Z Z Z Z Z Z ZZZZ Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Topology Non-Trivial Cycles Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Topology Non-Trivial Cycles Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Topology Non-Trivial Cycles Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Topology Non-Trivial Cycles Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Topology Non-Trivial Cycles Z1 and Z2 wind around the torus : non-trivial cycles They live on the lattice Z1 Z2 Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Topology Non-Trivial Cycles X1 and X2 are conjugate to Z1 and Z2 They live on the dual lattice X1 X2 X X X X X X X X X X XXXXXXXXXX Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Topology Non-Trivial Cycles Non-trivial cycles have non-trivial effects on the code space Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Topology Homological/Logical Classes |\u00CF\u0088\u00E3\u0080\u0089 = Bp\u00E2\u0080\u00B2 |\u00CF\u0088\u00E3\u0080\u0089 Z1 |\u00CF\u0088\u00E3\u0080\u0089 = Z1Bp\u00E2\u0080\u00B2 |\u00CF\u0088\u00E3\u0080\u0089 Z1 \u00E2\u0089\u00A1 Z1Bp\u00E2\u0080\u00B2 Z1 \u00E2\u0089\u00A1 Z1Bp\u00E2\u0080\u00B2Bp\u00E2\u0080\u00B2\u00E2\u0080\u00B2 Z1 \u00E2\u0089\u00A1 Z1 \u00E2\u0088\u008F pBp Z1 p\u00E2\u0080\u00B2 Z Z Z Z Z Z Z Z Z Z Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Topology Homological/Logical Classes |\u00CF\u0088\u00E3\u0080\u0089 = Bp\u00E2\u0080\u00B2 |\u00CF\u0088\u00E3\u0080\u0089 Z1 |\u00CF\u0088\u00E3\u0080\u0089 = Z1Bp\u00E2\u0080\u00B2 |\u00CF\u0088\u00E3\u0080\u0089 Z1 \u00E2\u0089\u00A1 Z1Bp\u00E2\u0080\u00B2 Z1 \u00E2\u0089\u00A1 Z1Bp\u00E2\u0080\u00B2Bp\u00E2\u0080\u00B2\u00E2\u0080\u00B2 Z1 \u00E2\u0089\u00A1 Z1 \u00E2\u0088\u008F pBp Z1 Bp\u00E2\u0080\u00B2 Z Z Z Z Z Z Z Z Z Z Z Z Z Z Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Topology Homological/Logical Classes |\u00CF\u0088\u00E3\u0080\u0089 = Bp\u00E2\u0080\u00B2 |\u00CF\u0088\u00E3\u0080\u0089 Z1 |\u00CF\u0088\u00E3\u0080\u0089 = Z1Bp\u00E2\u0080\u00B2 |\u00CF\u0088\u00E3\u0080\u0089 Z1 \u00E2\u0089\u00A1 Z1Bp\u00E2\u0080\u00B2 Z1 \u00E2\u0089\u00A1 Z1Bp\u00E2\u0080\u00B2Bp\u00E2\u0080\u00B2\u00E2\u0080\u00B2 Z1 \u00E2\u0089\u00A1 Z1 \u00E2\u0088\u008F pBp Z1Bp\u00E2\u0080\u00B2 Z Z Z Z Z Z Z Z Z Z Z Z Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Topology Homological/Logical Classes |\u00CF\u0088\u00E3\u0080\u0089 = Bp\u00E2\u0080\u00B2 |\u00CF\u0088\u00E3\u0080\u0089 Z1 |\u00CF\u0088\u00E3\u0080\u0089 = Z1Bp\u00E2\u0080\u00B2 |\u00CF\u0088\u00E3\u0080\u0089 Z1 \u00E2\u0089\u00A1 Z1Bp\u00E2\u0080\u00B2 Z1 \u00E2\u0089\u00A1 Z1Bp\u00E2\u0080\u00B2Bp\u00E2\u0080\u00B2\u00E2\u0080\u00B2 Z1 \u00E2\u0089\u00A1 Z1 \u00E2\u0088\u008F pBp Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Topology Homological/Logical Classes |\u00CF\u0088\u00E3\u0080\u0089 = Bp\u00E2\u0080\u00B2 |\u00CF\u0088\u00E3\u0080\u0089 Z1 |\u00CF\u0088\u00E3\u0080\u0089 = Z1Bp\u00E2\u0080\u00B2 |\u00CF\u0088\u00E3\u0080\u0089 Z1 \u00E2\u0089\u00A1 Z1Bp\u00E2\u0080\u00B2 Z1 \u00E2\u0089\u00A1 Z1Bp\u00E2\u0080\u00B2Bp\u00E2\u0080\u00B2\u00E2\u0080\u00B2 Z1 \u00E2\u0089\u00A1 Z1 \u00E2\u0088\u008F pBp ZZ Z Z Z Z Z Z Z Z Z Z Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Topology Homological/Logical Classes |\u00CF\u0088\u00E3\u0080\u0089 = Bp\u00E2\u0080\u00B2 |\u00CF\u0088\u00E3\u0080\u0089 Z1 |\u00CF\u0088\u00E3\u0080\u0089 = Z1Bp\u00E2\u0080\u00B2 |\u00CF\u0088\u00E3\u0080\u0089 Z1 \u00E2\u0089\u00A1 Z1Bp\u00E2\u0080\u00B2 Z1 \u00E2\u0089\u00A1 Z1Bp\u00E2\u0080\u00B2Bp\u00E2\u0080\u00B2\u00E2\u0080\u00B2 Z1 \u00E2\u0089\u00A1 Z1 \u00E2\u0088\u008F pBp Fast Decoders for Topological Quantum Codes Kitaev\u00E2\u0080\u0099s Toric Code Topology Summary Stabilizer \u00E2\u0086\u0094 Topology Every element of the stabilizer is a trivial cycle and vice-versa Every logical operator is a non-trivial cycle and vice-versa \u00E2\u0087\u0092 Topological equivalence classes Fast Decoders for Topological Quantum Codes Concatenation 1 Kitaev\u00E2\u0080\u0099s Toric Code 2 Concatenation Concatenated codes Efficient Optimal Decoder 3 Topological Codes Decoding Fast Decoders for Topological Quantum Codes Concatenation Concatenated codes Concatenated Codes Fast Decoders for Topological Quantum Codes Concatenation Concatenated codes Codes [[n,k,d]] . . . |\u00CF\u0088\u00E3\u0080\u0089 |\u00CF\u0088\u00E3\u0080\u0089 } Fast Decoders for Topological Quantum Codes Concatenation Concatenated codes Concatenated Codes . . . . . . . . . . . . |\u00CF\u0088\u00E3\u0080\u0089 |\u00CF\u0088\u00E3\u0080\u0089 k layers of encoding \u00E2\u0086\u0092 nk qubits Error rate decays doubly exponentially : k \u00E2\u0088\u00BC log \u000F Fast Decoders for Topological Quantum Codes Concatenation Efficient Optimal Decoder Efficient Optimal Decoder David Poulin, Phys. Rev. A 74, 052333 (2006) Fast Decoders for Topological Quantum Codes Concatenation Efficient Optimal Decoder Optimal (Soft) Decoder syndrome . . . {P(I), P(X), P(Y ), P(Z)} Noise Model Exponential in n, but n is constant Distillates error probability on the logical qubits Fast Decoders for Topological Quantum Codes Concatenation Efficient Optimal Decoder Recursive Decoder syndrome . . . P(L) Noise Model syndrome . . . P(L) syndrome . . . P(L) . . . syndrome P(L) k layers with at most nk codes Complexity : O(nkk) Fast Decoders for Topological Quantum Codes Topological Codes Decoding 1 Kitaev\u00E2\u0080\u0099s Toric Code 2 Concatenation 3 Topological Codes Decoding Fast Decoders for Topological Quantum Codes Topological Codes Decoding Threshold 0.0001 0.001 0.01 0.1 1 2 3 4 5 6 7 8 9 10 P ro b ab il it e d \u00E2\u0080\u0099e rr eu r d u d ec od eu r Force du canal Bit-Flip, p (%) l=8 l=16 l=32 l=64 l=128 l=256 l=512 l=1024 The threshold is the noise strength under which it is useful to encode Fast Decoders for Topological Quantum Codes Topological Codes Decoding Previous Method PMA : perfect matching algorithm (Preskill, Landahl et al.) Minimum distance decoder Complexity : O(`6), in practice limited to ` . 100 Threshold of \u00E2\u0088\u00BC 15.5% under depolarizing noise Limited to Kitaev\u00E2\u0080\u0099s toric code Fast Decoders for Topological Quantum Codes Topological Codes Decoding Previous Method PMA : perfect matching algorithm (Preskill, Landahl et al.) Minimum distance decoder Complexity : O(`6), in practice limited to ` . 100 Threshold of \u00E2\u0088\u00BC 15.5% under depolarizing noise Limited to Kitaev\u00E2\u0080\u0099s toric code Fast Decoders for Topological Quantum Codes Topological Codes Decoding Previous Method PMA : perfect matching algorithm (Preskill, Landahl et al.) Minimum distance decoder Complexity : O(`6), in practice limited to ` . 100 Threshold of \u00E2\u0088\u00BC 15.5% under depolarizing noise Limited to Kitaev\u00E2\u0080\u0099s toric code Fast Decoders for Topological Quantum Codes Topological Codes Decoding Previous Method PMA : perfect matching algorithm (Preskill, Landahl et al.) Minimum distance decoder Complexity : O(`6), in practice limited to ` . 100 Threshold of \u00E2\u0088\u00BC 15.5% under depolarizing noise Limited to Kitaev\u00E2\u0080\u0099s toric code Fast Decoders for Topological Quantum Codes Topological Codes Decoding Previous Method PMA : perfect matching algorithm (Preskill, Landahl et al.) Minimum distance decoder Complexity : O(`6), in practice limited to ` . 100 Threshold of \u00E2\u0088\u00BC 15.5% under depolarizing noise Limited to Kitaev\u00E2\u0080\u0099s toric code Fast Decoders for Topological Quantum Codes Topological Codes Decoding Our solution (Phys. Rev. Lett. 104, 050504 (2010)) We designed an algorithm inspired by the concatenated decoder Complexity : O(`2 log `) parallelizable to O(log `) time Enabled decoding of a ` = 1024 lattice without parallelizing More resiliant to noise : threshold of \u00E2\u0088\u00BC 16.5% under depolarizing noise Not limited to toric code (e.g. color codes : triplet of defects) Fast Decoders for Topological Quantum Codes Topological Codes Decoding Our solution (Phys. Rev. Lett. 104, 050504 (2010)) We designed an algorithm inspired by the concatenated decoder Complexity : O(`2 log `) parallelizable to O(log `) time Enabled decoding of a ` = 1024 lattice without parallelizing More resiliant to noise : threshold of \u00E2\u0088\u00BC 16.5% under depolarizing noise Not limited to toric code (e.g. color codes : triplet of defects) Fast Decoders for Topological Quantum Codes Topological Codes Decoding Our solution (Phys. Rev. Lett. 104, 050504 (2010)) We designed an algorithm inspired by the concatenated decoder Complexity : O(`2 log `) parallelizable to O(log `) time Enabled decoding of a ` = 1024 lattice without parallelizing More resiliant to noise : threshold of \u00E2\u0088\u00BC 16.5% under depolarizing noise Not limited to toric code (e.g. color codes : triplet of defects) Fast Decoders for Topological Quantum Codes Topological Codes Decoding Our solution (Phys. Rev. Lett. 104, 050504 (2010)) We designed an algorithm inspired by the concatenated decoder Complexity : O(`2 log `) parallelizable to O(log `) time Enabled decoding of a ` = 1024 lattice without parallelizing More resiliant to noise : threshold of \u00E2\u0088\u00BC 16.5% under depolarizing noise Not limited to toric code (e.g. color codes : triplet of defects) Fast Decoders for Topological Quantum Codes Topological Codes Decoding Our solution (Phys. Rev. Lett. 104, 050504 (2010)) We designed an algorithm inspired by the concatenated decoder Complexity : O(`2 log `) parallelizable to O(log `) time Enabled decoding of a ` = 1024 lattice without parallelizing More resiliant to noise : threshold of \u00E2\u0088\u00BC 16.5% under depolarizing noise Not limited to toric code (e.g. color codes : triplet of defects) Fast Decoders for Topological Quantum Codes Topological Codes Decoding Subcode Imagine we had a surface encoding taking 2 qubits into 8 Fast Decoders for Topological Quantum Codes Topological Codes Decoding Toric Code : A concatenation ? We could recurse on this encoding the build a bigger surface code Fast Decoders for Topological Quantum Codes Topological Codes Decoding Toric Code : A concatenation ? . . . We could recurse on this encoding the build a bigger surface code Fast Decoders for Topological Quantum Codes Topological Codes Decoding Decoding . . . If the toric code is just a concatenated code, then we know how to decode it efficiently ! Fast Decoders for Topological Quantum Codes Topological Codes Decoding Incomplete Stabilizers Some of the stabilizers are incomplete Fast Decoders for Topological Quantum Codes Topological Codes Decoding Closing the Stabilizers We complete the stabilizer by adding qubits to the subcode Fast Decoders for Topological Quantum Codes Topological Codes Decoding Closing the Stabilizers By adding these qubits the construction is no more a concatenation Fast Decoders for Topological Quantum Codes Topological Codes Decoding Concatenated code decoder Even though shared qubits correspond to the same physical entity, we are going to treat them as two diffrent qubits with the same noise model Main approximation : Decode with the concatenated code decoder anyway Fast Decoders for Topological Quantum Codes Topological Codes Decoding Characterizing the subcode SubCode stabilizer generators : 10 \u00E2\u0087\u0092 2 logical qubits Fast Decoders for Topological Quantum Codes Topological Codes Decoding Characterizing the subcode SubCode stabilizer generators : 10 \u00E2\u0087\u0092 2 logical qubits Fast Decoders for Topological Quantum Codes Topological Codes Decoding Results 0.1 6 6.5 7 7.5 8 8.5 9 P ro b ab il it e d \u00E2\u0080\u0099e rr eu r d u d ec od eu r Force du canal depolarizant, p (%) l=8 l=16 l=32 Is there a threshold at all ? At best, these are size effects Fast Decoders for Topological Quantum Codes Topological Codes Decoding Inconsistency By treating shared qubits as independent ones, we introduce inconsistencies A compromise between this and exact decoding would be to enforce consistency Fast Decoders for Topological Quantum Codes Topological Codes Decoding Generalized Belief Propagation (Jonathan S. Yedidia) Self-consistency constraints on shared qubits Neighboring unit cells exchange messages \u00E2\u0086\u0092 Belief propagation Compromise on shared qubits Fast Decoders for Topological Quantum Codes Topological Codes Decoding Intuition about GBP X 1 Depolarizing Channel, p << 1 1 0 1 2 3 Fast Decoders for Topological Quantum Codes Topological Codes Decoding Intuition about GBP X 1 Depolarizing Channel P (X) \u00E2\u0088\u00BC 50%P (X) \u00E2\u0088\u00BC p2 P (X) \u00E2\u0088\u00BC 50% 1 P (X) \u00E2\u0088\u00BC 50% 0 1 2 3 Fast Decoders for Topological Quantum Codes Topological Codes Decoding Intuition about GBP X 1 P (X) \u00E2\u0088\u00BC 50%P (X) \u00E2\u0088\u00BC p2 P (X) \u00E2\u0088\u00BC 50% 1 P (X) \u00E2\u0088\u00BC 50% 0 1 2 3 Fast Decoders for Topological Quantum Codes Topological Codes Decoding Intuition about GBP X 1 P (X) \u00E2\u0088\u00BC 50% P (X) \u00E2\u0088\u00BC p2 P (X) \u00E2\u0088\u00BC 50% 1 P (X) \u00E2\u0088\u00BC 50% 0 1 2 3 Fast Decoders for Topological Quantum Codes Topological Codes Decoding Results 0.01 0.1 1 12 13 14 15 16 17 P ro b ab il it e d \u00E2\u0080\u0099e rr eu r d u d ec od eu r Force du canal depolarizant, p (%) l=8 l=16 l=32 l=64 Fast Decoders for Topological Quantum Codes Topological Codes Decoding Preliminary Physical Decoding s1 s2 s3 P1(e) P2(e) Pi(e). . . . . . . . . BP on the bare stabilizers and qubits Accounts correlations between X and Z introduced by Y Its output is the input to the concatenated decoder Fast Decoders for Topological Quantum Codes Topological Codes Decoding Preliminary Physical Decoding s1 s2 s3 P1(e) P2(e) Pi(e). . . . . . . . . BP on the bare stabilizers and qubits Accounts correlations between X and Z introduced by Y Its output is the input to the concatenated decoder Fast Decoders for Topological Quantum Codes Topological Codes Decoding Preliminary Physical Decoding s1 s2 s3 P1(e) P2(e) Pi(e). . . . . . . . . BP on the bare stabilizers and qubits Accounts correlations between X and Z introduced by Y Its output is the input to the concatenated decoder Fast Decoders for Topological Quantum Codes Topological Codes Decoding Results 0.1 1 15 15.5 16 16.5 17 17.5 18 P ro b ab il it e d \u00E2\u0080\u0099e rr eu r d u d ec od eu r Force du canal depolarizant, p (%) l=8 l=16 l=32 l=64 l=128 PMA Fast Decoders for Topological Quantum Codes Topological Codes Decoding Results 0.0001 0.001 0.01 0.1 1 2 3 4 5 6 7 8 9 10 P ro b ab il it e d \u00E2\u0080\u0099e rr eu r d u d ec od eu r Force du canal Bit-Flip, p (%) l=8 l=16 l=32 l=64 l=128 l=256 l=512 l=1024 Unit cell (2\u00C3\u0097 1) + decoding the 2 types of defects independently \u00E2\u0087\u0092 ` = 1024 lattice Fast Decoders for Topological Quantum Codes Conclusion Conclusion Topological codes use highly non-local operators to encode information We proposed an efficient (O(log `) time) to decode them \u00E2\u0086\u0092 Concatenated codes, GBP More resiliant to noise under depolarizing noise than known methods (16.5% vs. 15.5%) It enabled decoding of color codes pth \u00E2\u0088\u00BC 8.7% (He\u00CC\u0081ctor Bombin) Fast Decoders for Topological Quantum Codes Conclusion Work in progress : Color Codes \u00EF\u0080\u0081 \u00EF\u0080\u0081\u00EF\u0080\u0082\u00EF\u0080\u0083\u00EF\u0080\u0084\u00EF\u0080\u0085\u00EF\u0080\u0086\u00EF\u0080\u0087\u00EF\u0080\u0082\u00EF\u0080\u0088 \u00EF\u0080\u0089 \u00EF\u0080\u008A \u00EF\u0080\u0089 \u00EF\u0080\u008A \u00EF\u0080\u008B \u00EF\u0080\u0089 \u00EF\u0080\u0089 \u00EF\u0080\u008A \u00EF\u0080\u008A \u00EF\u0080\u008B\u00EF\u0080\u0082\u00EF\u0080\u0083\u00EF\u0080\u0084\u00EF\u0080\u0085\u00EF\u0080\u0086\u00EF\u0080\u0087\u00EF\u0080\u0082\u00EF\u0080\u008C \u00EF\u0080\u0081\u00EF\u0080\u0082\u00EF\u0080\u0083\u00EF\u0080\u0084\u00EF\u0080\u0085\u00EF\u0080\u0086\u00EF\u0080\u0087\u00EF\u0080\u0082\u00EF\u0080\u008C \u00EF\u0080\u008B\u00EF\u0080\u0082\u00EF\u0080\u0083\u00EF\u0080\u0084\u00EF\u0080\u0085\u00EF\u0080\u0086\u00EF\u0080\u0087\u00EF\u0080\u0082\u00EF\u0080\u0088 \u00EF\u0080\u008B \u00EF\u0080\u0081 \u00EF\u0080\u008B \u00EF\u0080\u0081 \u00EF\u0080\u008B \u00EF\u0080\u0081 \u00EF\u0080\u008B \u00EF\u0080\u0081 Fast Decoders for Topological Quantum Codes Conclusion Color Codes : Mapping B BA A ZiXi Fast Decoders for Topological Quantum Codes Conclusion Color Codes : Results 0.0001 0.001 0.01 0.1 1 7 7.5 8 8.5 9 9.5 10 10.5 11 D ec od in g er ro r p ro b ab il it y Bit-Flip channel strength p% l=16 l=32 l=64 l=128 l=256"@en . "Presentation"@en . "10.14288/1.0103160"@en . "eng"@en . "Unreviewed"@en . "Vancouver : University of British Columbia Library"@en . "Attribution-NonCommercial-NoDerivatives 4.0 International"@en . "http://creativecommons.org/licenses/by-nc-nd/4.0/"@en . "Graduate"@en . "Quantum error-correction"@en . "Topological quantum codes"@en . "Toric code"@en . "Renormalization"@en . "Belief propagation"@en . "Depolarizing channel"@en . "Erasure channel"@en . "Color codes"@en . "Fast Decoders for Topological Quantum Codes"@en . "Text"@en . "Moving Image"@en . "http://hdl.handle.net/2429/30068"@en .