Quantum Error Correction

Nikolas Breuckmann

University College London

​

QuID Summer School 2019

ETH Zurich

Construction

How to construct quantum codes in a systematic way?

​

What constraints are there?

Construction: Stabilizer Codes

• Shor’s code was constructed from bit-flip code
• In particular: used encoding circuit
• Generally: hard to construct quantum code by looking at states
• Convenient tool: stabilizer formalism
• Developed by Daniel Gottesman in his Ph.D. thesis

Construction: Stabilizer Codes

Construction: Stabilizer Codes

Construction: Stabilizer Codes

Construction: Stabilizer Codes

The all-important property of Pauli-X/Z:

X Z = - Z X

Construction: Stabilizer Codes

Construction: Stabilizer Codes

Construction: Stabilizer Codes

Construction: Stabilizer Codes

Distance:

• If error contains a logical operator: a priori no way to correct it
• Indicator for code performance is the distance d:

Minimum number of qubits that support a logical operator

• Distance of Shor’s code is d = 3
• Parameters of a code [[n, k, d]]
• number of physical qubits n
• Number of encoded qubits k
• Distance d

Construction: Stabilizer Codes

Construction: Stabilizer Codes

Construction: Stabilizer Codes

CSS Codes

Shor’s code has an interesting property:

The stabilizer group is generated by Pauli operators which

act as Pauli-X or Pauli-Z only

Construction: Stabilizer Codes

CSS Codes

​

Construction: Stabilizer Codes

CSS Codes

Stabilizer group elements commute since Z-nodes and X-nodes overlap

on an even number of qubit nodes

​

Construction: Stabilizer Codes

CSS Codes

Not all stabilizer codes are CSS codes:

[[5,1,3]] code a.k.a. “5-qubit code”

​

Construction: Stabilizer Codes

Bounds on parameters

[Bravyi-Poulin-Terhal ‘09]: If stabilizer code is local on a D-dimensional (euclidean) lattice then

For 2D classical storage:

Construction: Stabilizer Codes

​

Summary:

​

Stabilizer Codes:

• Stabilizer formalism is a convenient tool to construct quantum codes
• Code space is +1-eigenspace of a commutative subgroup of the Pauli group
• Stabilizers may anti-commute with errors: syndrome given by their eigenvalues
• CSS codes: generators of stabilizer group act as X or Z on qubits
• Can construct CSS code from a tripartite graph where nodes in the outer layers share even number of neighbours

​

References: Gottesman’s PhD thesis arXiv:quant-ph/9705052

Topological Codes

How can topology and geometry be used to correct quantum errors?

Topological Codes: Kitaev’s Toric Code

Topological Codes: 2D Toric Code

​

Any face and vertex share 0 or 2 edges:

This is a CSS code

Topological Codes: 2D Toric Code

​

Z-logical operators:

• Must commute with all X-stabilizers
• Hence: can not have end-points
• Contractible loop: product of Z-stabilizers
• Logicals are non-contractible loops (k = 2)

Topological Codes: 2D Toric Code

​

Topological Codes: 2D Toric Code

​

Decoding:

• Minimum-weight perfect matching
• Sophisticated algorithm (Blossom)
• Computational complexity scales n³

Figure from Wikipedia article on Blossom algorithm

Topological Codes: 2D Toric Code

​

Decoding:

• [Delfosse & Nickerson ‘17]

Union find decoder: almost linear time

• same threshold as MWPM
• Works by growing regions around syndromes until regions are ‘neutral’
• Then perform simple peeling decoder beginning at boundaries of regions

Figure from Delfosse & Nickerson arXiv:1709.06218

Topological Codes: 2D Toric Code

​

Figure from Dennis et. al. 2001: Topological Quantum Memories

• Syndrome measurement can be faulty
• Need to repeat to gain confidence
• Perform matching in space-time

Topological Codes:

[Bravyi & Kitaev, Freedman & Meyer ‘98]

Topological Codes: Toric/Surface Code Threshold

​

Decoding Threshold:

