Quantum Error Correction | NotionNext BLOG

Introduction physical systems for qubits:Pros & Cons From classical to quantum error correction a simple example:[n, k, d] notation of classical error correction codes from bits to qubits Quantum code distance Stabilizer codes [[n,k,d]] notation for quantum error correction codes Properties of the code stabilizers The logical operators of stabilizer codes A general encoding circuit for stabilizer codes Quantum error correction with stabilizer codes Example: The Shor [[9,1,3]] code The surface code The surface code four-cycle The [[5, 1, 2]] surface code Scaling the surface code Practical considerations for quantum error correction Efficient decoding algorithms Code thresholds Fault tolerance Encoded computation

Introduction

Quantum error correction protocols will play a central role in the realisation of quantum computing; the choice of error correction code will influence the full quantum computing stack, from the layout of qubits at the physical level to gate compilation strategies at the software level.

physical systems for qubits:

photons

trapped ions

superconducting circuits

spin in semiconductors

Pros & Cons

Advantages:

Parallelism: One of the main advantages of quantum computing is parallelism. Due to the property of quantum superposition, a quantum computer can process a large number of possibilities at once. This makes quantum computers potentially much more powerful than classical computers for certain tasks.

Quantum Algorithms: There are specific algorithms, such as Shor's algorithm for factoring large numbers and Grover's algorithm for searching unsorted databases, that can be executed much more efficiently on a quantum computer than on any known classical computer.

Quantum Simulation: Quantum computers can simulate quantum systems efficiently, which is a task that is believed to be intractable for classical computers. This could be particularly useful for research in quantum physics, chemistry, and materials science.

Challenges:

Error Correction: Quantum systems are very susceptible to errors due to decoherence and other quantum noise. Developing effective quantum error correction codes and fault-tolerant quantum computers is a major challenge.

Scalability: Building a large-scale quantum computer is a significant technological challenge due to the stringent requirements for maintaining quantum coherence and high-fidelity quantum operations.

Programming and Control: Quantum programming and controlling a quantum computer are fundamentally different from their classical counterparts and require new concepts and tools.

Quantum Supremacy: Demonstrating a clear quantum advantage for a practical problem, often referred to as "quantum supremacy" or "quantum advantage", is still an open challenge.

shortcoming:

It is difficult to sufficiently isolate the qubits from the effects of external noise, meaning errors during quantum computation are inevitable.

vs bits

on/off states of transistor switches which are differentiated by billions of electrons.

high error margins

limitation

no cloning theorem

Peter Shor 1995

proposing the first quantum error correction scheme.

redundantly encoded by entangling it across an expanded system of qubits

Shor PW. Scheme for reducing decoherence in quantum computer memory. Phys Rev A. 1995;52:R2493.

From classical to quantum error correction

The basic principle behind error correction is that the number of bits used to encode a given amount of information is increased.The exact way in which this redundant encoding is achieved is specified by a set of instructions known as an error correction code.

a simple example:

three-bit repetition code

formally:

a mapping from an original binary alphabet to a code alphabet

where the encoded bit-strings ‘000’ and ‘111’ are referred to as the logical codewords of the code .

So, if we wish to communicate a single-bit message ‘0’ to a recipient in another location, we would send the ‘000’ codeword.

When a single bit-flip error occurs during transmission, the bit-string the recipient receives is ‘010’. In this scenario, the recipient can infer that the intended codeword is ‘000’ via a majority vote.

what if 2 bit-flip errors occur?

The majority vote will lead to the incorrect codeword。

what if 3 bit-flip errors occur?

Independent identically distributed(i.i.d)

The probability of each bit experiencing a bit flip error is . While the probability of each bit not experiencing an error is .

Error Type	1 bit-flip	2 bit-flip	3 bit-flip
Probability

💡

The distance of a code is defined as the minimum number of errors that will change one codeword to another in this way.

The distance of code is denoted as ，we can relate to the number of errors the code can correct as follows,

where is the number of errors the code can correct. For the three-bit code, and .

[n, k, d] notation of classical error correction codes

In general, error correction codes are described in terms of the notation,

n is the total number of bits per codeword,

k is the number of encoded bits (the length of the original bit-string) ,

d is the code distance.

Under this notation, the 3-bit repetition code is labelled .

from bits to qubits

where and are complex numbers that satisfy the condition .

A new complex example gives us more insight as follows,

classical:

0 or 1	No.0 bit
0 or 1	No.1 bit

quantum:

n classical computing, the computational space has only 4 values. Each value has 2 dimension

However, in quantum computing, the computational space has infinite values. Each value has 4 dimension.The computational space scales as where is the total number of qubits.

what if qutrit?

Qutrits have higher expressive power.The computational space scales as where is the total number of qutrits.

Quantum code distance

As is the case for classical codes, the distance of a quantum code is defined as the minimum size error that will go undetected. Alternatively, this minimum size error can be viewed as a logical Pauli operator that transforms one codeword state to another.

three-qubit code

