Quantum Error Correction - Part 1

Quantum Error Correction - Part 1

Outline

This is the first lecture of an introductory course on Quantum Error Correction. In this lecture we will introduce the essential concepts to understand this fascinating topic. In particular: classical error correction, physical and logical qubits, the so called NISQ and FTQC era, and the No-cloning Theorem. We will end with showing how we can encode a logical qubit on top of physical ones using a simple quantum circuit. Below the full table of content:

Computation is noisy

Running computations on physical systems whether classical or quantum, is inevitably subject to noise. External factors, such as interaction with the environment, can alter the calculation and compromise the final result. This can lead to inaccurate calculations and, in the worst case, if errors propagate rapidly, to incorrect results.

For this reason, nature has developed various techniques known as error correction codes. For example, in biological systems, the information contained in DNA is encoded redundantly. Many classic error correction codes, which are implemented in classical computing, are inspired by biology and are based on duplication and redundancy.

This reality becomes even more drastic in quantum computing and technologies given that quantum physical systems, i.e. quantum states, are intrinsically fragile. For instance, random photons generated by heat, visible light, or other lower frequency light can interact with the qubits in the quantum computer. In this case, we say that qubits become then entangled with the environment and undergo decoherence.

Error Correction in Classical Computing

In classical error correction, one of the simplest way to fight noise is the repetition code. This consist of replicating/copying the information multiple times. For instance, you could use three bits to represent a single logical bit by encoding:

0→000,  1→1110 → 000, \hspace{2cm} \; 1→ 111

Now consider a noisy environment, where each physical bit has a probability pp of flipping. When reading a logical bit, you check all three physical bits and take a majority vote. If pp is small, then seeing something like 001001 likely means the last bit was corrupted by noise. You can confidently correct it by flipping it back, restoring the original state 000000.

💡 However, in quantum computing, this is prohibited. We will soon see that, given the No-Cloning Theorem, you cannot create an exact copy of an arbitrary quantum state. The no-cloning theorem forbids creating identical copies of a quantum system while preserving the original (see below). Quantum mechanics offers a uniquely powerful alternative: entanglement coupled with a clever protocol to detect and correct errors. Instead of duplicating quantum states, we use entanglement to distribute quantum information across multiple physical qubits.

To review Classical Quantum Error Correction, I suggest this video from 3Blue1Brown:

Quantum Error Correction: basic concepts

Quantum Error Correction (QEC) is a way of writing quantum algorithms and composing quantum circuits that encode information in a redundant way so that running the algorithms on a quantum computer is robust against noise from the environment.

Logical vs Physical Qubits

Before entering into QEC details, it is important to introduce and emphasize the concept of logical and physical qubits:

  • Logical qubits: an abstraction where a single, robust qubit state is spread across many physical qubits. Their stability is guaranteed by QEC. They take part of the logical computation enabling practical, fault-tolerant quantum computing.
  • Physical qubits: real, fundamental two-level quantum systems (e.g., electron spin, photon polarization, trapped ions) on a quantum chip. They are extremely susceptible to environmental noise, leading to high error rates and short coherence times, making long computations unreliable

In QEC, a quantum circuit is used to store a single logical qubit of information in the state of multiple noisy physical qubits, so that it is possible to determine and recover errors on the individual physical qubits protecting the logical information. In other words, there are noisy physical qubits that builds up logical qubits protected from noise through error correction. Entanglement between qubits plays a determinant role. It allows to distribute quantum information across multiple physical qubits. The challenge in QEC is that the implementation of error correction is itself error-prone.

Noisy Intermediate-Scale Quantum (NISQ) & Fault-Tolerant Quantum Computing (FTQC)

⏱ Noisy Intermediate-Scale Quantum (NISQ) is the quantum era we are living nowadays. In the NISQ era, quantum processors are caracterized by tens–thousands of noisy physical qubits, limited coherence, and no full error correction. Algorithms are typically hybrid (quantum + classical) and shallow in depth, often paired with error mitigation. Examples: Variational algorithms: VQE, Short-depth quantum simulation of small molecules/material patches, Sensing/metrology protocols leveraging entanglement at limited scale, Error mitigation workflows.

🔮 Fault-Tolerant Quantum Computing (FTQE) is the future of quantum many people are dreaming of. In the FTQE era the error detection and correction procedures can correct errors faster than they cascade. We speak of Fault-Tolerant Quantum Error Correction. This happens when computation on logical qubits protected by quantum error correction. Repeated syndrome extraction and decoding keep error rates below threshold, allowing arbitrarily deep circuits with predictable reliability. This design methodology ensures that a quantum computation can tolerate errors, so that QEC can remain effective in time throughout the execution of a quantum algorithm. Examples: Surface/toric/color codes, Large-scale quantum simulation (chemistry, materials, high-energy) with phase estimation/qubitization, Deep algorithms (e.g., factoring, advanced optimization, cryptography-relevant primitives)

