Quantum fault-tolerance and locality

Robert König

Theory of Complex Quantum Systems

Department of Mathematics

Talk on joint work with

School of Computation, Information and Technology

Shin Ho Choe

Technical University of Munich

arXiv:2402.13863

robert.koenig@tum.de

Colloquium of the Extreme
Universe Collaboration
April 19, 2024
1

Quantum computing long-term vision
Molecular structure andmaterial science simulations

Integer factoring

Quantum walks

Universal Fault-Tolerant
Quantum Computer

Semidefinite
programming

Q://

Grover search

HHL algorithm
𝐴𝑥 = 𝑏

Quantum computing 101: Starting the computation𝑛-qubit state spacecomputational basis elementℂ2 ⊗𝑛 = ℂ2 ⊗ ⋯ ⊗ ℂ2

(Hilbert space)|𝑥⟩ = 𝑥1 ⊗ ⋯ ⊗ 𝑥𝑛
𝑥 = 𝑥1 , … , 𝑥𝑛 ∈ {0,1}𝑛(tensor product) orthonormal basis element

A system of 𝑛 qubits can be initialized in a basis state |𝑥⟩ for any 𝑥 ∈ 0,1 𝑛|𝑥⟩𝑛-bit input“converted” tocomputational
basis stateQuantum Computing 101: Quantum gates𝑛-qubit evolution/gate

𝑈: ℂ2 ⊗𝑛 → ℂ2 ⊗𝑛 linear∥ 𝑈Ψ ∥=∥ Ψ ∥ for all Ψ ∈ ℂ2 ⊗𝑛unitary

Gates are norm-preserving linear maps (unitary matrices).
Hadamard

Phase shift

𝐻

𝑆

𝑎

1

0 → |0⟩

𝑏

0 →

1 →

2
1
2

0 + |1⟩0 − |1⟩

1 → 𝑖|1⟩

Controlled-NOT𝑎, 𝑏 → |𝑎, 𝑎 ⊕ 𝑏⟩
00 ↦ 00
01 ↦ 0110 ↦ 1111 ↦ |10⟩

Quantum Computing 101: Quantum gates
Gates can be applied (simultaneously) to (disjoint) subsets of qubits

S-gate applied to qubit 1

H-gate applied to qubit 3

𝑆(simultaneously applied)
S-gate on qubit 1
CNOT on qubits 2 & 3
H on qubit 4

𝑆
𝐻
𝐻

unitarymapQuantum computing 101: Measurements
൛states on ℂ2 ⊗𝑛 ൟ𝜓 =→ {probability distributions on {0,1}𝑛 }↦෍ 𝜓𝑥 𝑥𝑝𝑥 = 𝜓𝑥 2

𝑥∈ 0,1 𝑛

Measurement allows one to sample 𝑥 ∈ 0,1 𝑛 from the probability distribution 𝑝𝑥

𝜓𝑥 ∈ 0,1 𝑛Quantum Computing 101: Quantum circuits
𝑆
|𝑥⟩

𝐻

𝑛-bit input

𝐻time

The behavior of the circuit iscompletely described by theconditional distribution

𝑛-bit output 𝑧Quantum Computing 101: Quantum circuits
𝑆
|𝑥⟩

𝐻

𝑛-bit input

𝑛-bit output 𝑧

𝐻time

A depth-𝒅 quantum circuit consists of 𝑑 time steps.
Each time step contains one- and two-qubit gates acting on disjoint subsets of qubits.

Universal gate sets and the Solovay-Kitaev Theorem
Basic question:

What is needed to apply a general unitary 𝑈 on ℂ2 ⊗𝑛 ?
Which gates should we be using?

Hadamard

Phase shift

𝐻

𝑆

𝑎

1

0 → |0⟩

𝑏

0 →

1 →

2
1
2

0 + |1⟩0 − |1⟩

1 → 𝑖|1⟩

Controlled-NOT𝑎, 𝑏 → |𝑎, 𝑎 ⊕ 𝑏⟩
00 ↦ 00
01 ↦ 0110 ↦ 1111 ↦ |10⟩

Universal gate sets and the Solovay-Kitaev Theorem
Basic question:

What is needed to apply a general unitary 𝑈 on ℂ2 ⊗𝑛 ?

Answer: It suffices to be able to apply any gate from a (possibly finite) universal gate set.

Definition: A family 𝒢 = ቄ𝑈𝑗 ∣ 𝑈𝑗 unitary on ℂ2 ⊗𝑛 ൟ is universal if𝑥𝑥⟨𝒢⟩ = 𝑈𝑗11 ⋯ 𝑈𝑗𝑀𝑀 | 𝑀 ∈ ℕ, 𝑥𝑗 ∈ {±1}is dense in the unitary group U 2𝑛 .
Theorem (Solovay & Kitaev):
Let 𝒢 be a universal gate set for 𝑆𝑈 2 closed under taking
inverses. There is an algorithm which, given 𝜀 > 0 and any
input unitary 𝑈 ∈ 𝑆𝑈(2), outputs a sequence 𝑔1 , … , 𝑔𝐿 ∈ 𝒢
of length
𝐿 = 𝑂 log 𝛼 1/𝜀where 𝛼 ≈ 2.7, such that 𝑈 − 𝑔1 ⋯ 𝑔𝐿 < 𝜀Furthermore, this algorithm runs in polynomial time in 𝐿.

𝑈≈with 𝒢 ≔ {

𝐻

,

𝑇

,

𝑇, †

}

Universal gate sets and the Solovay-Kitaev Theorem
Basic question:

What is needed to apply a general unitary 𝑈 on ℂ2 ⊗𝑛 ?

Answer: It suffices to be able to apply any gate from a (possibly finite) universal gate set.

Definition: A family 𝒢 = ቄ𝑈𝑗 ∣ 𝑈𝑗 unitary on ℂ2 ⊗𝑛 ൟ is universal if𝑥𝑥⟨𝒢⟩ = 𝑈𝑗11 ⋯ 𝑈𝑗𝑀𝑀 | 𝑀 ∈ ℕ, 𝑥𝑗 ∈ {±1}is dense in the unitary group U 2𝑛 .
Examples for 𝑛 = 1 (a qubit)
Universal gate sets:

•

𝑅𝑋 𝛼

• {𝑇, 𝐻}𝛼∈[0,2𝜋) ∪𝑅𝑍 𝛽𝑅𝑍 𝜃 = 𝑒 −𝑖𝜃𝑍𝑅𝑋 𝜃 = 𝑒 −𝑖𝜃𝑋𝛽∈[0,2𝜋)

𝐻=

1
2

1 1
1 −1

𝑖𝜋/8
𝑇= 𝑒
0

0
𝑒 −𝑖𝜋/8

Universal gate sets and the Solovay-Kitaev Theorem
Basic question:

What is needed to apply a general unitary 𝑈 on ℂ2 ⊗𝑛 ?

Answer: It suffices to be able to apply any gate from a (possibly finite) universal gate set.

Definition: A family 𝒢 = ቄ𝑈𝑗 ∣ 𝑈𝑗 unitary on ℂ2 ⊗𝑛 ൟ is universal if𝑥𝑥⟨𝒢⟩ = 𝑈𝑗11 ⋯ 𝑈𝑗𝑀𝑀 | 𝑀 ∈ ℕ, 𝑥𝑗 ∈ {±1}is dense in the unitary group U 2𝑛 .
NOT universal :Pauli group

𝒞1 =

𝑛

𝑋𝑗 , 𝑌𝑗 , 𝑍𝑗 𝑗=1

𝑋=

0 1
0 −𝑖
1 0
,𝑌 =
,𝑍 =
1 0
𝑖 0
0 −1

where 𝑋𝑗 = 𝐼 ⊗ ⋯ 𝐼 ⊗ 𝑋⊗ 𝐼 ⋯ 𝐼
𝑗

Clifford group

𝒞2 = 𝑈 ∈ U 2𝑛 ∣ 𝑈𝒞1 𝑈 † ⊂ 𝒞1

𝐻=

1 1
2 1

1
1
,𝑆 =
0
−1

0
𝑖

Sergey Bravyi and Alexei Kitaev. Universal quantum computation with ideal Clifford gates and noisy ancillas. Phys. Rev. A, 71:022316, Feb 2005.

Magic state injection: useful gates from resource states
𝑇
𝑖𝜋/8
𝑒
𝑇=
0

𝑆

=
0

𝑆=

1 0
0 𝑖

|𝐴⟩

𝑒 −𝑖𝜋/8|𝐴⟩ = 2−1/2 |0⟩ + 𝑒 𝑖𝜋/4 |1⟩

Idea: Implement certain gates by using• “magic” resource states

