Canadian Summer School on Quantum Information (CSSQI) (10th : 2010)

Fast Decoders for Topological Quantum Codes Duclos-Cianci, Guillaume 2010-07-25

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

Item Metadata

Download

Media
59370-Duclos-Cianci_QAMF10.pdf [ 2.86MB ]
59370-WS Jul 25 Guillaume.mp4 [ 94.83MB ]
Metadata
JSON: 59370-1.0103160.json
JSON-LD: 59370-1.0103160-ld.json
RDF/XML (Pretty): 59370-1.0103160-rdf.xml
RDF/JSON: 59370-1.0103160-rdf.json
Turtle: 59370-1.0103160-turtle.txt
N-Triples: 59370-1.0103160-rdf-ntriples.txt
Original Record: 59370-1.0103160-source.json
Full Text
59370-1.0103160-fulltext.txt
Citation
59370-1.0103160.ris

Full Text

Fast Decoders for Topological Quantum Codes Fast Decoders for Topological Quantum Codes Guillaume Duclos-Cianci1 David Poulin1 1Département de Physique, Université 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 → linked to the topology of the system Operators highly non-local → tailored to resist local noise Error correction requires local measurements and operations Kitaev’s toric code → useful toy model Quantum error-correction (QEC) → fast decoding algorithms Fast Decoders for Topological Quantum Codes Motivation Topological Codes Logical subspace → linked to the topology of the system Operators highly non-local → tailored to resist local noise Error correction requires local measurements and operations Kitaev’s toric code → useful toy model Quantum error-correction (QEC) → fast decoding algorithms Fast Decoders for Topological Quantum Codes Motivation Topological Codes Logical subspace → linked to the topology of the system Operators highly non-local → tailored to resist local noise Error correction requires local measurements and operations Kitaev’s toric code → useful toy model Quantum error-correction (QEC) → fast decoding algorithms Fast Decoders for Topological Quantum Codes Motivation Topological Codes Logical subspace → linked to the topology of the system Operators highly non-local → tailored to resist local noise Error correction requires local measurements and operations Kitaev’s toric code → useful toy model Quantum error-correction (QEC) → fast decoding algorithms Fast Decoders for Topological Quantum Codes Motivation Topological Codes Logical subspace → linked to the topology of the system Operators highly non-local → tailored to resist local noise Error correction requires local measurements and operations Kitaev’s toric code → useful toy model Quantum error-correction (QEC) → fast decoding algorithms Fast Decoders for Topological Quantum Codes Motivation 1 Kitaev’s Toric Code 2 Concatenation 3 Topological Codes Decoding Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code 1 Kitaev’s Toric Code Stabilizer generators Logical Operators Topology 2 Concatenation 3 Topological Codes Decoding Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Stabilizer generators Stabilizer Generators Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Stabilizer generators Lattice l l 2D square lattice Periodic boundary conditions Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Stabilizer generators Lattice l l 2D square lattice Periodic boundary conditions Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Stabilizer generators Lattice + Qubits l l 2D square lattice Periodic boundary conditions A qubit per edge ⇒ 2`2 qubits Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Stabilizer generators Lattice + Qubits l l 2D square lattice Periodic boundary conditions A qubit per edge ⇒ 2`2 qubits Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Stabilizer generators Lattice + Qubits l l 2D square lattice Periodic boundary conditions A qubit per edge ⇒ 2`2 qubits Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Stabilizer generators Lattice + Qubits l l 2D square lattice Periodic boundary conditions A qubit per edge ⇒ 2`2 qubits Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Stabilizer generators Stabilizer Generators X X X Z Z Z Z X Site (vertex) operator : As = ∏ i∈v(s)Xi Plaquette operator : Bp = ∏ i∈v(p) Zi `2 site and plaquette operators Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Stabilizer generators Stabilizer Generators X X X Z Z Z Z X Site (vertex) operator : As = ∏ i∈v(s)Xi Plaquette operator : Bp = ∏ i∈v(p) Zi `2 site and plaquette operators Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Stabilizer generators Stabilizer Generators X X X Z Z Z Z X Site (vertex) operator : As = ∏ i∈v(s)Xi Plaquette operator : Bp = ∏ i∈v(p) Zi `2 site and plaquette operators Fast Decoders for Topological Quantum Codes Kitaev’s 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′ ] = [Bp, Bp′ ] = 0 [As, Bp] = 0 The code is spanned by the simultaneous +1 eigenstates of all these C = {|ψ〉 : As |ψ〉 = |ψ〉 , Bp |ψ〉 = |ψ〉 (∀s, p)} Fast Decoders for Topological Quantum Codes Kitaev’s 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′ ] = [Bp, Bp′ ] = 0 [As, Bp] = 0 The code is spanned by the simultaneous +1 eigenstates of all these C = {|ψ〉 : As |ψ〉 = |ψ〉 , Bp |ψ〉 = |ψ〉 (∀s, p)} Fast Decoders for Topological Quantum Codes Kitaev’s 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′ ] = [Bp, Bp′ ] = 0 [As, Bp] = 0 The code is spanned by the simultaneous +1 eigenstates of all these C = {|ψ〉 : As |ψ〉 = |ψ〉 , Bp |ψ〉 = |ψ〉 (∀s, p)} Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Stabilizer generators Stabilizer Generators X X X Z Z Z Z X Z Z Z Z X X XX ∏ sAs = I ∏ pBp = I ⇒ 2`2 − 2 independent generators ⇒ 2 logical qubits Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Stabilizer generators Stabilizer Generators X X X Z Z Z Z X Z Z Z Z X X XX ∏ sAs = I∏ pBp = I ⇒ 2`2 − 2 independent generators ⇒ 2 logical qubits Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Stabilizer generators Stabilizer Generators X X X Z Z Z Z X Z Z Z Z X X XX ∏ sAs = I∏ pBp = I ⇒ 2`2 − 2 independent generators ⇒ 2 logical qubits Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Stabilizer generators Stabilizer Generators X X X Z Z Z Z X Z Z Z Z X X XX ∏ sAs = I∏ pBp = I ⇒ 2`2 − 2 independent generators ⇒ 2 logical qubits Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Logical Operators Logical Operators Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Logical Operators First Logical Qubit Z1 = ∏ i∈γ1 Zi [Z1, Bp] = 0 [Z1, As] = 0 ∀s ∈ S [Z1, s] = 0 Z1 γ1 Z Z Z Z Z Z Z Z Z Z Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Logical Operators First Logical Qubit Z1 = ∏ i∈γ1 Zi [Z1, Bp] = 0 [Z1, As] = 0 ∀s ∈ S [Z1, s] = 0 Z1 γ1 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’s Toric Code Logical Operators First Logical Qubit Z1 = ∏ i∈γ1 Zi [Z1, Bp] = 0 [Z1, As] = 0 ∀s ∈ S [Z1, s] = 0 Z1 γ1 X X XX Z Z Z Z Z Z Z Z Z Z X X X X Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Logical Operators First Logical Qubit Z1 = ∏ i∈γ1 Zi [Z1, Bp] = 0 [Z1, As] = 0 ∀s ∈ S [Z1, s] = 0 Z1 γ1 Z Z Z Z Z Z Z Z Z Z Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Logical Operators First Logical Qubit X1 = ∏ i∈γ1 Xi [X1, Bp] = 0 [X1, As] = 0 ∀s ∈ S [X1, s] = 0 {X1, Z1} = 0 X1 γ′1 X X X X X X X X X X Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Logical Operators First Logical Qubit X1 = ∏ i∈γ1 Xi [X1, Bp] = 0 [X1, As] = 0 ∀s ∈ S [X1, s] = 0 {X1, Z1} = 0 X1 γ′1 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’s Toric Code Logical Operators First Logical Qubit X1 = ∏ i∈γ1 Xi [X1, Bp] = 0 [X1, As] = 0 ∀s ∈ S [X1, s] = 0 {X1, Z1} = 0 X1 γ′1 X X X X X X X X X X X X XX X X XX Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Logical Operators First Logical Qubit X1 = ∏ i∈γ1 Xi [X1, Bp] = 0 [X1, As] = 0 ∀s ∈ S [X1, s] = 0 {X1, Z1} = 0 X1 γ′1 X X X X X X X X X X Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Logical Operators First Logical Qubit X1 = ∏ i∈γ1 Xi [X1, Bp] = 0 [X1, As] = 0 ∀s ∈ 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’s 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γ ′ 2 γ2 Z Z Z Z Z Z Z Z Z Z XXXXXXXXXX Fast Decoders for Topological Quantum Codes Kitaev’s 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γ ′ 2 γ2 Z Z Z Z Z Z Z Z Z Z XXXXXXXXXX Fast Decoders for Topological Quantum Codes Kitaev’s 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’s 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’s 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’s Toric Code Logical Operators New Basis A1, . . . , An/2−1, B1, . . . , Bn/2−1, Z̄1, Z̄2 tA1 , . . . , tAn/2−1 , tB1 , . . . , tBn/2−1 , X̄1, X̄2 Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Topology Topology ? Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Topology Trivial Cycles Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Topology Trivial Cycles Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Topology Trivial Cycles Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Topology Trivial Cycles Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Topology Trivial Cycles All As, Bp are trivial cycles They act as the identity on the code space : As |ψ〉 = Bp |ψ〉 = +1 |ψ〉 Topologically and logically trivial X X XX Z Z Z Z Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Topology Trivial Cycles All As, Bp are trivial cycles They act as the identity on the code space : As |ψ〉 = Bp |ψ〉 = +1 |ψ〉 Topologically and logically trivial X X XX Z Z Z Z Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Topology Trivial Cycles All As, Bp are trivial cycles They act as the identity on the code space : As |ψ〉 = Bp |ψ〉 = +1 |ψ〉 Topologically and logically trivial X X XX Z Z Z Z Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Topology Trivial Cycles {As, Bp} span the set of trivial cycles ⇒ 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’s Toric Code Topology Trivial Cycles {As, Bp} span the set of trivial cycles ⇒ 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’s Toric Code Topology Trivial Cycles {As, Bp} span the set of trivial cycles ⇒ 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’s Toric Code Topology Non-Trivial Cycles Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Topology Non-Trivial Cycles Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Topology Non-Trivial Cycles Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Topology Non-Trivial Cycles Fast Decoders for Topological Quantum Codes Kitaev’s 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’s 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’s Toric Code Topology Non-Trivial Cycles Non-trivial cycles have non-trivial effects on the code space Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Topology Homological/Logical Classes |ψ〉 = Bp′ |ψ〉 Z1 |ψ〉 = Z1Bp′ |ψ〉 Z1 ≡ Z1Bp′ Z1 ≡ Z1Bp′Bp′′ Z1 ≡ Z1 ∏ pBp Z1 p′ Z Z Z Z Z Z Z Z Z Z Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Topology Homological/Logical Classes |ψ〉 = Bp′ |ψ〉 Z1 |ψ〉 = Z1Bp′ |ψ〉 Z1 ≡ Z1Bp′ Z1 ≡ Z1Bp′Bp′′ Z1 ≡ Z1 ∏ pBp Z1 Bp′ Z Z Z Z Z Z Z Z Z Z Z Z Z Z Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Topology Homological/Logical Classes |ψ〉 = Bp′ |ψ〉 Z1 |ψ〉 = Z1Bp′ |ψ〉 Z1 ≡ Z1Bp′ Z1 ≡ Z1Bp′Bp′′ Z1 ≡ Z1 ∏ pBp Z1Bp′ Z Z Z Z Z Z Z Z Z Z Z Z Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Topology Homological/Logical Classes |ψ〉 = Bp′ |ψ〉 Z1 |ψ〉 = Z1Bp′ |ψ〉 Z1 ≡ Z1Bp′ Z1 ≡ Z1Bp′Bp′′ Z1 ≡ Z1 ∏ pBp Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Topology Homological/Logical Classes |ψ〉 = Bp′ |ψ〉 Z1 |ψ〉 = Z1Bp′ |ψ〉 Z1 ≡ Z1Bp′ Z1 ≡ Z1Bp′Bp′′ Z1 ≡ Z1 ∏ pBp ZZ Z Z Z Z Z Z Z Z Z Z Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Topology Homological/Logical Classes |ψ〉 = Bp′ |ψ〉 Z1 |ψ〉 = Z1Bp′ |ψ〉 Z1 ≡ Z1Bp′ Z1 ≡ Z1Bp′Bp′′ Z1 ≡ Z1 ∏ pBp Fast Decoders for Topological Quantum Codes Kitaev’s Toric Code Topology Summary Stabilizer ↔ Topology Every element of the stabilizer is a trivial cycle and vice-versa Every logical operator is a non-trivial cycle and vice-versa ⇒ Topological equivalence classes Fast Decoders for Topological Quantum Codes Concatenation 1 Kitaev’s 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]] . . . |ψ〉 |ψ〉 } Fast Decoders for Topological Quantum Codes Concatenation Concatenated codes Concatenated Codes . . . . . . . . . . . . |ψ〉 |ψ〉 k layers of encoding → nk qubits Error rate decays doubly exponentially : k ∼ log  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’s 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 ’e 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 ∼ 15.5% under depolarizing noise Limited to Kitaev’s 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 ∼ 15.5% under depolarizing noise Limited to Kitaev’s 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 ∼ 15.5% under depolarizing noise Limited to Kitaev’s 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 ∼ 15.5% under depolarizing noise Limited to Kitaev’s 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 ∼ 15.5% under depolarizing noise Limited to Kitaev’s 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 ∼ 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 ∼ 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 ∼ 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 ∼ 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 ∼ 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 ⇒ 2 logical qubits Fast Decoders for Topological Quantum Codes Topological Codes Decoding Characterizing the subcode SubCode stabilizer generators : 10 ⇒ 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 ’e 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 → 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) ∼ 50%P (X) ∼ p2 P (X) ∼ 50% 1 P (X) ∼ 50% 0 1 2 3 Fast Decoders for Topological Quantum Codes Topological Codes Decoding Intuition about GBP X 1 P (X) ∼ 50%P (X) ∼ p2 P (X) ∼ 50% 1 P (X) ∼ 50% 0 1 2 3 Fast Decoders for Topological Quantum Codes Topological Codes Decoding Intuition about GBP X 1 P (X) ∼ 50% P (X) ∼ p2 P (X) ∼ 50% 1 P (X) ∼ 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 ’e 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 ’e 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 ’e 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× 1) + decoding the 2 types of defects independently ⇒ ` = 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 → 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 ∼ 8.7% (Héctor Bombin) Fast Decoders for Topological Quantum Codes Conclusion Work in progress : Color Codes                       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

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            data-media="{[{embed.selectedMedia}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.59370.1-0103160/manifest

Comment

Related Items