• Decoding failure probability P depends on physical error probability p
• There exists a threshold p_t such that P→0 for L→∞ for all p < p_t
• Realistic noise models:

p_t ~ 1%

Reference: Fowler et. al. arXiv:1208.0928

Topological Codes

Consider some more exotic geometries:

• Projective plane:

unit circle with opposing points on boundary identified

• Can tile the projective plane using
• 3 vertices
• 9 edges
• 7 faces

Topological Codes

Exercise:

• Find all Z-/X-stabilizers
• X-stabilizers: vertices
• Z-stabilizers: faces
• Find a logical operator
• Do you notice something?

Topological Codes

Topological Codes

This is Shor’s code!

​

[arXiv:quant-ph/9810055]

Topological Codes

Corresponds to the non-contractible loop of the projective plane

Logical operator: Z₁ Z₄ Z₇

Homological codes

Recipe

​

​

1. Take tessellated D-manifold

​

• Pick dimension 0 < i < D

​

• Identify:
1. i-cells with qubits

​

• i-1-cells with X-checks

​

• i+1-cells with Z-checks

There is a very general principle standing behind this:

Algebraic topology & Homology

Topological Codes: 3D Toric Code

Topological Codes: 3D Toric Code

Topological Codes: 4D

Topological Codes: 4D

[Alicki, Horodecki³], arXiv:0811.0033

• Construct Hamiltonian with code as ground space
• Syndrome gives energy penalty

Topological Codes: 4D

• Do majority vote around face
• Can only shrink syndrome & does not increase it

[Dennis et. al. (2001)]

• Appealing:
• low complexity
• easy to implement

Hyperbolic Codes

• Defined on negatively curved surfaces of increasing area
• Surfaces have large genus: many encoded qubits
• Comparable stabilizer generators to surface code

Hyperbolic Codes

Animation by Tim Hutton

Hyperbolic Codes: encoding rate k/n

Chern-Gauss-Bonnet Theorem:

D = 2, i = 1

Number of encoded qubits grows linearly with number of physical qubits n

Hyperbolic Codes: distance d

• Hyperbolic pace expands tree-like
• Distance d is of order log(n)
• Note that hyperbolic codes break the BPT-bound by a logarithmic factor

Figure from: Moran - The growth rate and balance of homogeneous tilings, ‘95

Hyperbolic Codes: Overhead reduction

Color Codes

• First considered by Héctor Bombín
• Consider a 2D tiling such that
• Faces have a 3-coloring
• Vertices & edges form trivalent graph
• Identify
• Vertices with qubits
• Faces with X-stabilizers & Z-stabilizers
• Stabilizers will commute:

obtain valid stabilizer code

• Example: Steane code

Color Codes

Reference: Kubica PhD thesis https://thesis.library.caltech.edu/10955/

• Symmetries allow for fault-tolerant gate constructions
• [Kubicka, Yoshida, Pastawski ‘15]: Equivalent via local unitaries to copies of the toric code
• Variation: 3D Gauge Color Code
• allows for interesting FT-schemes
• behaves a bit like 4D code
• maybe thermally stable?
• “gauge”: two different codes: can switch between

Figure by Héctor Bombín

LDPC Stabilizer Codes

LDPC: Low Density Parity Check

• The number of qubits that each stabilizer generator acts upon is constant
• Desired as syndrome measurements become non-fault-tolerant otherwise

• [Tillich & Zémor ‘13: arXiv:0903.0566]: hypergraph product codes
• Constructed from two classical codes
• Quantum code inherits classical code properties
• Best code parameters: linear rate & d~√n

[Bacon, Flammia,Harrow,Shi ‘14: arXiv:1411.3334] highest distance:

d = n^1-ε with ε = O(1/√log(n))

LDPC Stabilizer Codes

Threshold comparison not be taken too seriously!

Basics: Topological Codes

Summary:

​

Topological & LDPC Codes:

• Can construct quantum codes from lattices
• Lattices can have exotic geometries (projective plane, hyperbolic, higher-dimensional)
• LDPC codes: more general class, not bound by geometry
• Currently favoured scheme: surface code (low checks, high-threshold, planar)