The following set of one- and twoqubit operations give computational
universality:• State preparation of a single-qubit
1state |0⟩ or 2 |0⟩ + 𝑒 𝑖𝜋/4 |1⟩• (computational basis) measurements and• Application of a single- or twoqubit Clifford unitary (possibly theidentity)• adaptive (but simple) operations (e.g., Clifford
unitaries/Paulis)• Measurement of any qubit in thecomputational basis

Definition of adaptive circuits and (quantum) circuit depth
| 0⟩
| 0⟩
|𝐴⟩

H

| 0⟩
|𝐴⟩ H
|𝐴 ⟩
| 0⟩

H

Z

𝑋 𝑧Ƹ1

H
Z

H

𝑚1

|0⟩

𝑌 𝑧Ƹ2

S

|0⟩

X

𝑚2
𝑚r

S
Z
H
X

S

|0⟩

|𝐴 ⟩

𝑍 𝑧Ƹ𝑛

S

S

H

Classical
computation

Classical
computation

Adaptivity: Each two-qubit operation may depend (in an efficiently computable manner)
on previous measurement outcomes.
(Quantum) circuit depth of 𝓠: = number 𝑇 of layers.

XS

Definition of adaptive circuits and (quantum) circuit depth
| 0⟩
| 0⟩
|𝐴⟩

H

| 0⟩
|𝐴⟩ H
|𝐴 ⟩
| 0⟩

H

Z

𝑋 𝑧Ƹ1

H
Z

H

𝑚1

|0⟩

𝑌 𝑧Ƹ2

X

𝑚2
𝑚r

S

S

Each layer ℳ (𝑇) consists in theparallel application of the following|0⟩one- and two-qubit operations:

S
|𝐴 ⟩

𝑍 𝑧Ƹ𝑛

S

H

Classical
computation

Z
H

X
S
• State preparation of a single-qubit
state |0⟩ or

1
2|0⟩ + 𝑒 𝑖𝜋/4 |1⟩

X• Application of a single- or twoqubit Clifford unitary (possibly the|0⟩identity)S• Measurement of any qubit in thecomputational basis
Classical
computation

Adaptivity: Each two-qubit operation may depend (in an efficiently computable manner)
on previous measurement outcomes.
(Quantum) circuit depth of 𝓠: = number 𝑇 of layers.

Definition of adaptive circuits and (quantum) circuit depth
| 0⟩
| 0⟩
|𝐴⟩

H

| 0⟩
|𝐴⟩ H
|𝐴 ⟩
| 0⟩

H

Z

𝑋 𝑧Ƹ1

H
Z

H

𝑚1

|0⟩

𝑌 𝑧Ƹ2

X

𝑚2
𝑚r

S

S

Each layer ℳ (𝑇) consists in theparallel application of the following|0⟩one- and two-qubit operations:

S
|𝐴 ⟩

𝑍 𝑧Ƹ𝑛

S

H

Classical
computation

Z
H

X
S
• State preparation of a single-qubit
state |0⟩ or

1
2|0⟩ + 𝑒 𝑖𝜋/4 |1⟩

X• Application of a single- or twoqubit Clifford unitary (possibly the|0⟩identity)S• Measurement of any qubit in thecomputational basis
Classical
computation

Adaptivity: Each two-qubit operation may depend (in an efficiently computable manner)
on previous measurement outcomes.
(Quantum) circuit depth of 𝓠: = number 𝑇 of layers.

Definition of adaptive circuits and (quantum) circuit depth
| 0⟩
| 0⟩
|𝐴⟩

H

Z

| 0⟩
|𝐴⟩ H
|𝐴 ⟩

H

| 0⟩

H

Z

𝑋 𝑧Ƹ1

H
𝑚1

S

|0⟩

𝑌 𝑧Ƹ2

|0⟩

X

Z
Pairing of qubits in each layer
𝑚2 (support of two-qubit operations)H
S

X

|𝐴 ⟩

|0⟩

𝑚r

S

𝑍 𝑧Ƹ𝑛

S

S

H

Classical
computation

Classical
computation

Adaptivity: Each two-qubit operation may depend (in an efficiently computablemanner) on previous measurement outcomes.
(Quantum) circuit depth of 𝓠: = number 𝑇 of layers.

XS

Definition of adaptive circuits and (quantum) circuit depth
| 0⟩
| 0⟩
|𝐴⟩

H

Z

| 0⟩
|𝐴⟩ H
|𝐴 ⟩

H

| 0⟩

H

Z

𝑋 𝑧Ƹ1

H
𝑚1

S

|0⟩

𝑌 𝑧Ƹ2

|0⟩

X

Z
Pairing of qubits in each layer
𝑚2 (support of two-qubit operations)H
S

X

|𝐴 ⟩

|0⟩

𝑚r

S

𝑍 𝑧Ƹ𝑛

S

S

H

Classical
computation

Classical
computation

Adaptivity: Each two-qubit operation may depend (in an efficiently computablemanner) on previous measurement outcomes.
(Quantum) circuit depth of 𝓠: = number 𝑇 of layers.

XS

Definition of adaptive circuits and (quantum) circuit depth
S

Each layer ℳ (𝑇) consists in theparallel application of the following|0⟩one- and two-qubit operations:

Consider a 𝑛-qubit circuit 𝒬 = ℳ (𝑇) ∘ ⋯ ∘ ℳ 1

XS• State preparation of a single-qubit

composed of 𝑇 layers ℳ (1) , … , ℳ (𝑇)state |0⟩ orThat is, there are for each 𝑡 ∈ [𝑇]:(i) a pairing(𝑡) (𝑡)𝑖𝑟 , 𝑗𝑟(ii) two-qubit operations𝑘
𝑟=1|0⟩ + 𝑒 𝑖𝜋/4 |1⟩

X• Application of a single- or twoqubit Clifford unitary (possibly the|0⟩identity)of the set of qubits 𝑛 : = 1, … , 𝑛𝑘(𝑡,𝑟)ℳ (𝑡,𝑟) 𝑟=1 such that ℳ (𝑡) =⊗𝑘𝑟=1 ℳ (𝑡) (𝑡)
𝑄 𝑄
𝑖𝑟

𝑗𝑟

S

• Measurement of any qubit in thecomputational basis
Classical
computation

Adaptivity: Each two-qubit operation may depend (in an efficiently computablemanner) on previous measurement outcomes.
(Quantum) circuit depth of 𝓠: = number 𝑇 of layers.

12Main problem addressed in this talk:
How to deal with real-world constraints

Src: wikipedia

Src: people.math.sc.edu/Burkardt/c_src/image_denoise/image_denoise.html

Real-world obstacle I:
Hardware architectures and geometric locality

Two-qubit operations
applicable only to neighboring
pairs of qubits on a graph!

Real-world obstacle I:
Geometric locality: (gate) connectivity
full connectivity

limited connectivity

2-qubit operations
between….
…… any pair of qubits…… e.g., nearest andnext-to-nearest neighboring qubits

Real-world obstacle II: Noisy building blocks

Errors can affect all involved operations: preparation, storage, gates and readout.

This talk: How to use
noisy, local operations

noisy qubits/
operations

ideal qubits/
operations

How to use a limited-connectivity, noisy device tosimulate an ideal, fully-connected device?
Low-connectivity
noisy device

Fully connectedideal device• How many (additional) qubits are needed?
• What is the time required/blow-up inquantum circuit depth?

How to use noisy
operations

noisy qubits/
operations

ideal qubits/
operations

Fault-tolerance
construction
Fully connectedideal device

Fully connectednoisy device

ignoring locality considerations

How to use noisy, local
operations instead ofnoisy, (general) operations

noisy qubits/
operations

noise-robust
localizer
Fully connectednoisy device

Low-connectivity
noisy device

ignoring the problem of simulating
an ideal (noise-free) device

This talk: How to use
noisy, local operations

noisy qubits/
operations

Fault-tolerance
construction
Fully connectedideal device

ideal qubits/
operations

noise-robust
localizer
Fully connectednoisy device

Main conceptual consequence:

Fault-tolerance (threshold) considerations and locality restrictions
can be analyzed separately.

Low-connectivity
noisy device

This talk: How to use
noisy, local operations

noisy qubits/
operations

Fault-tolerance
construction
Fully connectedideal device

ideal qubits/
operations

noise-robust
localizer
Fully connectednoisy device

Low-connectivity
noisy device

Main consequence:
Overhead-efficient fault-tolerance constructions incorporating locality constraints.

Fault-tolerance construction of Yamasaki and Koashi
Can the (ideal) circuit 𝒬ideal be
simulated using noisy
operations?
Theorem [1] There is a threshold error strength 𝑝0 > 0 such that for large 𝑛 and 𝜀 ∈ 0,1 :Let 𝒬ideal be a circuit withThen:𝑛 qubits
𝑇(𝑛) = 𝑂 poly 𝑛