In few words: NISQ → do the best with noisy qubits today (hybrid, shallow, mitigated). FTQC → protect and scale tomorrow (logical qubits, deep and dependable).

Quantum Error Correction (QEC) vs Quantum Error Mitigation (QEM)

QEM is a set of algorithmic/statistical techniques that reduce bias in measured observables on noisy hardware without encoding into error-correcting codes. It leaves circuits mostly unchanged and fixes results via calibration and post-processing. Examples: zero-noise extrapolation (ZNE), probabilistic error cancellation (PEC), measurement-error mitigation (MEM), symmetry verification/post-selection, Clifford Data Regression (CDR/vCDR), randomized compiling/Pauli twirling; often paired with dynamical decoupling.

QEM is useful today on NISQ devices: shallow-moderate depth circuits (VQE, short-depth QAOA, sensing), limited qubits, no fast mid-circuit measurement/feed-forward. It’s quick to adopt and improves expectation values, but offers no asymptotic reliability; sampling overhead and noise-model mismatch can limit gains. On the other hand, QEC is a set of coding techniques that protect quantum states during computation by encoding logical qubits into many physical qubits, measuring syndromes, and correcting errors online. It provides scalability via fault tolerance once below threshold error rates. Examples: 3-qubit repetition (bit/phase-flip) codes, Shor [[9,1,3]], Steane [[7,1,3]], surface/toric codes, Bacon–Shor, color codes; decoded via methods like minimum-weight matching. QEC will be decisive going forward for FTQC: deep circuits, long algorithms, and guaranteed reliability via syndrome cycles, fast classical decoding, and code distance scaling (e.g., surface-code thresholds ~1% order of magnitude). It demands substantial qubit/control overhead but is the only path to scalable, arbitrarily long computations; QEM will remain a complementary tool for trimming bias and shot cost.

The No-Cloning Theorem

The No-Cloning Theorem says we cannon copy an arbitrary unknown quantum state. On the other side (and this is often misunderstood) it is possible to copy a known quantum state (if we could not prepare arbitrary quantum states multiple time, or on multiple qubits, quantum computing would be useless). To see what the No-Cloning Theorem is, suppose we have two initial (pure) states ∣ψ⟩|\psi \rangle and ∣s⟩|s\rangle. The quantum information that we wish to copy is ∣ψ⟩|\psi\rangle, and we want to copy it into the target state ∣s⟩|s\rangle. So, our initial state is ∣ψ⟩⊗∣s⟩|\psi\rangle \otimes |s\rangle. Now suppose some unitary operator UU evolves the system:

∣ψ⟩⊗∣s⟩↦U(∣ψ⟩⊗∣s⟩)=∣ψ⟩⊗∣ψ⟩|\psi\rangle \otimes |s\rangle \mapsto U(|\psi\rangle \otimes |s\rangle) = |\psi\rangle \otimes |\psi\rangle

Suppose now that the unitary operator copies a second unknown state ∣ϕ⟩|\phi \rangle:

∣ϕ⟩⊗∣s⟩↦U(∣ϕ⟩⊗∣s⟩)=∣ϕ⟩⊗∣ϕ⟩|\phi\rangle \otimes |s\rangle \mapsto U(|\phi\rangle \otimes |s\rangle) = |\phi\rangle \otimes |\phi\rangle

Remember, we assumed from the beginning we could copy an arbitrary unknown state, so there is no reason UU should be able to copy the second state ∣ϕ⟩|\phi \rangle as well as the first one ∣ψ⟩|\psi \rangle. From this we take the inner product of the following two equations,

U(∣ψ⟩⊗∣s⟩)=∣ψ⟩⊗∣ψ⟩U(∣ϕ⟩⊗∣s⟩)=∣ϕ⟩⊗∣ϕ⟩U(|\psi\rangle \otimes |s\rangle) = |\psi\rangle \otimes |\psi\rangle \\ U(|\phi\rangle \otimes |s\rangle) = |\phi\rangle \otimes |\phi\rangle

and we obtain,

