1 of 27

Quantum Error Correction

2 of 27

Last time

How to do deal with noise/errors in a quantum computation? A priori it seems very different from errors in classical computation (infinitely many possible errors on a single qubit, no-cloning, measurement collapse,…)

Can reduce problem of error-correction for a single-qubit to a discrete set of errors

Bitflip error:

Phaseflip error:

Bitflip & Phaseflip error:

3 of 27

Bitflip code

Enc

Logical state

Encoded state

Syndrome

qubits

Error

Diagnosis

(Possibly)

Noisy state

Error

Correction

4 of 27

Phaseflip code

Enc

Logical state

Encoded state

Syndrome

qubits

Error

Diagnosis

(Possibly)

Noisy state

Error

Correction

Key idea: phaseflip is just bitflip in diagonal basis!

5 of 27

Shor’s 9 qubit code

6 of 27

Shor’s 9 qubit code

Encoding:

Phaseflip Enc

Bitflip Enc

7 of 27

Shor’s 9 qubit code

Correction and decoding procedure:

Bitflip Correction

Phaseflip

Correction

Bitflip Decoding

Phaseflip

Decoding

= syndrome ancillas

8 of 27

Shor code can detect and fix:

Any single qubit X error

Any single qubit Z error

Any single qubit XZ error

9 of 27

Why errors can be discretized

Every unitary can be written as a linear combination of Pauli matrices:

10 of 27

Why errors can be discretized

Every unitary can be written as a linear combination of Pauli matrices:

11 of 27

Why errors can be discretized

Can handle more than just unitary errors:

12 of 27

Why errors can be discretized

13 of 27

14 of 27

Other quantum error correcting codes

15 of 27

Other quantum error correcting codes

16 of 27

The Toric Code

17 of 27

Toric code

18 of 27

Fault tolerance

Our analysis of Shor’s code assumes that encoding/correction/decoding are all done perfectly.

But in general all of these operations will experience errors. How do we cope with errors then?

Also, we don’t just want to store information – we want to compute with it! If we have encoded data, how to perform computations on them without decoding?

19 of 27

Fault tolerance

Main idea: only decode information only when absolutely necessary. Perform computations on top of encoded data.

Use quantum error correcting codes that allow for computations to be performed on encoded states, without requiring intermediate decoding.

Encoded operations should propagate errors in a controlled fashion.

20 of 27

Error propagation

Single qubit gates do not spread errors

Two-qubit gates can spread errors

21 of 27

Performing encoded gates

22 of 27

Performing encoded gates

.

Steane�codeword

Note: doesn’t work exactly like this for Shor code

Steane code supports transversal gates for any Clifford gate: X, Y, Z, P, H, CNOT.

23 of 27

Performing encoded gates

Steane�codewords

24 of 27

Eastin-Knill Theorem

25 of 27

Fault tolerance

In addition to performing encoded gates, periodically have to check for errors and correct them “mid-flight”.

26 of 27

Fault-Tolerance Theorem (a.k.a. the Threshold Theorem)

27 of 27

Today, and the future

We do not have fault tolerant systems yet. People are experimenting with quantum error correction schemes on small scale quantum computers, and seeing promising results.

Overhead due to fault-tolerance is enormous (1,000-10,000 encoded qubits for 1 logical qubit)

Three main directions:

Building better qubits/gates

Scaling up

Better error-correction/fault-tolerance schemes