1 of 28

Suhas Vittal

Poulami Das

Moinuddin Qureshi

Accurate Quantum Error-Decoding via Practical Minimum-Weight Perfect-Matching

Astrea

International Symposium on Computer Architecture (ISCA) 2023

2 of 28

Quantum Applications Need Low Error Rates

Hardware errors create a gap between applications and devices.

2

2023

2026

203X

~400 qubits

p = 0.5%

~4000 qubits

p = 0.1%

~100K qubits

p = 0.01%

Goal

Applications-at-scale

p < 10^-15

Significant gap in error rates!

3 of 28

Quantum Error Correction

QEC prevents errors by repeated performing syndrome extraction.

3

Logical

Qubit

X

Z

Syndrome Extraction

Decoder

X Syndrome: 0000

Z Syndrome: 1010

Correction

1

0

To deal with the limited fidelity of physical devices, we must use quantum error correction (or QEC) to protect quantum information. In this talk, we focus on the surface code, which encodes
logical qubits using a combination of
data qubits and
parity qubits. Half of these parity qubits are
Z stabilizers, which correct bit flip or X errors, and other half are
X stabilizers which protect against phase flip or Z errors.
To identify errors on the logical qubit, the quantum computer must
perform syndrome extraction on the logical qubit to obtain
failed parity checks.
The failed parity checks are compiled into bitstrings known as syndromes, which
are sent to classical logic known as a decoder which computes
a correction to undo any errors.
By performing syndrome extraction repeatedly, errors are removed from the logical qubit periodically, thus protecting quantum information.

4 of 28

Reducing the Logical Error Rate

We need accurate decoders to get the best performance!

4

17

Code Distance (d)

49

97

161

LER

3

5

7

9

Accurate Decoding

Inaccurate Decoding

5 of 28

Real-Time Decoding

We must decode syndromes in real-time to suppress errors!

5

Distance 5 Surface Code

Google, 2023

Distance 3 Surface Code

Wallraff Group, 2022

Offline Decoding

Real-Time Decoder

~1μs

6 of 28

The Last 21 Years of Real-Time Decoding

We propose Astrea to achieve this goal.

6

Latency

Accuracy

MWPM

2002

UF

2017

NISQ+

ISCA

2020

HPCA

2022

AFS

HPCA 2022

Clique

QULATIS

Ideal

ASPLOS

2023

100x to 100,000x worse

Real-Time decoding has been an open problem for over twenty years, with multiple communities working to solve it.

In 2002, we learned that MWPM decoding was near-optimal for the surface code, but existing implementations were not fast enough for real-time decoding. After that, various algorithms, such as
The Union-Find decoder were proposed, but no real-time decoder had been realized yet!
In 2020, NISQ+ was the first real-time decoder, but while its latency was very low, its performance was very poor and it relied the emerging superconducting devices. NISQ+ was followed by
QULATIS, another superconducting decoder, in 2022, whose performance was still poor. In the same year,
the AFS decoder, an implementation of UF in real-time was demonstrated. However, its performance was limited by the inherent inaccuracy of the UF algorithm.
Most recently, the Clique decoder was proposed in 2023, but its accuracy still pales in comparison to MWPM.
While these decoders improve on MWPM’s high latency, they sacrifice accuracy to do so,
to the extent that they are many orders of magnitude less accurate than MWPM.
Ideally, we want the performance of MWPM in real-time, and we propose Astrea to achieve this goal.

7 of 28

Astrea: Outline

Astrea: Insights, Design, and Results

What is Real-Time Decoding?

Astrea-G: Insights, Design, and Results

8 of 28

Accurate Quantum Error Decoding

Only handling one or two errors is rather underwhelming. Can we do better?

8

High Latency,

Low Overhead

Low Latency,

High Overhead

LILLIPUT can only handle one/two errors

(LILLIPUT)

9 of 28

Minimum-Weight Perfect Matching Decoding

How can we identify the MWPM for a syndrome in real-time?

9

a

b

d

c

Pair bits and minimize ΣW

a

b

d

c

MWPM

Nonzero Syndrome Bits

W = -log(P_error)

96% of syndromes not decodable

Hard to implement in real-time

10 of 28

Let’s Try an Exhaustive Search!

Insight 1: Low HW syndromes are easy to decode accurately.

The number of perfect matchings scales O(e^HW).

10

Look at small HW.

a

b

Only one option

c

d

e

f

Three options

i

j

k

x

y

z

= 15 options

5

* 3

* 1

Easy for exhaustive search

What if we were to try an exhaustive search for the MWPM? The number of perfect matchings scales exponentially with the number of ones in the syndrome, or the Hamming weight. So we can try this for small Hamming weights.

First, let’s look at a Hamming weight 2 syndrome with nonzero bits a and b. For this case, we only have
one option for the MWPM as we can only pair a with b.
For a syndrome with Hamming weight 4, we have three options.
Our first option is pairing c with d and e with f.
Our second option is pairing c with e and d with f. Finally,
Our last option is pairing c with f and d with e.
For a syndrome with Hamming weight 6, we have
5 choices for the first pair
3 choices for the second pair
And only 1 choices for the last pair, leading to 15 possible perfect matchings. In fact, 15 is quite a manageable number and
we can easily identify the MWPM using an exhaustive search.
Thus, our first insight is that we can decode these low Hamming weight syndromes easily and accurately with an exhaustive search.

11 of 28

What do we need to decode?

Insight 2: It suffices to only decode HW ≤ 10 up to d = 7.

11