There is a circuit 𝒬FT withdepth𝑛 ⋅ 𝑂(1) qubits
𝑇(𝑛) ⋅ exp 𝑂 log 2 (log(𝑛/𝜀))

depthsuch that a noisy implementation of 𝒬FT with local stochastic noise of strength 𝑝 ≤ 𝑝0 has an
output distribution whose 𝐿1 -distance to the output distribution of 𝒬ideal bounded by 𝜀.
[1] Yamasaki and Koashi, Nat. Phys. no. 20, Feb 2024

Main result: Fault-tolerance with local operations in 3D
Can the (ideal) circuit 𝒬ideal be
simulated using noisy, local
operations?
Theorem [1] There is a threshold error strength 𝑝0 > 0 such that for large 𝑛 and 𝜀 ∈ 0,1 :Let 𝒬ideal be a circuit withThen:𝑛 qubits
𝑇(𝑛) = 𝑂 poly 𝑛

There is a 3D-local circuit 𝒬FT withdepth𝑛 ⋅ 𝑂 𝑛1/2 log 3 𝑛 qubits
𝑇(𝑛) ⋅ exp(𝑂(log 2 (log(𝑛/𝜀)) ) depth

such that a noisy implementation of 𝒬FT with local stochastic noise of strength 𝑝 ≤ 𝑝0 has an
output distribution whose 𝐿1 -distance to the output distribution of 𝒬ideal bounded by 𝜀.
[1] RK and Shin Ho Choe, arXiv:2402.13863

Main result: Fault-tolerance with local operations in 3D
Can the (ideal) circuit 𝒬ideal be
simulated using noisy, local
operations?
Theorem [1] There is a threshold error strength 𝑝0 > 0 such that for large 𝑛 and 𝜀 ∈ 0,1 :Let 𝒬ideal be a circuit withThen:𝑛 qubits
𝑇(𝑛) = 𝑂 poly 𝑛

There is a 3D-local circuit 𝒬FT withdepth𝑛 ⋅ 𝑂 𝑛1/2 log 3 𝑛 qubits
𝑇(𝑛) ⋅ exp(𝑂(log 2 (log(𝑛/𝜀)) ) depth

such that a noisy implementation of 𝒬FT with local stochastic noise of strength 𝑝 ≤ 𝑝0 has an
output distribution whose 𝐿1 -distance to the output distribution of 𝒬ideal bounded by 𝜀.
[1] RK and Shin Ho Choe, arXiv:2402.13863

Main result: Fault-tolerance with local operations in 3D
Can the (ideal) circuit 𝒬ideal be
simulated using noisy, local
operations?
Theorem [1] There is a threshold error strength 𝑝0 > 0 such that for large 𝑛 and 𝜀 ∈ 0,1 :Let 𝒬ideal be a circuit withThen:𝑛 qubits
𝑇(𝑛) = 𝑂 poly 𝑛

There is a 3D-local circuit 𝒬FT withdepth𝑛 ⋅ 𝑂 𝑛1/2 log 3 𝑛 qubits
𝑇(𝑛) ⋅ exp(𝑂(log 2 (log(𝑛/𝜀)) ) depth

such that a noisy implementation of 𝒬FT with local stochastic noise of strength 𝑝 ≤ 𝑝0 has an
output distribution whose 𝐿1 -distance to the output distribution of 𝒬ideal bounded by 𝜀.
[1] RK and Shin Ho Choe, arXiv:2402.13863

Main result: Fault-tolerance with local operations in 3D
Can the (ideal) circuit 𝒬ideal be
simulated using noisy, local
operations?
Theorem [1] There is a threshold error strength 𝑝0 > 0 such that for large 𝑛 and 𝜀 ∈ 0,1 :Let 𝒬ideal be a circuit withThen:𝑛 qubits
𝑇(𝑛) = 𝑂 poly 𝑛

There is a 3D-local circuit 𝒬FT withdepth𝑛 ⋅ 𝑂 𝑛1/2 log 3 𝑛 qubits
𝑇(𝑛) ⋅ exp(𝑂(log 2 (log(𝑛/𝜀)) ) depth

such that a noisy implementation of 𝒬FT with local stochastic noise of strength 𝑝 ≤ 𝑝0 has an
output distribution whose 𝐿1 -distance to the output distribution of 𝒬ideal bounded by 𝜀.
[1] RK and Shin Ho Choe, arXiv:2402.13863

This talk: How to use
noisy, local operations

noisy qubits/
operations

Fault-tolerance
construction
Fully connectedideal device

ideal qubits/
operations

noise-robust
localizer
Fully connectednoisy device

Low-connectivity
noisy device

Main consequence:
Overhead-efficient fault-tolerance constructions incorporating locality constraints.

How to use noisy, local
operations instead ofnoisy, (general) operations

noisy qubits/
operations

noise-robust
localizer
Fully connectednoisy device

Low-connectivity
noisy device

ideal qubits/
operations

How to use local
operations

localizer

Low-connectivity
ideal device

Fully connectedideal device

ignoring noiseRouting of qubits in graphs
Given:• A graph 𝐺 = (𝑉, 𝐸) with a qubit 𝑄𝑣 at each vertex 𝑣.
• A special subset 𝑆 = 𝑣1 , … , 𝑣𝑘 of vertices.

Routing of qubits in graphs
Given:• A graph 𝐺 = (𝑉, 𝐸) with a qubit 𝑄𝑣 at each vertex 𝑣.
• A special subset 𝑆 = 𝑣1 , … , 𝑣𝑘 of vertices.
Capabilities: Can apply circuits composed of local and nearest-neighbor operations.

Routing of qubits in graphs
Given:• A graph 𝐺 = (𝑉, 𝐸) with a qubit 𝑄𝑣 at each vertex 𝑣.
• A special subset 𝑆 = 𝑣1 , … , 𝑣𝑘 of vertices.
Capabilities: Can apply circuits composed of local and nearest-neighbor operations.

Routing of qubits in graphs
Given:• A graph 𝐺 = (𝑉, 𝐸) with a qubit 𝑄𝑣 at each vertex 𝑣.
• A special subset 𝑆 = 𝑣1 , … , 𝑣𝑘 of vertices.
Capabilities: Can apply circuits composed of local and nearest-neighbor operations.
Problem input: A pairing

𝑣𝑖𝑟 , 𝑣𝑗𝑟𝑘𝑟=1

of the vertices of 𝑆(𝑟)

Goal: Apply a tensor product ⨂𝑘𝑟=1 ℳ𝑄𝑣 𝑄𝑣
𝑖𝑟

𝑗𝑟of two-qubit operations.

time

Routing of qubits in graphs: SWAP-based protocols

The number of SWAP-gate layers needed may scale linearly (in 1D)!

Entanglement swapping
𝑠1 , 𝑡1
|Φ⟩

𝑅1

|Φ⟩

𝑅2

𝑠𝐷−2 , 𝑡𝐷−2

𝑠2 , 𝑡2
|Φ⟩

𝑅3

⋯

|Φ⟩

𝑅𝐷−1

𝑅𝐷

Start with 𝐷 − 1 EPR pairs arranged on a line
Perform Bell measurements between neighboring pairs|Φ 𝑠,𝑡 ⟩The state after the Bell measurements is equivalent to a
“Pauli-corrupted” long-range entangled Bell stateΦ 𝑠,𝑡 =𝐼 ⊗ 𝑍 𝑠 𝑋 𝑡 |Φ⟩with Bell state determined by𝑠 = σ𝐷−2
𝑗=1 𝑠𝑗 (mod 2),
𝑡 = σ𝐷−2
𝑗=1 𝑡𝑗 (mod 2).

From qubit routing to parallel routing(using entanglement-swapping)
Original graph

Entanglement structure

|Φ⟩
|Φ⟩

|Φ⟩
|Φ⟩

|Φ⟩
|Φ⟩

Each edge is replaced by a Bell state |Φ⟩
|Φ⟩

|Φ⟩

From qubit routing to parallel routing(using entanglement-swapping)
Original graphpairing

𝑣𝑖𝑟 , 𝑣𝑗𝑟𝑘
𝑟=1

Entanglement structure

|Φ⟩
|Φ⟩

|Φ⟩
|Φ⟩

|Φ⟩
|Φ⟩

Each edge is replaced by a Bell state |Φ⟩
|Φ⟩

|Φ⟩

From qubit routing to parallel routing(using entanglement-swapping)
Original graphpairing

𝑣𝑖𝑟 , 𝑣𝑗𝑟𝑘
𝑟=1

Edge-disjoint family 𝜋𝑟 𝑘𝑟=1 of paths whose endpoints
𝜕𝜋𝑟 = 𝑣𝑖𝑟 , 𝑣𝑗𝑟 correspond to pairing

𝑣𝑖𝑟 , 𝑣𝑗𝑟

Entanglement structure
Entanglement swapping along each path 𝜋𝑟(executed in parallel)𝑘

𝑟=1

A combinatorial problem: Parallel routing in a graph
Given: A graph 𝐺 = (𝑉, 𝐸)
Definition: A subset 𝑆 = 𝑣1 , … , 𝑣2𝑘 of vertices is called parallel-routable :⇔For any pairing•

𝑣𝑖𝑟 , 𝑣𝑗𝑟𝑘𝑟=1

of 𝑆, there is collection 𝜋𝑟 𝑘𝑟=1 of paths such that

𝜋𝑟 𝑘𝑟=1 are pairwise edge-disjoint• 𝜕𝜋𝑟 = 𝑣𝑖𝑟 , 𝑣𝑗𝑟 for each 𝑟 = 1, … , 𝑘.
Problem: Find a parallel-routable set 𝑆 of maximal size.

Parallel routing in 2D grid graphs
Definition: A subset 𝑆 = 𝑣1 , … , 𝑣2𝑘 of vertices is called parallel-routable
For any pairing•

𝑣𝑖𝑟 , 𝑣𝑗𝑟

𝑘
𝑟=1

:⇔

of 𝑆, there is collection 𝜋𝑟 𝑘𝑟=1 of paths such that

𝜋𝑟 𝑘𝑟=1 are pairwise edge-disjoint• 𝜕𝜋𝑟 = 𝑣𝑖𝑟 , 𝑣𝑗𝑟 for each 𝑟 = 1, … , 𝑘.

Theorem: The 2D grid graph 𝑃𝐿 × 𝑃𝐿 contains a parallel-routable set 𝑆 of size 𝑆 = 𝐿.
The length of each path 𝜋𝑟 is ≤ 2𝐿, and the paths can be efficiently computed from the pairing.
Proof: Consider the set 𝑆 = 𝑣𝑟 = (𝑟, 𝑟) ∣ 𝑟 = 1, … , 𝐿 .

Parallel routing in 2D grid graphs
Definition: A subset 𝑆 = 𝑣1 , … , 𝑣2𝑘 of vertices is called parallel-routable
For any pairing•

𝑣𝑖𝑟 , 𝑣𝑗𝑟

𝑘
𝑟=1

:⇔

of 𝑆, there is collection 𝜋𝑟 𝑘𝑟=1 of paths such that

𝜋𝑟 𝑘𝑟=1 are pairwise edge-disjoint• 𝜕𝜋𝑟 = 𝑣𝑖𝑟 , 𝑣𝑗𝑟 for each 𝑟 = 1, … , 𝑘.

Theorem: The 2D grid graph 𝑃𝐿 × 𝑃𝐿 contains a parallel-routable set 𝑆 of size 𝑆 = 𝐿.
The length of each path 𝜋𝑟 is ≤ 2𝐿, and the paths can be efficiently computed from the pairing.
Proof: Consider the set 𝑆 = 𝑣𝑟 = (𝑟, 𝑟) ∣ 𝑟 = 1, … , 𝐿 .

Parallel routing in 2D grid graphs
Definition: A subset 𝑆 = 𝑣1 , … , 𝑣2𝑘 of vertices is called parallel-routable
For any pairing•

𝑣𝑖𝑟 , 𝑣𝑗𝑟

𝑘
𝑟=1

:⇔

of 𝑆, there is collection 𝜋𝑟 𝑘𝑟=1 of paths such that

𝜋𝑟 𝑘𝑟=1 are pairwise edge-disjoint• 𝜕𝜋𝑟 = 𝑣𝑖𝑟 , 𝑣𝑗𝑟 for each 𝑟 = 1, … , 𝑘.

Theorem: The 2D grid graph 𝑃𝐿 × 𝑃𝐿 contains a parallel-routable set 𝑆 of size 𝑆 = 𝐿.
The length of each path 𝜋𝑟 is ≤ 2𝐿, and the paths can be efficiently computed from the pairing.
Proof: Consider the set 𝑆 = 𝑣𝑟 = (𝑟, 𝑟) ∣ 𝑟 = 1, … , 𝐿 .

Parallel routing in 2D grid graphs
Definition: A subset 𝑆 = 𝑣1 , … , 𝑣2𝑘 of vertices is called parallel-routable
For any pairing•

𝑣𝑖𝑟 , 𝑣𝑗𝑟

𝑘
𝑟=1

:⇔

of 𝑆, there is collection 𝜋𝑟 𝑘𝑟=1 of paths such that

𝜋𝑟 𝑘𝑟=1 are pairwise edge-disjoint• 𝜕𝜋𝑟 = 𝑣𝑖𝑟 , 𝑣𝑗𝑟 for each 𝑟 = 1, … , 𝑘.

Theorem: The 2D grid graph 𝑃𝐿 × 𝑃𝐿 contains a parallel-routable set 𝑆 of size 𝑆 = 𝐿.
The length of each path 𝜋𝑟 is ≤ 2𝐿, and the paths can be efficiently computed from the pairing.
Proof: Consider the set 𝑆 = 𝑣𝑟 = (𝑟, 𝑟) ∣ 𝑟 = 1, … , 𝐿 .

Lemma A sufficient condition for the existence of 𝜋𝑟 𝑘𝑟=1 is(*)

𝑥 𝑣𝑖𝑟 , 𝑥 𝑣𝑗𝑟
𝑦 𝑣𝑖𝑟 , 𝑦 𝑣𝑗𝑟∩ 𝑥 𝑣𝑖𝑠 , 𝑥 𝑣𝑗𝑠∩ 𝑦 𝑣𝑖𝑠 , 𝑦 𝑣𝑗𝑠= ∅ for 𝑟 ≠ 𝑠= ∅ for 𝑟 ≠ 𝑠“Projections of endpoints onto coordinate axes do
not intersect for different pairs.”

Parallel routing in 3D grid graphs
Theorem: The 3D grid graph 𝑃𝐿 × 𝑃𝐿 × 𝑃4𝐿 contains a parallel-routable set 𝑆
of size 𝑆 = 𝐿2 . Corresponding paths have length at most 10L.
Proof: Consider the set 𝑆 = { 𝑥, 𝑦, 1 | 𝑥, 𝑦 ∈ {1, … , 𝐿}}=: ℱ1

Parallel routing in 3D grid graphs
Theorem: The 3D grid graph 𝑃𝐿 × 𝑃𝐿 × 𝑃4𝐿 contains a parallel-routable set 𝑆
of size 𝑆 = 𝐿2 . Corresponding paths have length at most 10L.
Proof: Consider the set 𝑆 = { 𝑥, 𝑦, 1 | 𝑥, 𝑦 ∈ {1, … , 𝐿}}
We use a greedy algorithm that given a pairingcollection 𝜋𝑟 𝑘𝑟=1 of paths as follows:

𝑣𝑖𝑟 , 𝑣𝑗𝑟

𝑘
𝑟=1

=: ℱ1

constructs a

For 𝑟 = 1, … , 𝑘:
1. Find the minimal floor level z such that adding Π𝑧 𝑣𝑖𝑟 , Π𝑧 𝑣𝑗𝑟 (where𝜋𝑧 (𝑥, 𝑦, 1) = (𝑥, 𝑦, 𝑧)) to the floorℱ𝑧 : = { 𝑥, 𝑦, 𝑧 | 𝑥, 𝑦 ∈ {1, … , 𝐿}}does not violate (*)
2. Then use “vertical” elevators and the Lemma to construct 𝜋𝑟Parallel routing in 3D grid graphs
Theorem: The 3D grid graph 𝑃𝐿 × 𝑃𝐿 × 𝑃4𝐿 contains a parallel-routable set 𝑆
of size 𝑆 = 𝐿2 . Corresponding paths have length at most 10L.
Proof: Consider the set 𝑆 = { 𝑥, 𝑦, 1 | 𝑥, 𝑦 ∈ {1, … , 𝐿}}=: ℱ1

(Ideal) localization

Theorem:
There is an adaptive circuit 𝒬 ′ withthe following properties:

Given: adaptive quantum circuit 𝒬

1. 𝒬 ′ uses 𝒏 ⋅ 𝑶 𝒏𝟏/𝟐 qubits

on 𝒏 qubitsof depth 𝑻
involving non-local operations

and is local when these are arranged
localizer

on a 3D grid graph.
2. 𝒬 ′ has quantum depth of order 𝑶(𝑻).
3. 𝒬 ′ simulates 𝒬 exactlyThis talk: How to use
noisy, local operations

noisy qubits/
operations

Fault-tolerance
construction
Fully connectedideal device

ideal qubits/
operations

noise-robust
localizer
Fully connectednoisy device

Low-connectivity
noisy device

Main consequence:
Overhead-efficient fault-tolerance constructions incorporating locality constraints.

(Standard) Fault-tolerance constructions
Fault-tolerance
construction
Fully connectedideal device(ignoring locality)
Fully connectednoisy device

How to realize simulate an (ideal, i.e., noise-free general) circuit by a noisy(general) circuit.
(other researchers’ fantastic achievements!)

Noise in quantum circuits: basic properties
Errors can affect all involved operations: preparation, storage, gates and readout.

preparation
faultyoperationmodel:

gate

memory/wait location

measurement

Local stochastic noise
Assumption
Errors are(randomly
chosen)Pauli errors.

Justification
Probabilistic Pauli noise is
no more detrimental than
general coherent noise.

argument based on linearity/operator bases:
Ekert, Macchiavello, Phys. Rev. Lett. 77, 2585 (1996)

evidence from numerical simulation for surface codes:
Bravyi, Englbrecht, K, Peard npj Quant. Inf., vol. 4, no. 55 (2018)
can be achieved by Pauli twirlingHigh weighterrors are
exponentiallysuppressed(unlikely).

Physical processes are
typically local/two-body.

Def. A random n-qubit Pauli error 𝐸 is called
local stochastic noise of strength 𝑝 ∈ [0,1] if

Pr[𝐹 ⊆ Supp(𝐸)] ≤ 𝑝|𝐹| for all 𝐹 ⊂ {1, … , 𝑛}Notation: 𝐸~𝒩(𝑝).

Such Pauli errors can be arbitrarily
correlated: no locality constraints

Local stochastic noise
Assumption
Errors are(randomly
chosen)Pauli errors.

Justification
Probabilistic Pauli noise is
no more detrimental than
general coherent noise.

argument based on linearity/operator bases:
Ekert, Macchiavello, Phys. Rev. Lett. 77, 2585 (1996)

evidence from numerical simulation for surface codes:
Bravyi, Englbrecht, K, Peard npj Quant. Inf., vol. 4, no. 55 (2018)
can be achieved by Pauli twirlingHigh weighterrors are
exponentiallysuppressed(unlikely).

Physical processes are
typically local/two-body.

probability of occurence

Def. A random n-qubit Pauli error 𝐸 is called
local stochastic noise of strength 𝑝 ∈ [0,1] if

Pr[𝐹 ⊆ Supp(𝐸)] ≤ 𝑝|𝐹| for all 𝐹 ⊂ {1, … , 𝑛}Notation: 𝐸~𝒩(𝑝).

Such Pauli errors can be arbitrarily
correlated: no locality constraints

Local stochastic noise
Assumption
Errors are(randomly
chosen)Pauli errors.

Justification
Probabilistic Pauli noise is
no more detrimental than
general coherent noise.

argument based on linearity/operator bases:
Ekert, Macchiavello, Phys. Rev. Lett. 77, 2585 (1996)

evidence from numerical simulation for surface codes:
Bravyi, Englbrecht, K, Peard npj Quant. Inf., vol. 4, no. 55 (2018)
can be achieved by Pauli twirlingHigh weighterrors are
exponentiallysuppressed(unlikely).

Physical processes are
typically local/two-body.

probability of occurence

Def. A random n-qubit Pauli error 𝐸 is called
local stochastic noise of strength 𝑝 ∈ [0,1] if

Pr[𝐹 ⊆ Supp(𝐸)] ≤ 𝑝|𝐹| for all 𝐹 ⊆ {1, … , 𝑛}Notation: 𝐸~𝒩(𝑝).

SuchPauli errors can be arbitrarily
Gottesman, Quant.Info. Comp., vol. 14, no. 15–16, 2014
Fawzi, Grospellier
FOCSconstraints
2018
correlated:
no& Leverrier,localityError transformation rules for probabilistic Pauli noise
Such Pauli errors can be arbitrarily
correlated: no locality constraints

Error accumulation:=
Error propagation:=
Def. A random n-qubit Pauli error 𝐸 is called
local stochastic noise of strength 𝑝 ∈ [0,1] if

Lemma:• 𝐸~𝒩 𝑝 , 𝐸′~𝒩(𝑞)(possibly dependent)⟹
𝐸 ′ 𝐸~𝒩(2 max{ 𝑝, 𝑞})• 𝐸~𝒩 𝑝 and 𝐶 depth-1
Clifford circuit⟹
𝐶 † 𝐸𝐶~𝒩( 2𝑝)

Pr[𝐹 ⊆ Supp(𝐸)] ≤ 𝑝|𝐹| for all 𝐹 ⊆ {1, … , 𝑛}Notation: 𝐸~𝒩(𝑝).

Gottesman, Quant.Info. Comp., vol. 14, no. 15–16, 2014
Fawzi, Grospellier & Leverrier, FOCS 2018

Local stochastic noise in quantum circuits
Let 𝑈 = 𝑈𝐷 𝑈𝐷−1 ⋅⋅⋅ 𝑈1 be a quantum circuit with layers of 1- and 2-qubit gates 𝑈𝑗…

ideal circuit
𝑈2

𝑈1

𝑈𝐷

…

noisy implementation
𝐸𝑖𝑛

𝑈1

𝐸1

𝑈2

𝐸2

𝑈𝐷

𝐸𝑜𝑢𝑡

𝐸𝐷

Def. A noisy implementation of 𝑈 with error strength gives a sample 𝑧out ∈ {0,1}𝑛 from𝑛

𝑃 𝑧out ∣ 𝐸in , 𝐸1 , … , 𝐸𝐷 , 𝐸out = 𝑧out 𝐸out 𝐸𝐷 𝑈𝐷 ⋯ 𝐸1 𝑈1 𝐸in 0
where

𝐸𝑗 ~ 𝒩 𝑝(qubit/gate noise)

𝐸𝑖𝑛 ~ 𝒩 𝑝
𝐸𝑜𝑢𝑡 ~ 𝒩 𝑝

2(preparation noise)(measurement noise)Universal quantum computation: Fault-tolerance constructions
Can the (ideal) circuit 𝒬ideal be
simulated using noisy components?

Fault-tolerance
construction
Given: (adaptive) quantum circuit
𝒬ideal on 𝑛 qubits of depth 𝑇

Larger circuit 𝒬FT whose
noisy implementation
simulates 𝒬ideal

Fault-tolerance construction of Yamasaki and Koashi
Can the (ideal) circuit 𝒬ideal be
simulated using noisy components?

Theorem [1] There is a threshold error strength 𝑝0 > 0 such that for large 𝑛 and 𝜀 ∈ 0,1 :Let 𝒬ideal be a circuit withThen:𝑛 qubits
𝑇(𝑛) = 𝑂 poly 𝑛

There is a circuit 𝒬FT withdepth𝑛 ⋅ 𝑂(1) qubits
𝑇(𝑛) ⋅ exp 𝑂 log 2 (log(𝑛/𝜀))

depthsuch that a noisy implementation of 𝒬FT with local stochastic noise of strength 𝑝 ≤ 𝑝0 has an
output distribution whose 𝐿1 -distance to the output distribution of 𝒬ideal bounded by 𝜀.
[1] Yamasaki and Koashi, Nat. Phys. no. 20, Feb 2024

Quantum memories: protecting information against noise
How to protect against noise given by a CPTP map ?
𝒩: ℬℇ
encoding
map

𝒩
noise
channelEncoding map: A CPTP mapℰ: ℬℂ2 ⊗𝑘 → ℬ

ℂ2 ⊗𝑛 → ℬ

ℂ2 ⊗𝑛

ℂ2 ⊗𝑛

noise channel=ℛ
recoverymap

Recovery map: A CPTP mapℛ: ℬℂ2 ⊗𝑛 → ℬℂ2 ⊗𝑛ℇ
encoding
map

ideally wantℛ∘𝒩∘ℰ =ℰ

“perfect recovery”

Stabilizer codes
Encoding map: A CPTP mapℰ: ℬℂ2 ⊗𝑘 → ℬℂ2 ⊗𝑛ℇ
encodingmap

𝒮 stabilizer group, i.e., an abeliansubgroup of the 𝑛-qubit Pauligroup 𝒫𝑛 such that −𝐼 ∉ 𝒮.

The encoded state ℰ(𝜌)ℒ𝒮 = Ψ ∈ ℂ2 ⊗𝑛 ∣ 𝑆Ψ = Ψ for all 𝑆 ∈ 𝒮

has support on a certain
subspace ℒ ⊂ ℂ2 ⊗𝑛 ,code space of stabilizer code

the code space of a quantum
error-correcting code.

𝒮 = 𝑆1 , … , 𝑆𝑛−𝑘generated by 𝑛 − 𝑘linearly independent
generators 𝑆𝑗

𝑛−𝑘
𝑗=1

.

Recovery in a stabilizer codeℇ
encoding
map

𝒩
noise
channelSyndromemeasurement

Correction

𝐶(𝑠){Π 𝑠 }𝑠 PVM

syndrome 𝑠recovery map ℛ

𝒮 = 𝑆1 , … , 𝑆𝑛−𝑘generated by 𝑛 − 𝑘linearly independent
generators 𝑆𝑗

Recoveryprocedure ℛ

1. measure the eigenvalue (−1)𝑠𝑗 of 𝑆𝑗
generating a syndrome 𝑠 ∈ {0,1}𝑛−𝑘
1

𝑛−𝑘
𝑠𝑗
Let Π(𝑠) = Π𝑗=1
𝐼
+
(−1)
𝑆𝑗
2
be the corresponding projection.

2. Compute a Pauli correction
𝐶(𝑠) ∈ 𝒫𝑛 , i.e., evaluate afunction 𝐶 : {0,1}𝑛−𝑘 → 𝒫𝑛 .

Apply 𝐶(𝑠).

𝑛−𝑘
𝑗=1

.

3-qubit repetition code
Example: 3-qubit repetition code
Logical operators
bitflip noise(error E)ℒ𝒮 = span

000 , |111⟩}𝒔 = 𝒔𝟏 , 𝒔𝟐

𝑪(𝒔)(𝟎, 𝟎)

𝐼(𝟏, 𝟎)

𝑋1(𝟎, 𝟏)

𝑋3(𝟏, 𝟏)𝑋2

𝒮 = ⟨𝑍1 𝑍2 , 𝑍2 𝑍3 ⟩𝑋᪄ = 𝑋1 𝑋2 𝑋3 , 𝑍᪄ = 𝑍1

Syndrome measurement𝑒encoding(isometry)

𝛼 0 + 𝛽|1⟩

𝑋1 1
𝑋

𝑒2

𝑋

𝑒3

Correction
𝐶(𝑠)0𝛼 000 + 𝛽|111⟩
0

𝑠1
𝑠2

recovery map ℛ
If recovery fails, we must have (𝑒1 , 𝑒2 ) = (1,1) or (𝑒1 , 𝑒3 ) = (1,1) or (𝑒2 , 𝑒3 ) = (1,1)

3-qubit repetition code
Example: 3-qubit repetition code
Logical operators
bitflip noise(error E)ℒ𝒮 = span

000 , |111⟩}𝒔 = 𝒔𝟏 , 𝒔𝟐

𝑪(𝒔)(𝟎, 𝟎)

𝐼(𝟏, 𝟎)

𝑋1(𝟎, 𝟏)

𝑋3(𝟏, 𝟏)𝑋2

𝒮 = ⟨𝑍1 𝑍2 , 𝑍2 𝑍3 ⟩𝑋᪄ = 𝑋1 𝑋2 𝑋3 , 𝑍᪄ = 𝑍1

Syndrome measurement

𝑒

𝑋1 1

encoding(isometry)

𝛼 0 + 𝛽|1⟩

𝑋

𝑒2

𝑋

𝑒3

Correction
𝐶(𝑠)
𝑠1

0

𝛼 000 + 𝛽|111⟩𝑠2

0

recovery map ℛ
Pr[ recovery fails ] ≤Pr𝐸 1,2 ⊆ supp 𝐸≤ 3 𝑝2 =: 𝑓(𝑝)+ Pr𝐸 1,3 ⊆ supp 𝐸+ Pr𝐸 2,3 ⊆ supp 𝐸
if 𝐸 ∼ 𝑁(𝑝) is local stochastic

The surface code: A [𝑛, 1, Θ(𝑛1/2 )]-code with geometrically local generators• encodes 1 qubit into 𝑛 = 𝑑 2 + (𝑑 − 1)2 physical qubits

one qubit on each edge

𝑋
𝑍

𝑋

𝑍

𝑍

𝑑

𝑍

𝑋
𝑋

• Code space is ground space of gapped local
Hamiltonians with 4-qubit interactions• Code has distance 𝑑 : no operator with support of sizeO(1) can distinguish ground states

𝑋
𝑋

𝑋
𝑋

𝑋
𝑋𝑍

𝑍

𝑍
𝑑

𝑍

𝑍

Logical operators𝑋᪄= ෑ 𝑋𝑒𝑒∈𝑃𝑍᪄= ෑ 𝑍𝑒𝑒∈𝑃′

where 𝑃 (resp. 𝑃′ ) connect left/right (resp. top/bottom) boundaries.

Combinatorial upper bounds on failure probability
Pr[ recovery fails ] ≤ σ𝑚∈ℳ Pr𝐸 [𝐷𝑚 ⊆ supp(𝐸)]𝐷𝑚 𝑚∈ℳ is a certain family of subsets of qubits𝑓(𝑝): = σ𝑚∈ℳ 𝑝 𝐷𝑚

Lemma: (Combinatorics)for𝑝 ∈ 0,1𝑓(𝑝) ≤ poly(𝑑) ⋅ 𝑝/𝑝0 𝑑/2

for all 𝑝 ≤ 𝑝0 = 1/36 ≈ 0.028

Corollary: Can recover from local stochastic error 𝐸 of strength 𝒑 ≤ 𝒑𝟎 for sufficiently large 𝑑
Proof: Use the Definition of local stochastic errors!

Dennis, Kitaev, Preskill, J. Math. Phys. 43, 4452-4505 (2002).
http://theory.caltech.edu/~preskill/ph219/fault-tolerance-2011.pdf
Fowler Phys. Rev. Lett. 109, 180502 (2012)

This talk: How to use
noisy, local operations

noisy qubits/
operations

Fault-tolerance
construction
Fully connectedideal device

ideal qubits/
operations

noise-robust
localizer
Fully connectednoisy device

Low-connectivity
noisy device

Main consequence:
Overhead-efficient fault-tolerance constructions incorporating locality constraints.

Noise-robust localizationnoise-robust
localizer
Low-connectivity
noisy device

Fully connectednoisy device

Basic building blocks:
localizer

Fully connectedideal device• Bell (resource) states
Low-connectivity
ideal device• EntanglementSwapping

Single-shot (stabilizer) state preparation protocols
Prepare a (stabilizer) state 𝚽 ∈ ℂ𝟐⊗𝒓

as follows:

1. Apply a constant-depth Clifford circuit 𝑊 to 0𝑁 .
2. Apply single-qubit measurements to 𝑁 − 𝑟 qubits,
resulting in a measurement results 𝑠 ∈ {0,1}𝑁−𝑟 .
3. Apply a Pauli correction 𝐶(𝑠) ∈ 𝒫𝑟 to the remaining
qubits.
(𝐶: {0,1}𝑁−𝑟 → 𝒫𝑟 should be efficiently computable.)ancillaqubitsshallowquantum
circuit

Pauli
𝐶(𝑠)

𝑊

𝑠 classicalcomputation|Φ⟩Single-shot (stabilizer) state preparation protocols
Prepare a (stabilizer) state 𝚽 ∈ ℂ𝟐⊗𝒓

as follows:

1. Apply a constant-depth Clifford circuit 𝑊 to 0𝑁 .

0 ⊗𝑛

2. Apply single-qubit measurements to 𝑁 − 𝑟 qubits,
resulting in a measurement results 𝑠 ∈ {0,1}𝑁−𝑟 .

shallowquantum
circuit𝑊

3. Apply a Pauli correction 𝐶(𝑠) ∈ 𝒫𝑟 to the remaining
qubits.

Pauli
𝐶(𝑠)
𝐸
𝑠 classicalcomputation

𝐸eff 𝐸 Φ ∝ 𝐶(𝑠)(𝐼 ⊗ ⟨𝑠|)𝐸|0𝑁 ⟩0 ⊗𝑛shallowquantum
circuit

Pauli
𝐶(𝑠)

𝑊

𝑠 classicalcomputation

𝐸eff 𝐸

State preparation: Robustness
FAIL ≔ {𝐸 ∈ 𝒫𝑛 | 𝐸eff 𝐸 Φ ≠ Φ }Definition: Let 𝑓: 0,1 → [0,1]. The protocol is called[𝑛]𝒇-robust if there is a family 𝐷𝑚 𝑚∈ℳ ⊂ 2

0 ⊗𝑛such thatshallowquantum
circuit𝑊(a) For every 𝐸 ∈ FAIL:

Pauli
𝐶(𝑠)
𝐸
𝑠 classicalcomputation∃ 𝑚 ∈ ℳ such that 𝐷𝑚 ⊆ supp (𝐸)𝐸eff 𝐸 Φ ∝ 𝐶(𝑠)(𝐼 ⊗ ⟨𝑠|)𝐸|0𝑁 ⟩(b) σ𝑚∈ℳ 𝑝 𝐷𝑚 ≤ 𝑓 𝑝 for all 𝑝 ∈ 0,1 .

We are often only interested in the probability
Pr [protocol fails to prepare |Φ⟩] = Pr[E ∈FAIL]

0 ⊗𝑛shallowquantum
circuit

Pauli
𝐶(𝑠)

𝑊

𝑠 classicalcomputation

𝐸eff 𝐸

State preparation: Robustness and failure probability
FAIL ≔ {𝐸 ∈ 𝒫𝑛 | 𝐸eff 𝐸 Φ ≠ Φ }Definition: Let 𝑓: 0,1 → [0,1]. The protocol is called[𝑛]𝒇-robust if there is a family 𝐷𝑚 𝑚∈ℳ ⊂ 2

0 ⊗𝑛such thatshallowquantum
circuit

Pauli
𝐶(𝑠)
𝐸
𝑠 classicalcomputation

𝑊(a) For every 𝐸 ∈ FAIL:∃ 𝑚 ∈ ℳ such that 𝐷𝑚 ⊆ supp (𝐸)𝐸eff 𝐸 Φ ∝ 𝐶(𝑠)(𝐼 ⊗ ⟨𝑠|)𝐸|0𝑁 ⟩(b) σ𝑚∈ℳ 𝑝 𝐷𝑚 ≤ 𝑓 𝑝 for all 𝑝 ∈ 0,1 .

Lemma An 𝑓-robust protocol 𝜋 faulttolerantly prepares the state Φunder local stochastic noise 𝐸 ∼ 𝒩(𝑝):Pr 𝜋 fails ≤ 𝑓 𝑝 for any 𝑝 ∈ [0,1].

Proof. Consider local stochastic noise 𝐸 ∼ 𝒩(𝑝) with strength 𝑝 ≤ 𝑝0 .
Then
Pr[𝐸 ∈ FAIL]≤ ෍ Pr 𝐷𝑚 ⊆ supp(𝐸) by the union bound and (a)𝑚∈ℳ≤ ෍ 𝑝 𝐷𝑚 by the assumption 𝐸 ∼ 𝒩(𝑝)𝑚∈ℳ

≤ 𝑓(𝑝) by (b)Raussendorf, Bravyi, Harrington, PRA (2005)

Robustness of a 3D-local state preparation procedure
Theorem (Quantum bus architecture).

𝑄2

Δ
8

For any 𝑅 ≥ 2 , Δ ∈ ℕ with 𝑅 ≤ 𝑒 there is a circuit 𝜋 such that:(i) 𝜋 is local and constant-depth on the grid graph 𝑃Δ × 𝑃Δ × 𝑃𝑅 .
1(ii) 𝜋 prepares the state |𝛷⟩ = (|00⟩ + |11⟩).
2(iii) 𝝅 is 𝒇-robust for a function 𝒇: 𝟎, 𝟏 → 𝟎, 𝟏 that satisfies
𝒇 𝒑 =

𝒑
𝒑𝟎

|𝛷⟩

for any 𝒑 ≤ 𝒑𝟎 : = 𝟏/𝟓𝟎𝟎𝟒.

𝑞2
𝑞1

𝑅

Shin Ho Choe and RK, arXiv: 2209.09774

Δ

𝑄1
Δ

Robustness of a 3D-local state preparation procedure
Theorem (Quantum bus architecture).

𝑄2

Δ
8

For any 𝑅 ≥ 2 , Δ ∈ ℕ with 𝑅 ≤ 𝑒 there is a circuit 𝜋 such that:(i) 𝜋 is local and constant-depth on the grid graph 𝑃Δ × 𝑃Δ × 𝑃𝑅 .
1(ii) 𝜋 prepares the state |𝛷⟩ = (|00⟩ + |11⟩).
2(iii) 𝝅 is 𝒇-robust for a function 𝒇: 𝟎, 𝟏 → 𝟎, 𝟏 that satisfies
𝒇 𝒑 =

𝒑
𝒑𝟎

𝑅
|𝛷⟩

for any 𝒑 ≤ 𝒑𝟎 : = 𝟏/𝟓𝟎𝟎𝟒.

Creates a constant-fidelity Bell pair at a distance exponential in 𝑁𝑟𝑒𝑝𝑒𝑎𝑡𝑒𝑟
where the number of qubits per slice is 𝑁𝑟𝑒𝑝𝑒𝑎𝑡𝑒𝑟 = Δ2 .
(We know that the maximal distance for any protocol is 𝑂(𝑁𝑟𝑒𝑝𝑒𝑎𝑡𝑒𝑟 ).

Δ

𝑄1
Δ

State preparation up to local stochastic noise
Prepare a (stabilizer) state 𝚽 ∈ ℂ𝟐⊗𝒓

as follows:

1. Apply a constant-depth Clifford circuit 𝑊 to 0𝑁 .
2. Apply single-qubit measurements to 𝑁 − 𝑟 qubits,
resulting in a measurement results 𝑧 ∈ {0,1}𝑁−𝑟 .

shallowquantum
circuit𝑊

3. Apply a Pauli correction 𝐶(𝑧) ∈ 𝒫𝑟 to the remaining
qubits.

Definition: The protocol prepares |Φ⟩

Pauli
𝐶(𝑠)
𝐸
𝑠 classicalcomputation

𝐸eff 𝐸 Φ ∝ 𝐶(𝑠)(𝐼 ⊗ ⟨𝑠|)𝐸|0𝑁 ⟩up to local stochastic noise of strength 𝒒
under local stochastic noise of strength 𝒑if

𝑬 ∼ 𝓝(𝒑) implies that

𝑬eff (𝑬) ∼ 𝓝(𝒒).

shallowquantum
circuit

Pauli
𝐶(𝑠)

𝑊

𝑠 classicalcomputation

𝐸eff 𝐸

A parallel repetition theorem
Theorem (Parallel repetition)𝐶

Let 𝜋 be a 𝑓-robust protocol preparing |Φ⟩ ∈ ℂ2 ⊗𝑟 .
Then:

𝜋×𝜋

prepares𝑊|Φ⟩ ⊗ |Φ⟩1/𝑟

up to local stochastic noise of strength 𝑓(𝑝)under local stochastic noise of strength 𝒑

𝐸

.

𝐶
𝑊

A parallel repetition theorem
Theorem (Parallel repetition)𝐶

Let 𝜋 be a 𝑓-robust protocol preparing |Φ⟩ ∈ ℂ2 ⊗𝑟 .
Then:

𝜋×𝜋

prepares𝑊
𝐸𝑒𝑓𝑓|Φ⟩ ⊗ |Φ⟩up to local stochastic noise of strength 𝒇(𝒑)𝟏/𝒓 .

under local stochastic noise of strength 𝑝𝐶𝑊A parallel repetition theorem

𝐶
𝑊

Theorem (Parallel repetition)
Let 𝜋 be a 𝑓-robust protocol preparing |Φ⟩ ∈ ℂ2 ⊗𝑟 .
Then:

𝜋 ×𝑘

preparesΦ ⊗𝑘up to local stochastic noise of strength 𝑓(𝑝)1/𝑟 .

𝐶𝑊𝐸

under local stochastic noise of strength 𝑝
𝐶
𝑊

Effective output noise of strength
independent of the number of parallel repetitions.

A parallel repetition theorem
Theorem (Parallel repetition)
Let 𝜋 be a 𝑓-robust protocol preparing |Φ⟩ ∈ ℂ2 ⊗𝑟 .
Then:

𝜋 ×𝑘

preparesΦ ⊗𝑘up to local stochastic noise of strength 𝑓(𝑝)1/𝑟 .

under local stochastic noise of strength 𝑝

Effective output noise of strength
independent of the number of parallel repetitions.

𝐸Putting it all together: basic ideaΦPath 𝑃 used in pairing

4 buses applied in parallel
fault-tolerant bus &parallel repetition theorem

Result:Φ ⊗4 with local stochastic noise

3 entanglement swapping
measurements
circuit level analysisΦconstant-fidelity Bell pair

Putting it all together⋮

𝑘 = 𝐿2 /2

paths

𝑃1 , … . , 𝑃𝑘

4 𝑘 buses applied in parallelΦ⋮

3 𝑘 entanglement swapping

measurements

Result:fault-tolerant bus &parallel repetition theorem

parallel repetition theorem
for entanglement swappingΦ ⊗4𝑘 with local stochastic noise𝚽 ⊗𝐤 up to local stochastic noise

Main result: noise-robust localization
Theorem:
There is an adaptive circuit 𝒬 ′ withthe following properties:

1. 𝒬 ′ uses 𝒏 ⋅ 𝑶 𝒏𝟏/𝟐 𝒍𝒐𝒈𝟑 𝒏 qubits
and is local when these are arranged
on a 3D grid graph.

Given: adaptive quantum circuit 𝒬

2. 𝒬 ′ has quantum depth of order 𝑶(𝑻).

on 𝒏 qubitsof depth 𝑻
involving non-local operations

noise-robust
localizer

3. 𝒬 ′ simulates 𝒬 exactly
4. A noisy implementation of 𝒬 ′ withnoise of strength 𝑝 is equivalent to anoisy implementation of 𝒬
with noise of strength 𝐶𝑝𝑐

Application I of localizers:
Fault-tolerant computation

noisy qubits/
operations

Fault-tolerance
construction
Fully connectedideal device

use Yamasaki
and Koashi, Nat.
Phys. no. 20, Feb
2024

ideal qubits/
operations

noise-robust
localizer
Fully connectednoisy device

Low-connectivity
noisy device

Main consequence I:
Overhead-efficient fault-tolerance constructions incorporating locality constraints.

Referencegeometry/locality

physical qubit overhead
quantum depth overhead
Related work on fault-tolerant
computation[1-4]

1D, 2D & 3D

poly(𝑛)poly(𝑛)[5-8]

2D & 3D

poly(n)poly(𝑛)our work

quasi-2D-local

O 𝑛 log 3 𝑛

exp 𝑂( log 2 log 𝑛

our work

3𝐷-local

O 𝑛1/2 log 3 𝑛

exp 𝑂( log 2 log 𝑛Fawzi et al. & Gottesman

non-local

O(1)

O(𝑛)

Yamasaki et al.

non-local

O(1)exp 𝑂( log 2 log 𝑛[1] Aharonov and Ben-Or, SIAM J. Comp. 38, 1207-1282 (2008)[2] Gottesman, J. Mod. Opt 47, 333-345 (2000)[3] Svore, Terhal, DiVincenzo, Phys. Rev. A72, 002317 (2005)[4] Svore, DiVincenzo, Terhal, Quant. Inf. Comp. Vol. 7, No. 4, pp. 297-318 (2007)[5] Raussendorf, Harrington, Phys. Rev. Lett. 98, 190504 (2007)[6] Bombin, arXiv:1810.0957[7] Hormsan, Fowler, Devitt, Meter, NJP, 2012
[8] Litinski, Quantum 2019.
[9] Yamasaki and Koashi, Nat. Phys. no. 20, Feb 2024
[10] Fawzi, Grospellier & Leverrier, FOCS 2018& D. Gottesman, Quant. Inf. Comp. 2014

Application II of localizers:
quantum memories

noisy qubits/
operations

Fault-tolerant
memoryideal quantum
memoryuse single-shot
decoder for goodquantum LDPC
codes by Gu et al.

ideal qubits/
operations

noise-robust
localizer
Fully connectednoisy device

Low-connectivity
noisy device

Main consequence II:
Overhead-efficient fault-tolerant constructions incorporating locality constraints.

Another application: building quantum memories
construction

physical qubit overhead

quantum depth overhead

locality

toric code/surface codes [1]polynomial

polynomial

2D

hierarchical code [2] by
Pattison et al.

polylogarithmic

polynomial

2D

our work together with [3]polynomialconstant

3D (or quasi-2D)[1] E. Dennis, A. Kitaev, A. Landahl, J. Preskill, J. Math. Phys. 43, 4452-4505 (2002).
[2] Pattison, Krishna and Preskill, arXiv:2303.04798[3] Gu, Tang, Caha, Choe, He, Kubica, Commun. Math. Phys. 405, 85 (2024)

Construction

LDPC code
implemented
with qubit
routing
LPDC codewith faulttolerantrouting
LDPC code
concatenated +O(1)surface code
LDPC code
concatenated +O(log n)surface code

Circuit depth𝑇

𝑂(1)Total numberof qubits

𝑂 𝑛

Syndrome
extraction(Delfosse
et al.)
bound
appliesParameterssaturate
bound

Recovery(Baspin et al)
boundappliesParameter
saturate
bound

Faulttolerant

Reference

Yes

Yes

Yes

No

No

Our work(routing)

Yes

Yes

No

Yes

Our work

Yes

Yes

Yes

No

Pattison et
al.

3/2

𝑂(1)
Θ 𝑛3/2 log 3 𝑛
up to polylog
factors

No(controls
are not
parities)

Yes
Θ( 𝑛)

Θ(𝑛)

Pattison etal.

Θ( 𝑛log 𝑛)Θ 𝑛log 2 𝑛

No(not LPDC)

Yes

Yes

Yes

Yes

[1] N. Delfosse, M. E. Beverland, and M. A. Tremblay, Bounds on stabilizer measurement circuits and obstructions to local implementations of quantum LDPC codes, Sep. 2021. arXiv: 2109.14599.
[2] N. Baspin, O. Fawzi, and A. Shayeghi, A lower bound on the overhead of quantum error correction in low dimensions, Feb. 2023. arXiv: 2302.04317.

Local codes in ℝ𝐷
Bound𝑑 ∈ 𝑂(𝑛Reference
𝐷−1
𝐷

)

[1]

2
𝑘𝑑 𝐷−1 ∈ 𝑂(𝑛)

[2]

𝐷−2
𝑘 ∈ 𝑂(𝑛 𝐷 )[3]𝑑 code distance𝑘 number of encoded (logical) qubits
𝑛 number of physical qubits

𝐷=2

𝐷=3

No-go theorems (trade-off bounds)

Explicit constructions]1[ S. Bravyi and B. Terhal, "A no-go theorem for a two-dimensional self-correcting
quantum memory based on stabilizer codes," New Journal of Physics, vol. 11, no. 4,
p. 043 029, Apr. 2009. DOI: 10.1088/1367 − 2630/11/4/043029.
[2] S. Bravyi, D. Poulin, and B. Terhal, "Tradeoffs for reliable quantum information
storage in 2d systems," Phys. Rev. Lett., vol. 104, p. 050503,5 Feb. 2010. DOI:
10.1103/ PhysRevLett. 104.050503.
[3] J. Haah, "A degeneracy bound for homogeneous topological order," SciPost
Phys., vol. 10, p. 011, 2021. DOI: 10.21468/SciPostPhys.10.1.011.

[1] Elia Portnoy, Local Quantum Codes from Subdivided Manifolds,
arXiv:2303.06755[2] Dominic J. Williamson and Nouédyn Baspin, Layer codes, arXiv:2309.16503[3] Ting-Chun Lin, Adam Wills, Min-Hsiu Hsieh,
Geometrically Local Quantum and Classical Codes from Subdivision,
arXiv:2309.16104

The layer code associated with the Shor code
Shor’s code𝒮 = ⟨𝑍1 𝑍2 , 𝑍2 𝑍3 , 𝑍4 𝑍5 , 𝑍5 𝑍6 , 𝑍7 𝑍8 , 𝑍8 𝑍9 , 𝑋1 𝑋2 𝑋3 𝑋4 𝑋5 𝑋6 , 𝑋4 𝑋5 𝑋6 𝑋7 𝑋8 𝑋9 ⟩Figure from [1][1] Dominic J. Williamson and Nouédyn Baspin, Layer codes, arXiv:2309.16503

The layer code associated with the Shor code
Shor’s code𝒮 = ⟨𝑍1 𝑍2 , 𝑍2 𝑍3 , 𝑍4 𝑍5 , 𝑍5 𝑍6 , 𝑍7 𝑍8 , 𝑍8 𝑍9 , 𝑋1 𝑋2 𝑋3 𝑋4 𝑋5 𝑋6 , 𝑋4 𝑋5 𝑋6 𝑋7 𝑋8 𝑋9 ⟩Figure from [1][1] Dominic J. Williamson and Nouédyn Baspin, Layer codes, arXiv:2309.16503

The layer code associated with a good quantum LDPC codeBound𝑑 ∈ 𝑂(𝑛Reference
𝐷−1
𝐷

)

[1]

2
𝑘𝑑 𝐷−1 ∈ 𝑂(𝑛)

[2]

𝐷−2
𝑘 ∈ 𝑂(𝑛 𝐷 )

[3]

𝐿
𝐿
𝐿

𝑑 code distance𝑘 number of encoded (logical) qubits
𝑛 number of physical qubits

Applying the layer code construction to a good quantum CSS-code gives a code with parameters𝑛, 𝑘, 𝑑 = Θ 𝐿3 , Θ(𝐿), Θ 𝐿2
[1] Dominic J. Williamson and Nouédyn Baspin, Layer codes, arXiv:2309.16503[2] A. Leverrier, G. Zémor, Quantum Tanner codes, FOCS 2022

Conclusions• New, geometrically local fault-tolerance constructions with low depth-overhead• Systematic separation of locality considerations and fault-tolerance design(codes/decoders/gates)• Many open question:• Optimality?
• 2D-locality?

• Exciting recent new developments in our field!
Quantum LDPC codes, No low-energy trivial states conjecture, optimal local codes…..

Shin Ho Choe, RK, How to fault-tolerantly realize any quantum
circuit with local operations, arXiv:2402.13863

Shin Ho Choe, RK, Long-range data transmission in a fault-tolerant
quantum bus architecture, arXiv:2209.09774