7/27/2023
Quantum LDPC codes
Lecture 3
Nicolas Delfosse
Microsoft
PCMI Summer School 2023
July 27th 2023
7/27/2023
Overview of the whole scheme
Today
code Syndrome
extraction X syndrome of E
circuit
0 1 1
Pauli
error E Correcti Decode
𝜓 ∈ stabilizer code 𝐸𝜓
on of E r
1 0 1
Syndrome Z syndrome of E
extraction
circuit
circuit layout
7/27/2023
The decoding problem
7/27/2023
MLE = Most Likely
MLE, MLC and MW decoders Error
MLC = Most Likely
Coset
MW = Min Weight
• Model = Perfect measurement
• Qubit noise = Probability distribution Pr 𝐸 over 𝐼, 𝑋, 𝑌, 𝑍
Def. A decoder is a map 𝐷: 0,1 → 𝐼, 𝑋, 𝑌, 𝑍 .
• It is a MW decoder if 𝐷(𝜎) is a min weight Pauli error with
syndrome 𝜎.
• It is a MLE decoder if 𝐷(𝜎) is a Pauli error that maximizes Pr 𝐸|𝜎 .
• It is a MLC decoder if 𝐷(𝜎) is a Pauli error that maximizes
Pr 𝐸. 𝑆|𝜎 .
7/27/2023
Comparison
• In general MLC > MLE > MW
• If low noise rate + low correlation probability then
MLE ≈ MLC ≈ MW
• A MLC decoder may achieve a higher threshold. For surface codes:
• MLE threshold ≈ 16%
• MLC threshold ≈ 19%
7/27/2023
Standard Pauli noise models
Perfect measurement model:
• Noise on data qubits
Phenomenological model:
• Noise on data qubits
• Noise on measurements
Circuit noise:
| +> • Noise on data qubits
• Noise on measurements
• Noise on ancilla qubits
• Noise on gates
• Noise on waiting qubits
7/27/2023
From perfect measurements to
circuit model
The syndrome extraction circuit is
noisy.
=> We need to correct circuit faults
But Circuit faults ≈ Pauli errors for
a larger code.
=> We focus on Pauli errors because:
Measuremen
Ex. t error
• Circuit faults in 2D surface codes
≈ Pauli errors in 3D surface code1.
• Circuit fault in a Clifford circuit Qubit
≈ Pauli errors in the spacetime errors
code2.
time
1. Dennis, Kitaev, Landhal, Preskill – Topological quantum memory (2001)
2. Delfosse, Paetznick – Spacetime codes of Clifford circuits (2023) Three rounds of
measurements
7/27/2023
Lookup table decoder
7/27/2023
Computational complexity
Computational complexity:
• MLE decoding for stabilizer codes is NP-hard1
• MLC decoding for stabilizer codes is #P-hard2
In practice:
• Use highly structure codes (Hamming, Reed Muller, BCH, Reed
Solomon, Turbo, Polar, LDPC, Spatially-Coupled)
• Exploit this structure to design an efficient decoder.
• The decoder must be adapted to the resource available: memory,
compute, energy, space, time, technology, cost
1. Berlekamp, McEliece, Van Tilborg
2. Iyer, Poulin (2015)
7/27/2023
Implementation of a MW decoder
using a lookup table
Input: Code + bound 𝑀.
Output: A MW decoder for the correction of all errors with weight ≤
𝑀
1. Initialize 𝐷 𝜎 = 0 for all 𝜎. Checks Correctio
2. For 𝑤 = 1,2, … , 𝑀 do: n
3. Loop over Pauli errors 𝐸 with weight w and 100
do: Flip 4
4. Compute 𝜎(𝐸) 010 Flip 6
5. If 𝐷 𝜎 = 0, set D 𝜎 = 𝐸 110 Flip 2
6. Return 𝐷 001 Flip 7
101 Flip 3
Question. What is the size of 𝐷? 011 Flip 5
𝑛 111 Flip 1
3
𝑤 LUT decoder for Hamming code
` ,…,
7/27/2023
Example
Is there a LUT decoder in my laptop?
Claim:
• The flash memory uses LDPC codes with length 𝑛 ≈ 8,000.
• The code has distance 𝑑 ≈ 30
Is that feasible?
• We need to store all corrections with weight up to 𝑀 = 15.
8,000
• Cost: ≥ ≈ 2.10 bits =
15
• 20 trillions quetabits
7/27/2023
Belief Propagation
decoder for classical
codes
7/27/2023
Erasure channel
1-p
0 0
p
p ?
1 1
1-p
7/27/2023
Correction of an erased bit
with a (2,3)-code
?
Question: Does it work in
practice?
Select graph with large
girth (no short cycle).
? ? ?
? ?
7/27/2023
Classical peeling decoder
𝑥 = 1 0
? 1
? 0 1 0 1 Def. A dangling check is a check
connected to a single erased bit.
Peeling decoder:
1. While there exists a dangling
check do:
2. Select a dangling check
and use it to correct the
𝑥 +𝑥 +𝑥 +𝑥 = 0 incident bit.
⇒ 1+𝑥 +1+0 =0
⇒𝑥 =0
Zyablov, Pinsker –
1974
7/27/2023
Stopping sets
Def. A stopping set is a set of
erased bits with no dangling check.
𝑥 = 1 ? ? 0 ? 0 1 Prop. [Zyablov, Pinsker - 1974]. The
peeling decoder fails iff the
erasure contains a stopping set.
Theorem. [Richardson, Urbanke -
2001]. For carefully designed
classical LDPC codes, the
probability of an erased stopping
sets vanishes.
Basic idea: Design graphs with no
short cycle.
7/27/2023
References
7/27/2023
Binary symmetric channel
1-p
0 0
p
p
1 1
1-p
7/27/2023
Marginal bit-flip probability
channel
𝑥 𝑥 …𝑥 𝑦 𝑦 …𝑦
Goal: Compute 𝑃 𝑥 = 0 𝑦) and 𝑃 𝑥 = 1 𝑦) for all 𝑖.
We can use this value to correct each bit.
How?
7/27/2023
Marginal bit-flip probability
We want to evaluate
𝑃 𝑥 = 0 𝑦) = 𝑃 𝑦 𝑥)𝟏 ∈
∈
, ,…,
= 𝑃 𝑦 𝑥 )𝟏 ∈
,..
, ,…,
What is 𝟏 ∈ for the distance-3 repetition code?
• 𝑥 ∈ 𝐶 iff 𝑥 + 𝑥 = 0 and 𝑥 + 𝑥 = 0
• Therefore 𝟏 ∈ = (1 + 𝑥 + 𝑥 )(1 + 𝑥 + 𝑥 )
7/27/2023
Marginal bit-flip probability
We want to evaluate
𝑃 𝑥 = 0 𝑦) = 𝑃 𝑦 𝑥 )𝟏 ∈
,..
, ,…,
It a function of the form
𝑓 𝑥 … 𝑓 (𝑥)
, ,…,
For LDPC codes each 𝑓 depends only on a small number of variables 𝑥 .
How many multiplications are needed?
• 𝑂(2 𝑛) multiplications.
7/27/2023
Example
Compute the sum
𝑓 𝑥 ,𝑥 ,𝑥 𝑔 𝑥
, , ,
𝑓 𝑥 ,𝑥 ,𝑥 𝑔 𝑥
, ,
7/27/2023
Marginal computation by Belief
Propagation
Example: Compute the sum
𝑓 𝑥 , 𝑥 , 𝑥 𝑓 𝑥 , 𝑥 , 𝑥 𝑓 𝑥 𝑓 (𝑥 , 𝑥 )
, , , ,
Strategy:
• Represent the 𝑓 and their variables as a graph (called
factor graph).
• Use the graph topology to optimize the computation of
partial sums.
7/27/2023
𝑓 𝑓
𝑥 𝑥 𝑥 𝑥
𝑓 𝑓
𝑓 𝑥 , 𝑥 , 𝑥 𝑓 𝑥 , 𝑥 , 𝑥 𝑓 𝑥 𝑓 (𝑥 , 𝑥 )
, , , , 𝑥
7/27/2023
Belief Propagation messages
∏ 𝜇 → (𝟎)
= product of incoming messages
∏ 𝜇 → (𝟏)
…
𝑓 𝑓 𝑓
From variables to checks
7/27/2023
Belief Propagation messages
𝑥
∑𝒙𝟐 ,…,𝒙𝒔 𝑓 (0, 𝒙𝟐 , … , 𝒙𝒎 ) ∏ 𝜇 → (𝒙𝒊 )
∑𝒙𝟐 ,…,𝒙𝒔 𝑓 (1, 𝒙𝟐 , … , 𝒙𝒎 ) ∏ 𝜇 → (𝒙𝒊 )
𝑓 = sum over all values of incoming variables
…
𝑥 𝑥 𝑥
From checks to variable
7/27/2023
∑ 𝑓 (0, 𝑥 , 𝑥 ) × ∑ 𝑓 0, 𝑥 , 𝑥 𝑓 𝑥 ∑ 𝑓 𝑥 ,𝑥
∑ 𝑓 (1, 𝑥 , 𝑥 ) × ∑ 𝑓 1, 𝑥 , 𝑥 𝑓 𝑥 ∑ 𝑓 𝑥 ,𝑥
∑𝒙𝟐𝒙𝟑 𝑓 (0, 𝒙𝟐 , 𝒙𝟑 ) × 1 × 1 ∑𝒙𝟒𝒙𝟔 𝑓 0, 𝒙𝟒 , 𝒙𝟔 × 𝑓 𝒙𝟒 ∑ 𝑓 𝒙𝟒 , 𝑥 ×1
𝑥
∑𝒙𝟐𝒙𝟑 𝑓 (1, 𝒙𝟐 , 𝒙𝟑 ) × 1 × 1 ∑𝒙𝟒𝒙𝟔 𝑓 1, 𝒙𝟒 , 𝒙𝟔 × 𝑓 𝒙𝟒 ∑ 𝑓 𝒙𝟒 , 𝑥 ×1
𝑓 𝑓
𝑓 (0) × ∑ 𝑓 (0, 𝑥 ) 1
𝑓 (1) × ∑ 𝑓 (1, 𝑥 ) 1
1 1
𝑥 𝑥 𝑥 𝑥
1 1
𝑓 (0) ∑𝒙𝟓 𝑓 (0, 𝒙𝟓 ) × 1
𝑓 (1) ∑𝒙𝟓 𝑓 (1, 𝒙𝟓 ) × 1
𝑓 𝑓
1
𝑓 𝑥 , 𝑥 , 𝑥 𝑓 𝑥 , 𝑥 , 𝑥 𝑓 𝑥 𝑓 (𝑥 , 𝑥 ) 1
, , , , 𝑥
7/27/2023
Belief Propagation – Final
comments
Applications:
• In a tree: BP compute exactly the bit-flip probabilities.
• In a graph: BP compute an approximation of the bit-flip
probabilities.
• For LDPC codes: For LDPC code with large girth (no short cycle),
BP compute a good approximation of the bit-flip probabilities.
• Progressive edge growth: Algorithm producing LDPC codes with large
girth.
7/27/2023
The quantum decoding
problem
7/27/2023
1-p
0 0
p
Depolarizing channel
p
1 1-p 1
1-p Classical binary symmetric channe
𝜌 𝜌
p/3
𝑋𝜌𝑋
p/3
p/3 𝑌𝜌𝑌
𝑍𝜌𝑍
7/27/2023
First decoding attempt: BP
Classical case:
• Use BP to compute 𝑃 𝑥 = 0 𝑦) and 𝑃 𝑥 = 1 𝑦).
• Correct by selecting the most likely value 𝑥 = 0 or 1.
Quantum case:
• Use BP to compute 𝑃 𝐸 = 𝐼 𝑠), 𝑃 𝐸 = 𝑋 𝑠), 𝑃 𝐸 = 𝑌 𝑠) and 𝑃 𝐸 = 𝑍 𝑠).
• BP does not perform well for two reasons:
• The quantum Tanner graph contains many 4-cycles because of the
commutation relations.
• The event 𝐸 = 𝐼 is not well defined up to a stabilizer.
7/27/2023
UF decoder for LDPC
codes
7/27/2023
Separation of X and Z errors
In what follows we focus on Z errors.
7/27/2023
Error detection
= Z error Z Z
= check with
value 0 Z
= check with
value 1
A chain of errors is detected
at its endpoints
7/27/2023
Trivial errors and logical
errors
Paths connecting the Paths connecting the
Loops are trivial errors.
same side are two opposite sides are
trivial errors. logical errors.
No effect
7/27/2023
Union-Find decoder
Union-Find decoder:
1. Grow clusters around
check with value 1.
2. Stop growing a cluster
when it becomes
correctable.
3. Correct each cluster
independently.
Remark:
We track the growing
cluster using a Union-Find
data structure which leads
Delfosse, Nickerson (2017) arxiv1709.06218 to an almost-linear
complexity.
7/27/2023
The problem with LDPC codes
Clusters grow
too fast!
7/27/2023
Union-Find decoder for QLDPC
codes
Input: A syndrome value 𝑠 = 0 or 1 for each Z check.
Output: A correction for X errors.
1. Initialize ℇ = set of Z checks with syndrome 1. (ℇ = growing
clusters)
2. While there exist an uncorrectable cluster in ℇ:
3. Grow all the clusters in ℇ.
4. Check if the clusters are correctable.
5. Find a correction inside each cluster of ℇ.
6. Return the product of the corrections of the clusters.
Delfosse, Londe, Beverland (2021)
arxiv:2103.08049
7/27/2023
The covering radius
Def. The covering radius of a
syndrome s is the min radius such
that the red balls cover an error
with syndrome s.
Theorem (informal). If the
covering radius of the syndrome is
small, then the Union-Find decoder
succeeds.
Applications: The UF decoders
corrects 𝑛 errors for:
error • Quantum expander codes
detection • Hyperbolic codes1 in
dimension 𝐷 ≥ 3 [Guth,
Delfosse, Londe, Beverland (2021) Lubotzky, (2013)]
arxiv:2103.08049 • Toric codes in dimension 𝐷 ≥ 3
7/27/2023
Union-Find decoder -
Complexity
Complexity:
• For surface codes and color codes: 𝑂(𝑛𝛼(𝑛)).
𝛼(𝑛) is the inverse of Ackermann’s function.
• For LDPC codes: 𝑂(𝑛 ).
Research question: Improve the complexity of the UF decoder for LDPC
codes.
Research question: Design a UF decoder that corrects (d-1)/2 errors for
toric codes in all dim 𝐷 ≥ 3.
See section 7 of arxiv:2103.08049.
7/27/2023
BP-OSD
7/27/2023
BP+OSD0 decoder
error = ( 0 0 0 1 0 0 0 )
H = 0
1 0 1 0 1 0 1 => Syndrome s = Goal: Find a likely error x with
0
0 1 1 0 0 1 1 H x = s
1
0 0 0 1 1 1 1
(.12 .17 .05 .31 .32 .06
1. Estimate all bit flip
.01 )
probabilities using BP.
1 0 0 2. Select a basis H’ of columns
H’ = 0 0 1 made with highest probability
1 1 0
columns.
=> x’ = ( 0 1 0 ) 3. Solve H’ x’ = s.
4. Construct x from x’.
=> x = ( 0 0 0 1 0 0 0 )
Panteleev, Kalachev - arXiv:1904.02703.
7/27/2023
BP+OSD0 decoder - Complexity
Complexity:
• with OSD0: 𝑂(𝑛 ).
• with OSDw: 𝑂(2 𝑛 ).
Panteleev, Kalachev -
arXiv:1904.02703.
7/27/2023
Conclusion: Which decoder
should we use?
• PB: Does not work well with
quantum LDPC because of
short cycles
• UF for QLDPC: corrects a
poly number of errors but
may reduce the distance
• BP-OSD: Heuristic but seems
to behave well in
simulation.