Quantum LDPC codes
Lecture 2
Nicolas Delfosse
Microsoft
PCMI Summer School 2023
Overview of lecture 2
• Examples of quantum LDPC codes
• Syndrome extraction circuits for
surface codes
• Syndrome extraction circuits for LDPC
codes
• Performance of QLDPC codes
Classical and quantum
Hamming codes
Quantum codes detect X errors and Z errors:
Classical code detect bit flips: 0 1 1 Measure
𝑋 𝑋 𝑋 𝑋
Fli
p
X Z
1 0 0
1 0 1
𝑥 +𝑥 +𝑥 +𝑥
Measure
𝑍 𝑍 𝑍 𝑍
Design flow
Pick a
cellulation Kitaev
Only used to Define qubits and
define the Build the Tanner
stabilizer graph
code generators
Pick a pair of
Tanner graph HGP
The rotated surface
code
Planar cellulation
Instead of a torus, we consider a planar region:
• No identification of the opposite side.
• Rotate the square grid.
• Cute the corners faces and vertices.
Definition of the rotated
surface code
We use Kitaev’s construction for our rotated
planar cellulation:
X X • Place a qubit on each edge.
X
• Define a X stabilizer generator for each
X
vertex.
Z Z
• Define a Z stabilize generator for each
Z Z face.
Remark.
• The boundary vertices and faces define
weight-2 generators.
Tanner graphs of the rotated
surface code
3 x 3 surface code 5 x 5 surface code
Corrects 1 error Corrects 2 errors
The problem with surface codes: The encode only 1 logical qubit.
Hypergraph Product
(HGP) Codes
Example – Hypergraph product
code
Consider two bipartite graph
• Place a qubit on each circle-circle.
• Place a qubit on each square-square.
• Define a X generator for each square-
circle.
X Z Z Z • Define a Z generator for each circle-
square.
X
What is n?
X • n=11
Z
What is the first stabilizer generator?
• III XII XII XI
Number of logical qubits of
HGP codes
Theorem. For HGP(𝐶 , 𝐶 ) codes, we have
• 𝑛=𝑛 𝑛 +𝑟 𝑟
• 𝑘 =𝑘 𝑘 +𝑘 𝑘
• 𝑑 ≥ min 𝑑 , 𝑑 , 𝑑 𝑑
• If 𝑘 > 0, then 𝑑 ≤ 𝑑
• If 𝑘 > 0, then 𝑑 ≤ 𝑑
By selected random sparse graph we can achieve 𝑘 ∝ 𝑛 and 𝑑 ∝ 𝑛.
A family of LDPC codes with
constant rate
Select two random Tanner graphs with
• 4s bits with degree 3.
• 3s checks with degree 4.
We get HGP codes with
• 𝑛 = 25𝑠
• 𝑘=𝑠
• Generator degree = 7
• Qubit degree = 6 or 8
We also impose girth ≥ 8 and we select the best code out of 50 – 1000
samples.
Surface codes vs LDPC codes
Code Surface codes LDPC codes
# logical 1 𝑛
qubits k 25
Measurement 4 7
weight
# ancilla 𝑛 ?
qubits
Syndrome extraction
circuits
Classical vs Quantum error
correction
Bit
0 1 1 0 1 0 0 0 1 1 1 1 0 0
flips Correctio
n
0 0 0 Highly
1 0 0
reliable
classical
machine
Classical vs Quantum error
correction
Highly
reliable
Quantum
0
machine1 1
Pauli
error E
𝜓 ∈ stabilizer code 𝐸𝜓 Correctio
n
What is the issue?
Highly
1 0 1
Reliable quantum machines do not exist.
reliable
Quantum
Instead, we use additional noisy qubits.
machine
Measurement of a X check
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
The problem with high random
stabilizer codes
Question.
Can we use this noisy circuit with
random stabilizer codes?
Strategy:
• Suppose that we have 1000 qubits.
• Pick a random [[1000, 500]
| +>
stabilizer code.
• Measure the 500 stabilizers
generators.
Syndrome extraction
circuits for surface
codes
Syndrome extraction
circuit | +>
| +> | +> | +>
Z Z
flip
| +> | +> | +> | +>
X plaquette circuit
| +>
Surface codes
Why surface codes?
• High noise threshold
(about 1%).
• Implemented with 2D local
gates.
Main issue:
• Thousands of physical
qubits per logical qubit.
Here: 1250 physical qubits 25x25 surface code:
Physical error rate: Logical
error rate:
Syndrome extraction
circuits for LDPC
codes
Can we implement quantum LDPC
codes?
Typical LDPC code Typical quantum computer
Main results
With 2D local gates:
arxiv:2109.14
• Need large depth circuits or many ancilla 599
qubits.
• Numerically: poor performance.
With long-range connections: arxiv:2109.14
• Layout based on only a few planar layers. 609
• Numerically outperform surface codes.
Bounds on syndrome extraction
circuits
For surface codes: depth = 6.
Theorem. (informal) For quantum LDPC codes implemented with 2D
local gates:
depth
where q = total number of qubit used.
Constant depth Constant qubit
overhead
Bound # ancilla ≥ Depth ≥ constant × 𝑛
constant × 𝑛
Saturating circuit Switch-based HGP code circuit
circuit
(next slide)
2D local circuits
Simultaneous measurement of
all the X checks
[Link] an edge coloration
[Link] a readout qubits in |+⟩ for
each check.
[Link] each color c do:
4. Apply a CNOT on each edge
with color c
[Link] readout qubits in the X | +> | +> | +>
basis.
Switch-based circuit
3 4 5 1 6 2 7
3 4 1
3 1 4
1 3 2
1 2 3
1 2 3
Bell 1 2 3
Bell
1 2 3
2D local vs fully connected
implementation
• With fully connected
qubits:
• # ancillas:𝑂(𝑛)
• depth: 𝑂 1
• With 2D local gates: Cost of locality
• # ancilla qubits:
𝑂(𝑛)
• Depth 𝑂( 𝑛)
With long-range gates
Naïve layout with long-range
connectivity
Issue:
• Crossing gates may
induce correlated
errors.
Goal:
• A small number of
crossing gates.
• Short depth.
Graph with 100 vertices with degree 8
Planar decomposition of the
Tanner graph
Degree = 4 # planar layers = 2
-planar
layout
Assumptions:
• CSS code.
• Degree(Tanner graph)
= 𝛿.
We constructed a
syndrome extraction
circuit with:
• planar layers of
gates.
• Depth = 2 𝛿 + 2.
Improved depth for HGP
codes.
Numerical
results
Noise threshold:
0.28% (instead of 0.7% for surface codes)
# physical qubits per logical qubit:
49 (instead of thousands for surface codes)