If it were the case that qubits were only susceptible to X-errors, then the three-qubit code would have distance d = 3.

Logical Pauli- operator is given by , so that

where and are the logical codewords for the three-qubit code.

However, as qubits are also susceptible to phase-flip errors.

For one qubit, . For three-qubit code, the basis states choose

A weight-one logical Pauli- operator will transform , meaning the code is unable to detect the presence of single-qubit -errors. As a result, the three-qubit code has a quantum distance .

Stabilizer codes

[[n,k,d]] notation for quantum error correction codes

stabilizer codes, where is the total number of qubits, is the number of logical qubits and is the code distance.

Note the use of double brackets to differentiate quantum codes from classical codes which are labelled with single brackets.

💡

How the procedure to can be generalised to create [[n, k, d]] stabilizer codes?

A register of k data qubits, , is entangled with redundancy qubits via an encoding operation to create a logical qubit . At this stage, the data previously stored solely in is distributed across the expanded Hilbert space. Errors can then be detected by performing stabilizer measurements 。

Figure 4. Circuit illustrating the structure of an [[n,k,d]] stabilizer code.

for each stabilizer ,

From the above, we see that

if the stabilizer commutes with an error the measurement of ancilla qubit returns ‘0’.

If the stabilizer anti-commutes with an error , the measurement returns ‘1’.

For a well designed code, the syndrome allows us to deduce the best recovery operation to restore the logical state to the codespace.

Properties of the code stabilizers

The stabilizers of an code must satisfy:

Pauli-group elements, . is the Pauli Group over -qubits.

Pauli group

The Pauli group on a single-qubit, , is defined as the set of Pauli operators.

The Pauli Group over -qubits, , is the set of the tensor product of the matrices in .

Stabilize all logical states of the code. , each acts on

All the stabilizers of a code must commute with one another, so that , . The stabilizers can be measured simultaneously (or in a way independent of their ordering)

The stabilizers of an code, form an Abelian subgroup of the Pauli Group.

The stabilizer requirements listed above are incorporated into the definition of S as follows,

💡

Product of any stabilizers and , , will also be a stabilizer as

we should ensure the set of stabilizers, that are actually measured in the syndrome extraction process, form a minimal set of the stabilizer group

In a minimal set, it is not possible to obtain one stabilizer as a product of any of the other elements .

For the three-qubit code,

the set of stabilizers , is not a minimal set. ❎

a possible minimal set is . ✅

The logical operators of stabilizer codes

An stabilizer code has logical Pauli operators that allow for logical states to be modified without having to decode then re-encode.

For each logical qubit , there is a logical Pauli- operator and a logical Pauli- operator .

They satisfy

They commute with all the code stabilizers in .

They anti-commute with one other, so that .

why they need to commute with all the code stabilizers in ?

, the logical operator (which is ) satisfies , is also a logical state.

Any product of a logical operator and stabilizer will also be a logical operator. This is clear from the fact that the stabilizer maps the logical state onto its eigenspace. Any product therefore has the following action on the logical state .

A general encoding circuit for stabilizer codes

The codeword of any stabilizer can be obtained via a projection onto the (+1) eigenspace of all of its stabilizers,

where is the minimal set of the code stabilizers and the term is a factor that ensures normalisation.

For example, the codeword of the four-qubit code is given by

The remaining codewords of the code can be obtained by applying logical operators to the codeword.

Quantum error correction with stabilizer codes

💡

is the number of errors the code can correct

we need , so for correction codes.

Figure 6. The general procedure for active recovery in a quantum error correction code

Figure 6 shows the general error correction procedure for a single cycle of an stabilizer code.

The encoded logical state

an error process described by the circuit-element .

the code stabilizers are measured (using the syndrome extraction method illustrated in figure 4 ),

and the results copied to a register of ancilla qubits .

The ancilla qubits are then read out to give an -bit syndrome .

decoding, processing the syndrome to determine the best unitary operation .

the recovery output is

✅

this requires . →

❎

If , is a logical operator of the code. → , the output state is another code, the encoded information is changed.

Example: The Shor [[9,1,3]] code

💡

The first quantum error correction scheme to be proposed

first， 3-qubit code for phase-flip

second, for every qubit in first step, contruct 3-qubit code for bit-flip

where , are logical states of the bit-flip code.

the codespace of the Shor code

The stabilizer of the above code are given by

The first 6 stabilizers can detect single error;

The final 2 stabilizers can detect single error.

-errors that occur in the same block of the code have the same syndrome.However,we use one recovery operator to recovery the single-qubit error on 3 different qubits in the same block. For the errors, , we can use the recovery operator to recovery the original ,

The surface code

Surface codes belong to a broader family of so-called topological codes. The general design principle behind topological codes is that the code is built up by ‘patching’ together repeated elements.

In terms of actual implementation, the specific advantage of surface code for current hardware platforms is that it requires only nearest-neighbour interactions.

The surface code four-cycle

Qubits

stands for ancilla qubit;

