The Present and Future of Quantum Error Correction

Dr. Nikolas Breuckmann, UCLQ Fellow

​

UCLQ Annual Industry Event 2019

Background

Quantum computers not the first computing architectures with exponentially increased computing power:

Analog Computers

(more precisely: real random access machines)

Why do we pursue building Quantum Computers?

Exponential speed-ups over classical computers!

Digital Computer:

bits

010101000101010101

Analog Computer: continuous numbers

0.5772156649...

Background

PSPACE

Solvable by analog computer

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

BQP

Solvable by quantum computer

​

​

​

​

​

​

​

​

​

P

Solvable by classical computer

NP

“Problems of interest”

​

​

​

​

​

​

​

​

​

​

​

​

Schönhage (1979), "On the power of random access machines", Lecture Notes in Computer Science, 71, Springer

Background

Why are we not building analog computers?

Errors can not be corrected

Trying to scale up: output is dominated by noise

​

They are fictional devices.

Background

Quantum Computers

• Operate on continuous states: Qubits
• N qubits correspond to 2^N+1 real variables
• Scepticism after Shor’s factoring algorithm appeared in ‘94 (rightfully so!)

Why do we believe building a quantum computer is feasible?

• Quantum mechanics is a mix of continuous & discrete
• Measurements discretise errors
• Possible to correct errors in quantum computer [Shor ‘95]:

quantum error correcting codes

​

Background

Resource overhead:

for a computation of length T, we need

polylog (T) extra qubits

Assumptions:

• Initialize qubits mid-computation
• Gates can be done in parallel

Threshold Theorem [Aharonov - Ben-Or ‘96]:

There exists a threshold p_t such that

if the error rate per gate and time step is p < p_t

arbitrarily long quantum computations are possible.

Can perform quantum computation with faulty hardware:

Summary:

​

1. Error correction is a prerequisite to obtain asymptotic speed-ups.
2. Physical error rate has to be below threshold

State-of-the-art: Bridging the gap

Past 20 years: theory and experiment coming closer together

THEORY

• Increase threshold
• Better performing schemes

EXPERIMENT

• Number of qubits
• Decoherence time
• Quality of gates

GAP

State-of-the-art: Theory

• Hardware has to perform below a threshold error rate for quantum error correction to work
• Original FT-Theorem threshold p_t = 10^-5

​

​

Topological codes [Dennis et. al. ‘01]:

• High threshold: p_t = 10^-3 - 10^-2 (match numbers in leaked Google paper)
• Planar connectivity
• Simplified logic

Dominant paradigm

State-of-the-art: Theory

Overhead in resources (physical qubits):

1. Redundancy due to encoding
2. Manipulation of encoded states more costly

Current estimates (using topological codes) [Gidney ‘19]:

• Breaking 2048-bit RSA key (currently used)
• Gate error rate of 1%
• Planar layout

20 million physical qubits running for ~9h

(165x improvement over [Fowler ‘12])

State-of-the-art: Experiment

• Different hardware: different challenges for error correction
• Common challenges:

Qubit & gate quality

​

Error rate crucial for error correction to work

Classical control

​

• Low-latency (up to ns)
• Adaptive
• run classical algorithm

Wiring/Connectivity

​

• Address many qubits
• Connect fridges / modules

State-of-the-art: Experiment

Quantum error correction has not yet been experimentally demonstrated

​

Proto - Quantum Error Correction:

• Preparing topological code state on ion qubits [Nigg et. al. ‘14]
• Perform classical error correction [Kelly et. al. ‘14]
• Error detection [Córcoles et al. ‘15, Linke et al. ‘17]
• Improved sampling by error detection [Vuillot ‘17]

Summary:

​

• Regimes of theory and experiment beginning to overlap
• Quantum error correction could be demonstrated soon

Outlook

Issues with predictions about technological advances.

​

​

​

Wrong despite sound understanding of the science at the time:

​

“There is not the slightest indication that nuclear energy will ever be obtainable.”

Albert Einstein, 1932

​

​

By extrapolating current trends:

​

“Nuclear powered vacuum cleaners will probably be a reality within 10 years.”

Alex Lewyt (president of Lewyt vacuum company), 1955

Outlook: Theory

As of now:

• Hardware agnostic
• Toy models of quantum errors
• Results mostly about asymptotic scaling

​

Very soon (now - 5 years):

• Hardware specific
• Optimizing constants
• Characterize hardware to obtain realistic error models
• Vertical integration with error correction and compilation

Outlook: Experiment Mile-Stones

Proof-of-concept

Error correction improves life-time of memory

​

Google & IBM report error rates below threshold

Scaling inside fridge

Demonstrate error suppression by increasing code size

Fault-Tolerance

​

Error correction improves quantum algorithm

Connecting fridges

​

Easy for some architectures, harder for others

Google’s leaked “quantum supremacy paper”:

​

“To [...] eventually cover the computational volume needed to run well-known quantum algorithms [...] the engineering of quantum error correction will have to become a focus of attention.”