Hamming weight (HW)*	d = 3	d = 5	d = 7
0 to 2	0.99	0.99	0.99
3 to 6	4e-5	3e-5	0.01
7 to 10	0	2e-7	2e-6
>10	0	0	4e-9
Logical error rate (LER)	8.1e-6	1.3e-7	6e-9

*at p = 10^-4

P(HW > 10) < LER

12 of 28

Decoding HW 6 and Below with Astrea

Astrea can quickly decode syndromes with HW ≤ 6 in 32ns.

12

d

a

b

c

y

x

HW ≤6 = ≤32ns

MWPM

13 of 28

Decoding HW 8 with Astrea

Astrea pre-matches a pair of bits to decode HW 8.

13

d

a

b

c

x

y

HW ≤6 = ≤32ns

z

w

PM1

PM2

PM3

PM4

PM5

PM6

PM7

MWPM

min

HW 8 = 60ns

HW 8 Decoder

14 of 28

Decoding HW 8 with Astrea

Astrea pre-matches a pair of bits to decode HW 8.

14

HW ≤6 = ≤32ns

HW 8 = 60ns

HW 8 Decoder

15 of 28

Decoding HW 10 with Astrea

Astrea accurately decodes d = 7 in real-time with only 10% of the FPGA.

15

HW ≤6 = ≤32ns

HW 8 = 60ns

HW 8 Decoder

e

a

b

c

d

x

y

z

u

v

HW 10 = 456ns

PM1

PM9

........

MWPM

16 of 28

Astrea: Outline

Astrea-G: Insights, Design, and Results

What is Real-Time Decoding?

Astrea: Insights, Design, and Results

17 of 28

Coping with Larger Search Spaces

Insight 1: Filter out large weights to reduce search space.

#17

a

Hamming weight = 16

~2M possible matchings!

P_error = 10^-weight

Filter!

< LER

~2000 matchings

18 of 28

Finding the MWPM after Filtering

Insight 2: Prioritize lowest weights first to quickly find MWPM.

18

Bits left:

16

14

12

10

8

6

Pre-matching

+

HW 6 MWPM

0

PM

MWPM

19 of 28

Astrea-G: Design

Astrea-G is the first decoder to accurately decode d = 9 in real-time!

19

Filter out if w > W_TH

15

8

4

2	15	4	6
15	8	14	8
4	14	13	15
6	8	15	12

Greedy

Pre-match

+

Global Weight Table

MWPM Register

HW ≤ 6?

t = 1μs

STOP!

Minimum

40% FPGA Utilization

The high-level design of Astrea-G is as follows:

First, Astrea-G retrieves weights for each pair of syndrome bits from the Global Weight Table, and
Filters out these weights as they are read. Using the retrieved edge weights, Astrea-G
Prematches bits with the lowest edge weights multiple times until there are only 6 unmatched bits.
Then, Astrea-G calls the HW6Decoder to match the last 6 bits and
combines the output with the prematched bits to get the final matching. Finally, t
the MWPM register Is updated if the new matching has lower weight than the existing matching.
After 1us have passed, Astrea-G stops decoding and returns the result contained in the MWPM register.
Astrea-G does require more resources than Astrea, but we observe that its overheads are still reasonable. Nevertheless, by
Filtering out high weights and Prioritizing low weights, Astrea-G quickly converges on the MWPM.

20 of 28

Conclusion

1. Quantum error correction is necessary for applications at scale.

20

2. Quantum fault-tolerance requires real-time decoding

Astrea/Astrea-G are the first real-time decoders with near-ideal accuracy up-to d = 9.

21 of 28

Astrea Redefines the Trend!

21

Latency

Accuracy

MWPM

2002

UF

2017

NISQ+

ISCA

2020

HPCA

2022

AFS

HPCA 2022

Clique

QULATIS

Ideal

ASPLOS

2023

Astrea

ISCA

2023

22 of 28

BACKUP SLIDES BEGIN HERE

22

23 of 28

Astrea: Results

Astrea enables near-ideal real-time decoding up to d = 7 at low-cost.

23

Resource	Utilization
LUT	5.6%
FF	0.9%
BRAM	9.6%

24 of 28

Astrea-G: Results for d = 7 and d = 9

Astrea-G has comparable accuracy to MWPM in real-time.

24

Equal accuracy to MWPM for d = 7

Within 2.5x of MWPM for d = 9

25 of 28

Astrea-G Beyond d = 9

25

Code Distance (d)	MWPM LER	Astrea-G LER
7	4.6e-10	4.6e-10
9	1.2e-11	1.2e-11
11	1.7e-14	2.9e-13

26 of 28

Impact of W_THon Performance

Higher W_TH yields better accuracy at the cost of higher latency.

26

Default

-log(LER)

Lower Latency

Lower Error

27 of 28

Astrea-G under Tighter Constraints

Astrea-G can operate below the standard 1μs constraint.

27

Time to Decode (μs)	Relative Logical Error Rate
1	1.0x
0.8	1.0x
0.6	1.08x
0.5	1.33x

Extra time for:

28 of 28

Recent Software MWPM Implementations

There have been recent papers demonstrating fast versions of MWPM. These papers collectively have the following limitations:

Latency is measured per round.

While syndromes are extracted at a rate of 1μs per round, decoders must decode all rounds within 1μs.

Astrea/Astrea-G are both able to decode all rounds within 1μs.

The decoders have a mean latency of 1μs.

The efficacy of mean 1μs latency is unclear as failing to decode means that the QC must be stalled until the decoder completes.
This results in more rounds that must be decoded (called the backlog) that the decoder must complete before progressing.

Astrea/Astrea-G have worst-case latencies of 1μs.

28