stands for data qubit.

Gates

The red edges represent controlled- gates, each controlled on an ancilla qubit and acting on a data qubit .

Likewise, the blue edges represent controlled- operations, each controlled by an an ancilla qubit and acting on a data qubit.

Stabilizers

Ancilla qubit connects to data qubits and via red edges, and therefore measures the stabilizer .

Likewise, ancilla qubit measures the stabilizer .

The [[5, 1, 2]] surface code

The five-qubit surface code is formed by tiling together four four-cycles in a square lattice.

Stabilizers

From Figure 8, we can see that there are 5 code qubits, 4 stabilizers ⇒ encoding 1 logical qubit.

error detection

error anti-commutes with the stabilizer, triggers a ‘1’ syndrome. This is depicted by the red filling in the ancilla qubit .

-error anti-commutes with the stabilizer and triggers a ‘1’ syndrome measurement in ancilla qubit .

logical operators

According to the section ‘The logical operators of stabilizer codes’, the Pauli-X and Pauli-Z logical operators for each encoded qubit are pairs of operators that commute with all the code stabilizers but anti-commute with one another.

A suitable choice for the logical operators of the [[5,1,2]] surface code would therefore be

the minimum weight of the logical operators is 2, meaning the code is a detection code with .

Scaling the surface code

The distance of a surface code can be increased simply by scaling the size of lattice. In general, a surface code with distance will encode 1 logical qubit and have code parameters given by

The boundary qubits is , the sum number of all qubits is While ⇒

important example:

The circuit of (b)(c) can be obtained according to Figure 4。

Sometimes the measure operation (label 7 in (b)) can also be represented as follows，

the quantum state will collapse into a eigenstate of Z operator, or . So we can detect the state and .

And if we add a Hadamard gate before we excute the measure operation (label 7 in (b)), we can integrate the two operations into a new measure operation as follows,

we can detect the state and , which are eigenstates of X operator.

This array has been drawn with two types of boundaries, terminating with measure-X qubits on the right and left, which we call X boundaries, and terminating with measure-Z qubits on the top and bottom, which we call Z boundaries. The X boundaries are called smooth boundaries in the surface code literature, while Z boundaries are called rough boundaries

Practical considerations for quantum error correction

Efficient decoding algorithms

Given a code syndrome , the role of the decoder is to find the best recovery operation to restore the encoded quantum information to the codespace.

Measuring the stabilizers of an code will produce an -bit syndrome where . We can go back and take another look at Figure 4 .

method 1 lookup tables

We can use bit syndrome, so we have possible m-bit strings, from to .

If the code is , ⇒ . Too big!

method 2 approximate inference techniques

determine the most likely error to have occurred given a certain syndrome

For surface codes, a technique known as minimum weight perfect matching (MWPM) can be used for decoding, which works by identifying error chains between positive syndrome measurements.

decoding failure: 。 This recovery operator transforms the encoded state into another encoded state which is also in code space.

The logical error rate can be determined by simulating stabilizer code cycles with errors sampled from a noise model. The specifics of the noise model are motivated by the physical device on which the code is to be run.

Code thresholds

The threshold theorem for stabilizer codes states that

increasing the distance of a code will result in a corresponding reduction in the logical error rate , provided the physical error rate p of the individual code qubits is below a threshold .

When ,

Fault tolerance

Error can occur at any location in the circuit.

Much overhead for fault tolerance

For a quantum circuit with noisy ancilla measurements, it is not always possible to decode the error correction code in a single round of syndrome extraction.

Encoded computation

universal computing: can do any unitary operation

A example of a universal gate set is

The major challenge in constructing a universal encoded gate set is to find ways in which the relevant gates can be performed fault tolerantly.

For many codes, it is possible to fault tolerantly implement a subset of the gates in without having to introduce additional qubits. This is achieved by defining the logical operators with a property known as tranversality that guarantees errors will not spread uncontrollably through the circuit. However, a no-go theorem exists that prohibits the implementation of a full universal gate set in this way on a quantum computer.

the surface code could realise a universal gate set using a method called magic state injection.

magical state injection — magical state **injection**

This is usually done through magic state distillation, which is a process that consumes multiple noisy logical and outputs fewer logical of higher fidelity using logical Clifford operations and post-selection.

http://arxiv.org/abs/2203.13123

Circuit to perform 15-to-1 magic state distillation

Code Switching

For constructing transversal gates in a universal set, we can change a QEC code A into another code B , we execute the transversal gate which are not transversal in code A, then we

change the code B back into code A.

Contextual Stories - Quantum Error Correction, Part 1

An interactive introduction to the surface code | Arthur Pesah

A bird’s-eye view of quantum error correction and fault tolerance | Arthur Pesah

What is a "temporal" or "timelike" logical error in the surface code? - Quantum Computing Stack Exchange

error correction - What's the logical X and Z operator in XZZX surface code? - Quantum Computing Stack Exchange

All you need to know about classical error correction | Arthur Pesah