(⟨s∣⊗⟨ψ∣)U†U(∣ϕ⟩⊗∣s⟩)=(⟨ϕ∣⊗⟨ϕ∣)(∣ψ⟩⊗∣ψ⟩)(⟨s∣⊗⟨ψ∣)I(∣ϕ⟩⊗∣s⟩)=⟨ϕ∣⊗⟨ϕ∣ψ⟩⊗∣ψ⟩⟨ϕ∣ψ⟩⟨s∣s⟩=⟨ϕ∣ψ⟩⟨ϕ∣ψ⟩⟨ϕ∣ψ⟩=(⟨ϕ∣ψ⟩)2.(\langle s| \otimes \langle \psi|)U^{\dagger} U(|\phi\rangle \otimes |s\rangle) = (\langle \phi| \otimes \langle \phi|)(|\psi\rangle \otimes |\psi\rangle)\\ (\langle s| \otimes \langle \psi|)I(|\phi\rangle \otimes |s\rangle) = \langle \phi| \otimes \langle \phi|\psi \rangle \otimes |\psi \rangle \\ \langle \phi|\psi \rangle \langle s|s\rangle = \langle \phi|\psi \rangle \langle \phi|\psi \rangle \\ \langle \phi |\psi \rangle = (\langle \phi |\psi \rangle)^2.

However, this is essentially just the equation x=x2x = x^2, which has only two solutions, x=0x=0 and x=1x=1. So, either ⟨ψ∣ϕ⟩=0\langle \psi |\phi \rangle = 0 and the two states are orthogonal to each other, or ⟨ψ∣ϕ⟩=1\langle \psi |\phi \rangle = 1 and ∣ψ⟩=∣ϕ⟩|\psi\rangle = |\phi\rangle. So a *cloning operator* can only copy states that are orthogonal to each other, and a general cloning device cannot be constructed. 💡 Consequence: this presents a difficulty in creating error corrections codes because we cannot simply copy information in a repetition code the way we are able to in the classical bit-based data setting. Redundancy must be implemented via entanglement and stabilizers, not by copying. Encodings spread information non-locally across multiple qubits.

For another perspective on the No-Cloning Theorem, I invite you to watch one of the lessons from the excellent online course by Artur Ekert:

Quantum Error Types

As mentioned above, QEC consist of a series of methods for constructing logical qubits that are more robust to noise than the underlying physical qubits. Before diving into this topic, it is useful to ask ourselves:

🤔 What types of errors can qubits suffer?

Qubits can undergo several types of errors:

  • Bit Flip (this is the effect of XX gate): swapping of ∣0⟩↔∣1⟩|0 \rangle \leftrightarrow | 1\rangle
  • Phase Flip (this is the effect of ZZ gate): swapping of ∣+⟩↔∣−⟩|+ \rangle \leftrightarrow | -\rangle
  • Combination of XX and ZZ (this is the effect of YY gate): a simultaneous bit- and phase-flip, represented as iXZiXZ
  • Other errors (we will not discuss them in these lessons): such as amplitude damping, depolarizing, etc.

Quantum Error Correction Pipeline

In general, a QEC scheme is composed by several steps:

  • Qubit encoding: define how logical qubits are encoded within the physical system
  • Error detection or syndrome: extract information about possible errors, without disturbing the logical state
  • Error correction: infer the error from that information and apply the appropriate correction

We will conclude this first tutorial introducing the first step: Qubit encoding!

Qubit Encoding

We will show the simplest way to encode a logical qubit using a quantum circuit. This encoding can protect the logical qubit from bit-flip errors. There are more sophisticated ways to encode logical qubits, but the following is simple and allows us to better understand the basic mechanism.

A bit-flip error, i.e a swap of ∣0⟩↔∣1⟩|0 \rangle \leftrightarrow | 1\rangle, can be represented as an unintended action by operator XX on a qubit. To protect against bit-flips we encode the state ∣ψ⟩=α∣0⟩+β∣1⟩|\psi\rangle = \alpha|0\rangle + \beta|1\rangle into three qubits as the state α∣000⟩+β∣111⟩\alpha|000\rangle + \beta|111\rangle. This can be written as:

∣0⟩↦∣0L⟩=∣000⟩∣1⟩↦∣1L⟩=∣111⟩|0\rangle \mapsto |0_L\rangle = |000\rangle \\\\ |1\rangle \mapsto |1_L\rangle = |111\rangle
  • The logical ∣0⟩|0\rangle state corresponds to the encoded state ∣0L⟩|0_L\rangle
  • The logical ∣1⟩|1\rangle state corresponds to the state ∣1L⟩|1_L\rangle
  • The physical states are the states of the three qubit system into which these logical states are encoded.
🤔 As shown above, a logical qubit is encoded into several physical qubits. How this is practically implemented?

To encode a logical qubit we make use of a quantum circuit, such as in the picture below:

image

Further Readings

For those of you interested about the role that QEC might play in space-time building, I suggest:

Thanks for reading and soon I will share Part 2 of this blog series.