Introduction to Quantum Error Correction
and Fault Tolerance

Steven M. Girvin*

Yale Quantum Institute

17 Hillhouse Ave.

PO Box 208334

New Haven, CT 06520-8263 USA

*<EMAIL_ADDRESS>
## Abstract

These lecture notes from the 2019 Les Houches Summer School on ‘Quantum
Information Machines’ are intended to provide an introduction to classical and
quantum error correction with bits and qubits, and with continuous variable
systems (harmonic oscillators). The focus on the latter will be on practical
examples that can be realized today or in the near future with a modular
architecture based on superconducting electrical circuits and microwave
photons. The goal and vision is ‘hardware-efficient’ quantum error correction
that does not require exponentially large hardware overhead in order to
achieve practical and useful levels of fault tolerance and circuit depth.

###### Contents

  1. 1 Introduction: The Grand Challenge
  2. 2 Classical Error Correction and Fault Tolerance
    1. 2.1 Error-detection Parity-check Code
    2. 2.2 Error Correction Parity Check Codes: Part 1
      1. 2.2.1 Repetition Code
    3. 2.3 Error Correcting Parity Check Codes: Part 2
    4. 2.4 The Hamming Code
      1. 2.4.1 SARS COV-2 Sample Pooling
      2. 2.4.2 Example LDPC: The Hamming [7,4,3] Code
    5. 2.5 Fault-Tolerant Classical Error Correction
    6. 2.6 Fault-Tolerant Memory Operations
    7. 2.7 Fault-Tolerant Classical Gate Operations
    8. 2.8 Recursion and Fault-Tolerance Thresholds
  3. 3 Quantum Error Correction For Two-Level Systems (Qubits)
    1. 3.1 Coherent Errors
    2. 3.2 Errors due to entanglement with a bath
    3. 3.3 Quantum Error Correction as an Adversarial Game
  4. 4 Quantum Operations and Kraus Representations of Error Channels
    1. 4.1 Quantum Codes and the Knill-Laflamme Condition
    2. 4.2 Error Recovery Operation
    3. 4.3 Recovery Operation for the Quantum Repetition Code
    4. 4.4 Four-qubit Amplitude-Damping Code
  5. 5 Topological Quantum Error Correction: Kitaev’s Toric Code and the Surface Code
    1. 5.1 Toric Code as Quantum Memory
  6. 6 Overview of Bosonic Modes
    1. 6.1 Introduction
    2. 6.2 Pros and Cons of Microwave Bosonic Modes
    3. 6.3 Gaussian and Non-Gaussian States of Oscillators
    4. 6.4 Kraus Map for the Damped Harmonic Oscillator
  7. 7 Quantum Error Correction for Bosonic Modes
    1. 7.1 Introduction
    2. 7.2 Binomial Codes
  8. 8 Gottesman-Kitaev-Preskill Bosonic Codes
    1. 8.1 Geometry of Phase Space: Non-Commuting Translations and Boosts
    2. 8.2 GKP Codes: Lattices in Phase Space
    3. 8.3 Error Correction with GKP Codes
  9. 9 Lacunae
  10. 10 Conclusion

Link to Video Lectures

The website for the 2019 Les Houches School on Quantum Information Machines
contains links to slides and videos for the various lectures:

https://physinfo.fr/houches2019/program.html

##  1 Introduction: The Grand Challenge

The last 20 years have seen spectacular experimental progress in our ability
to create, control and measure the quantum states of superconducting
‘artificial atoms’ (qubits) and microwave photons stored in resonators. In
addition to being a novel testbed for studying strong-coupling quantum
electrodynamics in a radically new regime, ‘circuit QED,’ defines a
fundamental architecture for the creation of all-electronic quantum computers
based on integrated circuits with semiconductors replaced by superconductors.
The artificial atoms are based on the Josephson tunnel junction and their
relatively large size ($\sim$mm) means that they couple extremely strongly to
individual microwave photons. This strong coupling yields very powerful state-
manipulation and measurement capabilities, including the ability to create
extremely large ($>100$ photon) ‘cat’ states and easily measure novel
quantities such as the photon number parity. These new capabilities are
enabling new schemes for ‘continuous variable’ quantum error correction based
on encoding quantum information in superpositions of different Fock states of
microwave photons.

The grand challenge facing us as we attempt to build large-scale quantum
machines is fault tolerance. How do we build a nearly perfect machine from a
large collection of imperfect parts? This question was addressed in the
classical domain by von Neumann beginning after the second world war [1], in a
series of lectures at Caltech in 1952 that were published in 1956 [2] and in
the Silliman Lecture at Yale which he was unable to deliver but whose
manuscript was published posthumously [3]. In addition to thinking about the
crude and unreliable vacuum tube computers of his day, he was fascinated by
the ability of the complex network of neurons in the brain to reliably
compute. Claude Shannon, whose master’s thesis first proved that circuits of
switches and relays could perform arbitrary Boolean logic operations [4], was
also keenly interested in this problem [5].

Von Neumann showed (not quite rigorously) that a Boolean function that can be
computed by a network of $L$ reliable gates can be reliably (i.e., with high
probability) computed by a network of $\mathcal{O}(L\log L)$ unreliable gates.
This result was made rigorous by Dobrushin and Ortyukov [6]. Useful works to
consult, to learn more about this field, include [7, 8, 9, 10]. The modern
perspective connects the problem of reliable computation with unreliable
devices to Shannon’s information theory [11] which describes how to reliably
communicate over a noisy channel. As illustrated in Fig. 1, in Shannon’s
information theory, only the communication channel is considered unreliable
and the encoding at the input and decoding at the output is taken to be
perfect. A reliable computation can be performed by unreliable circuits by
using circuit modules that operate on codewords designed for the Shannon
communication problem and frequently checking them. The trick is to find ways
to distinguish between differences in the output and input of the module that
are intentional (i.e., due to the module correctly computing the intended
function of the input) or are erroneous [10].

Figure 1: Shannon communication problem. The sender’s message plus some
redundant information about that message are encoded by an ideal encoder and
transmitted over a noisy channel which introduces errors. The received
erroneous message is then processed by an ideal decoder which outputs the
recovered message plus ancillary information about the particular errors that
the channel randomly introduced. In this model, only the noisy channel is
imperfect. The computations needed for encoding and decoding are assumed to be
carried out by error-free hardware.

In addition to this key connection to information theory, there is also an
important connection to control theory, illustrated in Fig. 2. A quantum
computer is a dynamical system we are attempting to control despite noise and
errors that occur continuously in time. Classical control theory, founded by
Norbert Wiener, deals with a system (traditionally known as the ‘plant’ and
which might actually represent a car manufacturing or chemical production
plant) subject to errors. As illustrated in Fig. 3, sensors take continuous
measurements of the state of the plant and a controller analyzes this
information and uses it to provide (via an ‘actuator’) feedback to the plant
to keep it running stably and reliably. Robust control systems are able to
deal with the fact that the sensors, controller and actuator units can also be
made of unreliable parts. We will find this a useful point of view but will
have to deal with a number of subtleties in thinking about the control of
quantum systems since we know that measurements on a quantum state disturb the
state through measurement ‘back action’ (state collapse).

Figure 2: Three foundational topics in the study of complex classical systems.
Information theory was developed to study reliable communication over a noisy
channel using codes containing redundant information, but assuming reliable
computation for the encoding and decoding of that information. Reliable
computation requires understanding how to use redundant hardware to ensure
proper functioning of the computer. Robust control theory studies the use of
feedback to stabilize the operation of a complex system, even when the
sensors, actuators and feedback controller are imperfect.  Figure 3: Classical
control theory describes a system (‘the plant’) whose state is controlled by a
feedback system consisting of sensors, a controller that decides how to
respond to the sensor information by sending signals to an actuator which
adjusts parameters in the plant to maintain it in the desired state despite
perturbations. Robust control theory deals with the problem that the sensors,
controller and actuator can be imperfect.

The field of quantum machines has made tremendous experimental strides in the
last two decades and we are just entering the era where the hardware is now
reliable enough to begin to carry out quantum error correction. As we begin to
scale up existing small quantum processors to ever larger numbers of
components, it is essential that we learn how to do fault-tolerant design and
control of these novel and powerful new machines. This is the grand challenge
that must be met if the second quantum revolution is to succeed.

These lecture notes will discuss general issues in classical and quantum error
correction and fault tolerance with a focus on quantum information processing
with superconducting qubits and microwave photons using the ‘circuit QED’
architecture.

##  2 Classical Error Correction and Fault Tolerance

A significant benefit of the representation of information as discrete bits
(with 0 and 1 corresponding to a voltage for example) is that one can ignore
small noise voltages. That is, $V=0.99$ volts can be safely assumed to
represent 1 and not 0. Modern electronic logic chips deal with noise on input
signals by processing them through a circuit whose voltage input output
relation is shown schematically in Fig. (4). It is clear from this that input
voltages less than 0.5 are clamped near zero on the output and input voltages
larger than 0.5 are clamped near 1 on the output. This effectively erases
errors from small voltage deviations and makes digital devices more robust
than analog devices.

Figure 4: Input-Output relation for a voltage clamping circuit that eliminates
noise in classical logic devices.

Even relatively ‘small’ digital devices today contain a vast number of
components. For example, a typical cell phone contains more than 5 billion
transistors in its processor chips plus even more components in its memory.
Even if the individual components are highly reliable, they are never perfect.
This means that such a complex system will almost certainly fail to operate
correctly unless it is constructed using the principles of _fault tolerant
design_. Roughly speaking we must design our systems to be tolerant of two
kinds of faults–memory errors and gate operation errors. We will begin our
analysis with memory errors.

To overcome the deleterious effects of more severe electrical and magnetic
noise, cosmic rays, transistor failures and other hazards, modern digital
computer memories and information storage devices rely on error correcting
codes to store and correctly retrieve vast quantities of data. As illustrated
in Fig. 5, it turns out that there is a deep connection between memory error
correction and Claude Shannon’s work [11] on using redundant encoding of
messages for reliable communication of information over a noisy channel. In
the communication problem, Alice sends a message to Bob and the message is
corrupted by noise and loss during the transmission through space. We can view
the memory problem as Alice sending herself a message through time. She wants
to store information and retrieve it later, but it may become corrupted during
the passage of time.

Figure 5: In the communication problem, Alice sends Bob a message over a noisy
channel which may corrupt some of the bits. In the memory problem, Alice sends
herself a message over time by storing it in a memory that may become
corrupted. From the point of view of designing error correction codes to make
the messages robust, communication and storage are exactly the same problem.

Classical error correction works by introducing extra bits which provide
redundant encoding of the information. A familiar everyday example is the
phonetic alphabet used by air traffic control centers and pilots in their
communications. ‘Hold short of taxiway Tango Delta Bravo,’ is a lot easier to
understand in a noisy environment than ‘Hold short of taxiway TDB.’ The
‘distance’ in ‘acoustic signal space’ between ‘T,’ ‘D,’ and ‘B’ is much
smaller than for the lengthier codewords ‘Tango,’ ‘Delta,’ and ‘Bravo.’ The
latter are therefore more readily distinguished and correctly decoded when we
hear them. More formally, classical error correction proceeds by measuring the
bits and comparing them to the redundant information in the auxiliary bits.

All classical (and quantum) error correction codes are based on the assumption
that the hardware is good enough that errors are rare. The goal is to make
them even rarer. For classical bits there is only one kind of error, namely
the bit flip which maps 0 to 1 or vice versa. This error channel is
illustrated in Fig. 6.

Figure 6: In classical communication there is only one type of error, namely
the bit flip. If Alice sends a 0 to Bob, it correctly arrives as a zero with
probability $p_{00}$ and incorrectly arrives as a 1 with probability
$p_{01}=1-p_{00}$. If Alice sends a 1 to Bob it correctly arrives as a 1 with
probability $p_{11}$ and incorrectly arrives as a 0 with probability
$p_{10}=1-p_{11}$. The case $p_{10}=p_{01}=\epsilon$ is known in classical
information theory as the ‘binary symmetric channel’ (BSC).

As indicated in Fig. 6, in general the probability $p_{10}$ or an error when
transmitting a 1 can be different than the error probability for transmitting
a 0, $p_{01}$. For example, in transmitting a signal over an optical fiber, we
might have a code in which the presence of a photon indicates a 1 and the
absence of a photon encodes a 0. Attenuation (optical absorption) in the fiber
can lead to photons being lost which contributes to $p_{10}$. The physical
processes that contribute to $p_{01}$ are different and might include stray
photons entering the fiber from the environmental so-called ‘dark counts’ in
the photon detectors at the receiving end of the channel. Because the physical
mechanisms leading to the two errors are different, in general the error rates
will be different when transmitting 0’s and 1’s (with this particular encoding
and physical transmission channel). If for example, we can only lose photons
and never gain them, then 0 is always transmitted correctly, but 1 is
sometimes received as a 0. This a highly asymmetric noise channel. Here we
will assume for simplicity the binary symmetric channel (BSC) which is
characterized by a single error probability $\epsilon=p_{10}=p_{01}$
(typically with $\epsilon\ll 1$), and has the important property that error
occurrences are independent (uncorrelated) among different bits.

Another important error model is the _erasure channel_. In this case one knows
which bits are erroneous, but not their correct values. For example, suppose
that we are transmitting information via the polarization of individual
photons: vertical polarization could represent 0 and horizontal polarization
could represent 1. By passing the received photons through a polarizing beam
splitter, vertically polarized photons will land on one detector and
horizontally polarized photons will land on a different detector. If a message
is transmitted as a sequence of vertically and horizontally polarized photons
and one of those photons is absorbed by the transmitting medium (e.g., the
optical fiber), then the receiver will detect neither polarization (neither
detector will click) and we will know that particular photon has been lost.
Thus photon loss in this particular code is an erasure error. Erasure errors
are vastly easier to correct because we are given extra information–namely
which bits are erroneous. This is in contrast to a physical encoding in which
1 is represented by the presence of a photon and 0 is represented by the
absence of a photon. In this case, loss of a photon means that a 1 is
incorrectly received as a 0 rather than as an erasure. This means that the
error correction code has to be more sophisticated and be able to correct
errors at unknown locations.

The most general definition of an erasure error is that it is an unknown error
at a known location (i.e. on a known physical bit). Knowing which physical bit
has gone bad is very useful information and this makes correcting such errors
easier [12].

###  2.1 Error-detection Parity-check Code

Before considering codes which can correct errors, let us begin with a simple
example of a code that can detect, but not correct, a single error. Imagine
that the data is sent in blocks of $m$ bits. For example $m=8$ would
correspond to one byte of data. Now let Alice append an ancilla bit. This
redundant bit is called the ‘parity check’ bit and she arranges its value to
be such that the total parity of the $m+1$ bits is (say) even. Thus if the
number of 1’s in the first $m$ bits is even, she makes the parity check bit
have the value 0. Conversely if the number of 1’s in the first $m$ bits is
odd, she gives the parity check bit the value 1. Alice sends the $m+1$ bits
through a noisy channel to Bob. It is possible that one or more errors has
occurred, including perhaps in the parity check bit itself. Bob can then
compute the parity of the received bit string. If he finds that the parity is
even, he knows that the number of errors is even (and possibly 0). If he knows
that errors are sufficiently rare that he can neglect the possibility of more
than one error, then he can assume that with high probability there was no
error. (If there were an even number of bit flips, he would be fooled, but the
probability of 2 or more errors is very small.) If Bob sees that the parity is
odd, he knows that there was an error (or more precisely an odd number of
errors) and he can reject the information and ask Alice to resend it.111Notice
that if the single error is an erasure error, then we can recover the correct
bit value from the parity information in the remaining bits. This is a simple
example of why erasure errors are easier to deal with. This code that can
detect single errors at unknown locations, but can correct single erasure
errors. For the BSC, the probability of no errors occurring in a string of
$m+1$ bits is

$P_{0}=(1-\epsilon)^{m+1}\sim 1-(m+1)\epsilon,$ (1)

with the latter approximation being valid for $(m+1)\epsilon\ll 1$. The
probability of a single bit flip error is

$P_{1}={}_{m+1}C_{1}(1-\epsilon)^{m}(\epsilon)^{1}=(m+1)\epsilon(1-\epsilon)^{m}\sim(m+1)\epsilon,$
(2)

where ${}_{N}C_{k}$ is the binomial coefficient or combinatorial factor ‘$N$
choose $k$’

${}_{N}C_{k}=\frac{N!}{(N-k)!\,k!}$ (3)

Failure to detect an error occurs only if there are an even (but non-zero)
number of errors, The most likely case for failure is the case with the
smallest even number of errors, namely 2. The probability for this to occur is

$P_{2}={}_{m+1}C_{2}(1-\epsilon)^{m-1}(\epsilon)^{2}=\frac{(m+1)m}{2}\epsilon^{2}(1-\epsilon)^{m-1}\sim\frac{m(m+1)}{2}\epsilon^{2}.$
(4)

Assuming $m\epsilon/2\ll 1$, we have $P_{2}\ll P_{1}$ and so Bob can correctly
detect errors with high probability. The actual failure probability is
slightly larger than $P_{2}$ because $P_{4},P_{6},P_{8},...$ all contribute
but these probabilities are very small.

###  2.2 Error Correction Parity Check Codes: Part 1

To actually correct the error, Bob would have to know the location of the
error, but this information is not available to him in the simple parity check
code described above. Before exploring error correction parity check codes in
more detail, let us warm up with study of a very simple code, the repetition
code.

####  2.2.1 Repetition Code

It is useful to review the very simple (and not very efficient) repetition
code which is capable of not just detecting, but actually correcting a fixed
number of errors. The repetition code is perhaps the easiest classical error
correction code to understand and involves sending multiple copies of the data
and decoding using majority rule. Versions of this code can correct multiple
errors, but the code is very inefficient since it encodes only $1$ error-
correctable logical data bit in a string of $N$ physical bits and thus has
code rate $r=1/N$ which asymptotically goes to zero for large $N$.

To understand the repetition code, let us consider a register of $N=2m+1$
physical bits which we arrange to be in one of two ‘logical codewords’ (bit
strings representing logical 0 and logical 1)

$\displaystyle 0_{\mathrm{L}}$ $\displaystyle=$ $\displaystyle(000\dots 00)$
(5) $\displaystyle 1_{\mathrm{L}}$ $\displaystyle=$ $\displaystyle(111\ldots
11).$ (6)

We choose $N$ odd so that we can do majority voting in the decoding step. We
can encode this logical bit by having a single original data bit and copying
its value into the $2m$ additional ancilla bits in the register. Any state of
the register not equal to one of the two logical codewords, is by definition,
an error state.

The easiest repetition code to analyze is the smallest one which has $2m+1=3$
physical bits: $M=1$ original data bits and $R=2$ ancilla bits. Assuming that
the total number of errors in the register is limited to being either 0 or 1,
there will be $M+R+1=4$ possible error states (with the $+1$ accounting for
the possibility of zero errors) that can be encoded in the $2^{R}=4$ ancilla
states, still leaving the original information available after decoding in the
$2^{M}=2$ states of the data bit. (It is useful at this point to review Fig. 1
to see that the encoding has to have enough degrees of freedom to allow the
received version of the message to store both the intended message and the
information on which errors occurred in the noisy channel.)

Suppose now that one of the three physical bits suffers an error. By examining
the state of each bit it is a simple matter to identify the bit which has
flipped and is not in agreement with the ‘majority.’ We then simply flip the
minority bit so that it again agrees with the majority. This procedure
succeeds if the number of errors is zero or one, but it fails if there is more
than one error (because the majority is now wrong). Of course since we have
replaced one imperfect bit with three imperfect bits, this means that the
probability of an error occurring has increased considerably. For three bits
the probability $P_{n}$ of $n$ errors is given by

$\displaystyle P_{0}$ $\displaystyle=$ $\displaystyle(1-\epsilon)^{3}$ (7)
$\displaystyle P_{1}$ $\displaystyle=$ $\displaystyle
3\epsilon(1-\epsilon)^{2}$ (8) $\displaystyle P_{2}$ $\displaystyle=$
$\displaystyle 3\epsilon^{2}(1-\epsilon)$ (9) $\displaystyle P_{3}$
$\displaystyle=$ $\displaystyle\epsilon^{3}.$ (10)

Every error correction code begins by adding ancilla bits. This means that the
probability of errors actually rises. For example, we see from the above that
the probability of at least one error is

$1-P_{0}=1-(1-\epsilon)^{3}\sim 3\epsilon,$ (11)

where the approximation in the last term is valid for small $\epsilon$. We see
that in this limit the error probability triples. Our error correction circuit
must overcome this enhanced error probability if the error probability for the
logical qubit is to be lower than that for a single physical qubit.

Because our error correction code only fails for two or more physical bit
errors the error probability for our logical qubit is

$\epsilon_{\mathrm{logical}}=P_{2}+P_{3}=3\epsilon^{2}-2\epsilon^{3},$ (12)

As can be seen in Fig. 7, if $\epsilon<\epsilon^{*}=1/2$, then the error
correction scheme reduces the error rate (instead of making it worse). If for
example $\epsilon=10^{-6}$, then $\epsilon_{\mathrm{logical}}\sim 3\times
10^{-12}$. Thus the lower the raw error rate, the greater the improvement.
Note however that even at this low error rate, a petabyte ($8\times 10^{15}$
bit) storage system would have on average 24,000 errors. Futhermore, one would
have to buy three petabytes of storage since 2/3 of the disk would be taken up
with ancilla bits!

######  Box 1.

Break-Even Point for Error Correction The particular value
$\epsilon=\epsilon^{*}$ of the physical bit error probability at which
$\epsilon_{\mathrm{logical}}=\epsilon$ is known as the break-even point for
error correction. For $\epsilon>\epsilon^{*}$, error correction makes things
worse, while for $\epsilon<\epsilon^{*}$ the error correction increases the
lifetime of the quantum information. (Specifically in the case described
above, it is the break-even point for memory operation. The break-even point
for gate operations is a separate matter.) In general, the physical qubits
making up the logical bit have inhomogeneous properties. In this case, the
break-even point is conservatively defined as that point at which the error
probability of the logical bit is lower than that of the best physical bit
comprising it. A vivid example of the break-even point can be found in the
first transatlantic solo airplane flight in 1927 by Charles Lindbergh. Many
people thought that Lindbergh was foolish for using a single-engine airplane.
However, he correctly understood that having two engines doubled the
probability of engine failure in flight. He further understood that the 1927
engine technology was such that, unlike today, a twin-engine plane with one
engine out could barely fly and would not be able to reach a safe landing
place (such as Keflavik, Iceland). In short, the aircraft engine repetition
code did not exceed break even in 1927.

Figure 7: Logical error probability $\epsilon_{\mathrm{logical}}$ for the
classical repetition code vs. physical qubit error probability $\epsilon$.
Solid line is the $2m+1=3$ bit code. Dashed line is the $2m+1=21$ bit code.
The straight line is the single bit error probability. We see that the
repetition codes have a break-even point of $\epsilon^{*}=\frac{1}{2}$. Below
that value the logical error rate is lower than the physical error rate for a
single bit even though the logical bits contain more than one physical bit.
Notice that the larger the repetition code, the more sharp is the transition
near the threshold and the greater is the error correction gain at low
physical error rates.

The calculation above was for the case $2m+1=3$ bit code. For general $m$, the
repetition code fails only if there are more than $m$ errors (at which point
the errors are in the majority). Hence for physical bit error probability
$\epsilon$, the logical bit error probability is

$\epsilon_{\mathrm{logical}}=\sum_{n=m+1}^{2m+1}{}_{2m+1}C_{n}\,\,\epsilon^{n}(1-\epsilon)^{2m+1-n}$
(13)

where the summation is over the number of errors $n$. Keeping the full
expression without approximation, we see that the error threshold is
$\epsilon^{*}=\frac{1}{2}$ independent of the number of bits $2m+1$ in the
repetition code (visible graphically in Fig. 7 for the particular cases of
$m=1$ and $m=10$). However the error correction ‘gain’

$G=\frac{\epsilon}{\epsilon_{\mathrm{logical}}}$ (14)

is greater and greater for larger $m$, especially for $\epsilon\ll 1$ because
the code can tolerate up to $m$ errors and hence

$\epsilon_{\mathrm{logical}}\sim\frac{(2m+1)!}{m!(m+1)!}\,\epsilon^{m+1}$ (15)

in the limit of small $\epsilon$.

Notice that for large codewords of length $N=2m+1$, the number of errors $n$
(assuming as usual that they are uncorrelated) is also large on average:

$\bar{n}=\langle n\rangle=\epsilon N.$ (16)

If $\bar{n}$ is large then the probability distribution $P(n)$ for the number
of errors is approximately a Gaussian with mean $\bar{n}$ and standard
deviation $\sigma=\sqrt{\bar{n}}$. [See Exercise 2.2.1.] The code can correct
up to $m$ errors which means that failure requires a statistical fluctuation
in $n$ above the mean of $\Delta n\geq(m+1)-\bar{n}$. This is a fluctuation
corresponding to a very large number of standard deviations above the mean

$\frac{\Delta n}{\sigma}\sim\sqrt{\frac{m}{2\epsilon}}\,,$ (17)

an extremely unlikely event222Strictly speaking our approximation of the
probability distribution as a Gaussian breaks down in the far tails of the
distribution (where it becomes exponential rather than Gaussian), but this
simple derivation gets across the main idea that the failure probability is
extremely small, though not actually as small as the Gaussian approximation
would suggest. for large $m$.

For large $m$, Fig. 7 shows a relatively sharp transition from low logical
error rate to 50% as the physical error rate approaches 50% from below. Use
the central limit theorem to estimate how the width of this transition scales
with $m$ in the limit of large $m$.

We see that in the limit of large codeword length $N=2m+1$, the code failure
probability can be made arbitrarily small. However the repetition code only
stores one error-correctable logical bit in $N$ physical bits so the rate
$r=1/N$ vanishes (polynomially) as the error rate decreases exponentially with
$N$. This simple code is very inefficient.

###  2.3 Error Correcting Parity Check Codes: Part 2

We can compute the minimum degree of redundancy needed to detect and correct a
single bit flip in a string of $N$ bits by the following argument. Suppose
that we have $M$ data bits we wish to protect using $R$ redundant bits. There
are $N=M+R$ possible single-bit errors (because the error could be in one of
the redundant bits, not just in the data bits). Including the case of zero
errors, there are a total of $M+R+1$ error states. If we are to be able to
correct the error, we must know the error state and hence a necessary
condition is that $R$ be large enough to encode the error state. Thus we must
have

$2^{R}\geq M+R+1.$ (18)

We previously discussed the three-bit repetition code which has $M=1,R=2$ for
which the inequality in eqn (18) is satisfied as an equality. However we saw
that for highly redundant repetition codes with $R\gg 1$, the LHS of eqn (18)
is exponentially larger than the RHS, and yet the codes only hold a single
logical bit ($M=1$). For example with $R=10$ we could encode $1024$ error
states. Hence the number of data bits that we should be able to protect
against single errors is $M=1013$, much greater than $1$. This does not prove
sufficiency, i.e., that there exists an encoding/decoding circuit that will do
this, but it turns out there are parity check codes which will in fact work.
Notice that such a code would be very efficient: Out of $1024$ bits we send,
1013 of them are data bits and only 11 of them are ancilla bits. This
efficiency is quantified in the _code rate_

$r=\frac{\mathrm{data\ bits}}{\mathrm{total\ bits}}=\frac{1013}{1024}\approx
0.989.$ (19)

Because the number of redundant bits grows only logarithmically with the
number of bits $R\sim\log_{2}[M+R+1]\sim\log_{2}[N]$, the code rate

$r=\frac{N-R}{N}\sim 1-\frac{\log_{2}N}{N}$ (20)

asymptotically approaches unity as $N$ increases. Notice however that this
class of codes only corrects a single error and for them to work with high
probability, we would need $\epsilon[M+R]\ll 1$ and thus the error rate would
have to fall like $\epsilon\sim\Lambda/M$ as $M$ increases where $\Lambda\ll
1$ is a constant.

For a given fixed error rate $\epsilon$, the average number of errors in an
encoded message of length $N$ is of course $\epsilon N$ which becomes very
large as $N$ grows. Thus to deal with this situation, we would need to have
codes that for large $N$ can correct a large number of errors with very high
success probability. We saw above that the simple repetition code can easily
achieve arbitrarily high success probability but only at the cost of
asymptotically zero rate (because they encode only a single logical bit). A
remarkable ‘noisy channel theorem’ from Claude Shannon gives a (non-
constructive) proof that codes exist which have arbitrarily low failure
probability and have finite (i.e., not asymptotically zero) rate even when the
physical error rate has a fixed non-zero value.

To work out the redundancy $R$ required when we have a fixed error rate
$\epsilon$ we need to understand how much information $S$ is needed to specify
the locations of the $N\epsilon$ errors that will (typically occur). This is
very simply obtained from the Shannon entropy produced by probability
distribution associated with the error channel

$S=-N[\epsilon\log_{2}\epsilon+(1-\epsilon)\log_{2}(1-\epsilon)]\approx
N\epsilon\log_{2}\left(\frac{2}{\epsilon}\right),$ (21)

where the last approximate equality is valid for sufficiently small
$\epsilon$. The number of parity check bits $R$ needed to fully identify a
typical set of errors is $\left\lceil S\right\rceil$. To provide (with high
probability) security against upward fluctuations in the number of errors
above the mean, one only needs to have $R=\left\lceil S+\omega\right\rceil$,
where $\omega$ is subextensive (i.e., a sub-linear function of $N$). To gain
some intuition for why $\omega$ is subextensive, imagine that there is a very
rare large fluctuation in the number of errors above the mean
$\bar{n}=\epsilon N$ by (say) $10\sqrt{\bar{n}}$ (i.e., $10$ standard
deviations). A simple and strict upper bound on the increase in the entropy of
the error distribution (and therefore the size of $\omega$ needed to have a
low failure probability) is $10\sqrt{\bar{n}}\log_{2}N$. (This is obtained by
ignoring the fact that there can be at most one error per bit and allowing the
permutation of the locations of the errors to be counted as new error states
even though they are not.) Hence $\omega/N$ becomes negligible in the
asymptotic large $N$ limit. Thus, based purely on this information theoretic
argument, it should be possible to achieve a code rate (for asymptotically
large $N$) approaching

$r=\frac{M}{M+R}=1-\frac{R}{N}\approx
1-\epsilon\log_{2}\left(\frac{2}{\epsilon}\right).$ (22)

Of course this argument is not a proof that codes can be constructed which
achieve this bound, but it does show that it is impossible for codes to exceed
this bound because the information obtained from measuring the parity check
bits must equal or exceed the entropy added to the message by the error
channel. The point of this calculation is that it shows that satisfying this
bound does not require a large fraction of the message to be parity check bits
(i.e., we only need a low density of parity check bits within the code) if the
error rate is low but finite and one can successfully encode and decode very
long bit strings (of length $N=M+R$). Hamming was able to prove that such
codes exist by showing that choosing codes with random arrangements of parity
checks (random Tanner graphs in the language which will be introduced shortly
below and illustrated in Fig. 8) almost always produces codes that approach
this limit. (Presumably such random codes are not practical in terms of the
computational cost of encoding and decoding them.)

There is a vast literature on practical parity-check codes that have non-zero
rate and computationally tractable encoding and decoding protocols. We will
not pursue these here, but will give one prototypical example of a simple
parity-check code, the Hamming code, that is distinct from the simple
repetition code.

###  2.4 The Hamming Code

Low-density parity-check codes (LDPCs) are used in classical communication to
redundantly encode messages so that errors in transmission can be corrected by
the receiver. They are also being explored theoretically for quantum error
correction. To understand how these codes work it is useful to take advantage
of a curious connection between these codes and the protocols that can be used
to pool testing samples for the novel corona virus SARS COV-2 in order to
reduce testing costs and increase speeds.

####  2.4.1 SARS COV-2 Sample Pooling

If the positivity rate is low, most tests come back negative. (For the moment
we will assume tests are 100% reliable with no false negatives or false
positives.) One can reduce the number of tests needed to find positive cases
by dividing samples into a number of different portions and pooling them with
other samples. This is illustrated in the so-called ‘Tanner graph’ in Fig. 8
showing how 7 samples $(S_{1},\ldots,S_{7})$ are combined into 3 pools
$(P_{1},P_{2},P_{3})$. The pooling is arranged so that each sample produces a
unique pattern of positive results in the pools. If all of the samples are
negative then all of the pools will be negative. If, for example, the first
sample is positive, then only $P_{1}$ will be positive, while if the seventh
sample is positive, then $P_{1},P_{2},P_{3}$ will all be positive. For
simplicity, we assume that the sample positivity rate $\epsilon\ll 1/7$, so
that the probability of getting two or more positive samples can be neglected
to first approximation. In this case there are eight possible sample states:
none are positive or any one of the seven are positive. These eight states can
be encoded into the three ‘pool bits’. A pool bit value of 0 means that no
samples in the pool are positive. A pool bit value of 1 means that (at least)
one of the samples in the pool is positive.

The connectivity of the Tanner graph can be conveniently represented by a
rectangular matrix

$H=\left(\begin{array}[]{ccccccc}1&0&1&0&1&0&1\\\ 0&1&1&0&0&1&1\\\
0&0&0&1&1&1&1\end{array}\right).$ (23)

$H_{jk}$ is the element of the matrix in row $j$, column $k$. $H_{jk}=1$ means
that sample $k$ is present in pool $j$. Each of the seven columns in $H$
represent a possible output bit string. For example if sample $k$ is the one
which is positive then the output bit string is

$\left(\begin{array}[]{c}P_{1}\\\ P_{2}\\\
P_{3}\end{array}\right)=\left(\begin{array}[]{c}H_{1k}\\\ H_{2k}\\\
H_{3k}\end{array}\right)$ (24)

when the pools are measured. Assuming that at most one sample is positive, the
input/output relation can be summarized by the matrix equation

$\left(\begin{array}[]{c}P_{1}\\\ P_{2}\\\
P_{3}\end{array}\right)=HS=\left(\begin{array}[]{ccccccc}1&0&1&0&1&0&1\\\
0&1&1&0&0&1&1\\\
0&0&0&1&1&1&1\end{array}\right)\left(\begin{array}[]{c}S_{1}\\\ S_{2}\\\
S_{3}\\\ S_{4}\\\ S_{5}\\\ S_{6}\\\ S_{7}\end{array}\right),$ (25)

where

$S=\left(\begin{array}[]{c}S_{1}\\\ S_{2}\\\ S_{3}\\\ S_{4}\\\ S_{5}\\\
S_{6}\\\ S_{7}\end{array}\right)$ (26)

is a vector describing the state of the samples. If none of the samples are
positive, all of the entries in $S$ are $0$. If sample $k$ is the positive,
then $S_{k}=1$ and the remaining entries are $0$.

Notice that each row in $H$ contains four 1’s indicating that every pool
contains a mixture of four samples (as shown in the Tanner graph). Also notice
that each column of $H$ is unique because the $k$th column is the binary
representation for the number $k$. This uniqueness is what makes decoding
possible. To understand this consider the following examples. The pool
variable $P_{j}$ is zero if none of the four samples it contains is positive.
The pool variable is one if one of the samples it contains is positive. (We
assume here that there is at most one sample out of the seven that is
positive.) Thus we can treat the $P_{j}$ as bits and the bit string
$(P_{3}P_{2}P_{1})$ as the binary representation of the integer number
$k=P_{1}+2P_{2}+4P_{3}$ with $0\leq k\leq 7$. As an example, examination of
the Tanner graph in Fig. 8 shows that if (only) sample 5 is positive
($S_{5}=1$) then the pool ‘bit string’ is $(P_{3}P_{2}P_{1})=(101)$ since
sample 5 is present in pool 1 and pool 3, but not pool 2. Very conveniently
$(101)$ is the binary representation of 5 and from this we deduce that it was
sample 5 that causes the unique pool pattern $(101)$. Likewise if (only)
sample 2 is positive, the pool pattern is $(010)$ because sample two is not
present in pool 1 or pool 3. Again $(010)$ is the binary representation of 2
and we know that it was sample 2 that was positive. Finally if the pool
pattern is $(000)$ we know that none of the samples were positive.

Another way to see the uniqueness can be understood with the following
example. Again suppose that the pool pattern is $(101)$. Since $P_{1}=1$ the
positive sample must be either $S_{1},S_{3},S_{5}$, or $S_{7}$ since those
samples are all present in pool 1. But $P_{2}=0$ so that means that
$S_{2},S_{3},S_{6}$ and $S_{7}$ cannot be positive since they are all present
in pool 2. The contradiction with the pool 1 result eliminates $S_{3}$ and
$S_{7}$ as possibilities, leaving only $S_{1}$ and $S_{5}$. Now $P_{3}=1$
which means that either $S_{4},S_{5},S_{6}$ or $S_{7}$ must be positive. Since
$S_{5}$ must be positive, $S_{1}$ is eliminated and we have uniquely found
that it is sample 5 that is positive.

Figure 8: Tanner graph showing how 7 samples $S$ are pooled together into 3
pools $P$. Some samples go into a single pool, some are divided into two pools
and one is divided into three pools. The pooling is arranged so that each
sample produces a unique pattern of positive results in the pools with the
binary number $(P_{3}P_{2}P_{1})$ representing the sample number for the
sample that is positive.

####  2.4.2 Example LDPC: The Hamming [7,4,3] Code

The very same mathematics above can be used to construct an LDPC for
correcting errors in a message. Suppose we encode a message in a string of
seven bits. Assume that the error probability $\epsilon$ per bit is low enough
that there is at most one error in the string of seven bits. Then as before,
there are eight possible error states. To successfully decode the error state
we must reserve three of the seven bits as parity-check bits, leaving a total
of four data bits. If we do this, then our code should be able to correct any
single bit error (including errors that occur in the parity-check bits!). We
will be constructing the $[n,k,d]=[7,4,3]$ Hamming code. In this notation $n$
is the number of physical bits, $k$ is the number of error correctable logical
(data) bits and $d$ is the code ‘distance,’ the minimum Hamming distance
between any pair of codewords, or equivalently, the minimum number of single
qubit errors needed to convert two codewords into each other. (The minimum is
taken over all pairs of codewords.) We will see below that the number of bit
flip errors that the code can correct is monotonic in $d$ but is slightly less
than $d/2$. The ‘rate’ of this code is the ratio of the number of logical
qubits to physical qubits, $r=k/n=4/7$.

Our code will use the very same matrix $H$ that appeared in the sample pooling
protocol above but we will interpret eqn (25) differently. The seven-bit block
of coded message we send will be represented by a column vector $M$ similar to
$S$ in eqn (26), but now we will allow $M$ to have more than one non-zero
entry. The allowed encoded messages are not arbitrary but rather given by the
solutions of the equation

$\left(\begin{array}[]{c}P_{1}\\\ P_{2}\\\
P_{3}\end{array}\right)=HM=\left(\begin{array}[]{c}0\\\ 0\\\
0\end{array}\right).$ (27)

Now however we interpret all quantities modulo 2. Thus

$P_{j}=\left[\sum_{k=1}^{7}H_{jk}M_{k}\right]\,\mathrm{mod}\,2.$ (28)

That is, we replace all numbers by their parity (0 for even, 1 for odd).

We have 7 physical bits and 3 parity check constraints. We therefore expect
there to be 7-3=4 logically encoded bits of information possible in the code.
This requires $2^{4}=16$ allowed codewords and therefore 16 solutions to eqn
(27). Inspection shows that setting $M$ to be any one of the three rows of $H$
gives a solution to eqn (27). A fourth solution is $M=\vec{0}$, where
$\vec{0}=(0000000)^{\mathrm{T}}$. These four solutions give us the encoded
versions of (some of) the four data bit combinations allowed in the message
plus the three parity check bits determined by those four data bits. Let us
label these four encoded messages $M_{j};j=0,1,2,3$, with $M_{0}$ being
$\vec{0}$ and $M_{j}$ for $j=1,2,3$ being the $j$ row in $H$. Four other
solutions can be found by taking linear combinations of $M_{1},M_{2},M_{3}$
(again using addition mod 2). (Codes in which linear combinations of allowed
codewords are also allowed, are called linear codes.) That gives 8 solutions.
It is straightforward to verify that the 1’s complements of these 8 solutions
gives the final 8 solutions. The easiest way to do this is to check that
$\vec{1}=(1111111)^{\mathrm{T}}$ is a solution and then use linearity to find
the remaining solutions by adding (mod 2) the solution $\vec{1}$ to the
solutions already found. (This is what taking the 1’s complement means.) Thus,
as expected, there are altogether 16 distinct allowed codewords which means
that each codeword holds $k=\log_{2}16=4$ error correctable logical bits.

Now suppose that a single bit flip error occurs during transmission so that
the encoded message is

$M_{j}\rightarrow M_{j}^{\prime}=M_{j}\oplus S$ (29)

where $S$ is a column vector with one value set to 1 (indicating the location
of the corrupted bit) and the rest being 0. Here the notation $\oplus$ means
bitwise addition mod 2. The error state is now easily decoded by simply
computing

$\left(\begin{array}[]{c}P_{1}\\\ P_{2}\\\
P_{3}\end{array}\right)=HM^{\prime}=H[M\oplus S]=HM\oplus
HS=\left(\begin{array}[]{c}0\\\ 0\\\ 0\end{array}\right)\oplus HS=HS.$ (30)

The key point here is that we have chosen codewords that have to satisfy all
the parity checks. Hence locating the error in any codeword is the same
problem as locating the error in $\vec{0}$. We can now see why locating the
one bit flip is exactly the same problem as locating the one positive SARS
COV-2 sample from the measurements on the pooled samples. Therefore we know
that our decoder will work!

Since the code distance is $d=3$, a single error can be corrected. Two errors
leave you Hamming distance 2 from the correct word and only Hamming distance 1
from some other incorrect word. The decoder makes the assumption that errors
are rare and that it is most likely that only one error occurred, not two.
Thus it corrects the error state by moving it to the nearest (in Hamming
distance) allowed codeword. This works perfectly for 1 error but fails for two
errors (for this particular code). For general code distance $d$, the number
of errors that can be corrected is $\left\lfloor(d-1)/2\right\rfloor$.

The Hamming Code is just one particular example but it gets across the basic
ideas behind low-density parity-check codes (LDPCs) and linear codes. Useful
references include the following:

blah

https://errorcorrectionzoo.org/

https://errorcorrectionzoo.org/c/binary_linear

https://errorcorrectionzoo.org/c/hamming

https://en.wikipedia.org/wiki/Linear_code

https://en.wikipedia.org/wiki/Hamming_code

https://en.wikipedia.org/wiki/Hamming(7,4)#All_codewords

###  2.5 Fault-Tolerant Classical Error Correction

The break-even point $\epsilon^{*}=\frac{1}{2}$ computed above for the
repetition codes is technically known as the ‘code-capacity’ threshold. This
is because we have implicitly assumed that we have no errors in measuring the
states of the individual bits and no errors in the device that does the
majority rule calculation and then based on that information flips the errant
bit. Thus this threshold is a mathematical property of the code itself but is
not representative of any realistic experimental situation. True fault
tolerance requires good performance not only when physical bits fail, but also
when the circuits we use for error correction are themselves imperfect and
require additional (imperfect) circuitry to correct them.333This is sometimes
referred to as the ‘Who watches the watchman?’ problem. Let us therefore
reexamine the repetition code for the case $2m+1=3$ bits and look into more
detail about how we can build circuits to correct errors using imperfect
correction operations. Such error correction circuits (ECC) employ what is
known in electrical engineering as ‘triple modular redundancy’ (TMR) [7]. This
is not an especially ‘hardware-efficient’ scheme (i.e., its implementation
brings a large hardware overhead cost), but it is relatively simple and
clearly illustrates the key principles and concepts of fault tolerance.

Let us define the _code space_ for a bundle of 3 bits (or 3 wires in a
circuit) as the states $\\{000,111\\}$ and the _correctable space_ as the
union of the code space and the space of all single-bit errors. That is, the
correctable space is the set of states with at most one error (and therefore
can be corrected by majority voting). The remaining states with 2 errors are
uncorrectable because application of majority voting leads to a logical bit
flip error. States with 3 errors are actually back in the code space but
differ from the intended state by a logical bit flip. Fig. 9 illustrates the
control theory point of view that we have a dynamical system subject to noise
which is driving it out of the code space and we are attempting to build a
controller (out of noisy components) that keeps the system within the
controllable space (i.e., the correctable space) for as long as possible. (It
is also useful to review Fig. 3.) The essential idea of fault tolerance is
that we recognize that our controller (i.e., the ECC) is itself imperfect.
However if we can arrange things so that the errors produced by the imperfect
ECC are (almost always) in the category of errors that the controller can fix
in the next round of feedback, then the escape from the controllable region
will be significantly slowed. For example, if a perfect controller can fix
only single physical bit flips, it would be bad if the imperfect version of
the controller produced two or more bit flips. It is not so bad however if the
imperfect controller produces only single bit flips because the controller
will (likely) be able to fix its own error in the next round of correction.

Figure 9: HC SVNT DRACONES (‘Here be dragons’) was the Latin inscription used
to label the unknown and dangerous border regions at the ‘edge of the world’
on ancient maps. Here we illustrate the connection between error correction
and robust control theory. The target region (code space) is a subset of the
correctable or controllable region containing (in the case of the 3-bit
repetition code) at most one error, and the surrounding dangerous
uncontrollable region of two errors. The system is fault-tolerant if the
controller (Error-Correction Circuit, ECC) can correct leading-order errors in
the codewords and if leading-order imperfections in the controller circuit
keep the system within the controllable space. If, due to higher-order errors,
the controller fails to keep the system in the controllable region, there will
be a transition back into the code space with a logical error. However this
failure rate will be higher-order in the physical hardware error rate
$\epsilon$.

Let us now move from this high-level picture to the specifics of the triple
modular redundancy. Fig. 10 illustrates two possible error correction circuits
that can correct single bit-flip errors in a 3-bit repetition code. Each
circuit uses one or more majority voting units (MAJ) whose output matches the
majority of its inputs. Both circuits are capable of correcting a single bit-
flip error in the bundle by means of majority voting. However, in circuit (a)
the MAJ unit is a single point of failure. If it fails, its output corrupts
all three bits in the repetition code, thereby producing an unrecoverable
error. (All the bits in the new state of the bundle match and so it appears
there is no error when it is examined in the next round of error correction.)
If the input to the circuit in Fig. 10(a) lies within the controllable space
(i.e., has at most one error), then the output will have zero errors with
probability $P_{0}=1-\epsilon_{\mathrm{M}}$, where $\epsilon_{\mathrm{M}}$ is
the failure probability for the MAJ unit. The output will have three errors
(i.e., a logical bit flip occurs) with probability $\epsilon_{\mathrm{M}}$.

The circuit shown in Fig. 10(b) is more complex and requires three MAJ units,
increasing the probability of one of the units failing. However this circuit
is fault-tolerant in the following important sense. If the input to the
circuit lies within the controllable space, a single failure in one of the MAJ
units, still leaves the output within the controllable space. Note that it is
useful to think of an imperfect MAJ unit as a perfect MAJ unit followed by a
stochastic unit that produces an identity operation with probability
$1-\epsilon_{\mathrm{M}}$ and a bit flip with probability
$\epsilon_{\mathrm{M}}$. Then it is easy to see that, independent of whether
there are zero or one errors on the input lines, the three perfect MAJ units
correct the error. The subsequent stochastic units produce $n$ errors with
probabilities $P_{n}$ given by

$\displaystyle P_{0}$ $\displaystyle=$
$\displaystyle(1-\epsilon_{\mathrm{M}})^{3}$ (31) $\displaystyle P_{1}$
$\displaystyle=$ $\displaystyle
3\epsilon_{\mathrm{M}}(1-\epsilon_{\mathrm{M}})^{2}$ (32) $\displaystyle
P_{2}$ $\displaystyle=$ $\displaystyle
3\epsilon_{\mathrm{M}}^{2}(1-\epsilon_{\mathrm{M}})$ (33) $\displaystyle
P_{3}$ $\displaystyle=$ $\displaystyle\epsilon_{\mathrm{M}}^{3}.$ (34)

There are two critical features of this result. First, the probability to
leave the controllable space is (for $\epsilon_{\mathrm{M}}\ll 1$) second
order in $\epsilon_{\mathrm{M}}$

$P_{\mathrm{fail}}=P_{2}+P_{3}=3\epsilon_{\mathrm{M}}^{2}(1-\epsilon_{\mathrm{M}})+\epsilon_{\mathrm{M}}^{3}\approx
3\epsilon_{\mathrm{M}}^{2}.$ (35)

Second this probability distribution for the errors is identical for the case
of the input having no errors or having a single error. It does not matter
where we are within the controllable space, so long as we are inside it. Thus
if there is at most a single error on the input, it is corrected with
probability $P_{0}\approx 1-3\epsilon_{\mathrm{M}}$ and we stay within the
controllable space with probability $P_{0}+P_{1}=1-P_{\mathrm{fail}}\approx
1-3\epsilon_{\mathrm{M}}^{2}$.

Figure 10: Two possible error correction circuits (ECC) for the 3-bit
repetition code. The ellipses mark the bundle of three lines in the code going
into and coming out of the ECC. MAJ indicates a majority voting unit whose
output is designed to match the majority of its inputs. If the input suffers
no more than a single bit flip, the MAJ unit(s) correct this error. Circuit
(a) is not fault-tolerant because it has a single point of failure–the MAJ
unit. If the MAJ unit fails, its erroneous output fans out and corrupts all
three bits in the code, producing an unrecoverable error. Circuit (b) is fault
tolerant. If one of the MAJ units fails, it corrupts only a single bit in the
3-bit code, keeping the system within the space of correctable errors and
avoiding a logical error. Circuit (c) gives the schematic symbol that will be
used to represent the fault-tolerant majority voting ECC in (b).

###  2.6 Fault-Tolerant Memory Operations

Now that we understand how to do fault-tolerant error correction for the 3-bit
repetition code. Let us apply it to the problem of error-corrected memory
operations. Suppose that a physical memory bit flips randomly in time at rate
$\kappa$. That is, the probability of a bit flip occurring in any small time
interval $dt$ is $\kappa\,dt$. Let $\rho_{0}(t),\rho_{1}(t)$ be the
probabilities that the bit is in state 0 and state 1 respectively at time $t$.
The dynamics of the continuous-time Markov process describing the bit flips is
captured by the following differential equations

$\displaystyle\frac{d\rho_{0}(t)}{dt}$ $\displaystyle=$
$\displaystyle-\kappa\rho_{0}(t)+\kappa\rho_{1}(t)$ (36)
$\displaystyle\frac{d\rho_{1}(t)}{dt}$ $\displaystyle=$
$\displaystyle+\kappa\rho_{0}(t)-\kappa\rho_{1}(t).$ (37)

If the bit starts in state 0 and $t=0$, the solution to these equations is

$\displaystyle\rho_{0}(t)$ $\displaystyle=$
$\displaystyle\frac{1}{2}\left[1+e^{-2\kappa t}\right]$ (38)
$\displaystyle\rho_{1}(t)$ $\displaystyle=$
$\displaystyle\frac{1}{2}\left[1-e^{-2\kappa t}\right].$ (39)

Suppose we pick a time $t_{0}$ at which we can define the memory error
probability $\epsilon$ (for that value of $t_{0}$. Since the bit was in state
0 initially, the error probability is simply

$\epsilon=\rho_{1}(t_{0})=\frac{1}{2}\left[1-e^{-2\kappa t_{0}}\right].$ (40)

We see that the error probability rises linearly from zero at rate $\kappa$
for short times and then saturates at 50% for long times such that $2\kappa
t_{0}\gg 1$. Because an error rate of $50\%$ is the same as random guessing,
the memory _fidelity_ is defined to be the ‘true positive’ minus the ‘false
positive’ probability

$F(t_{0})=\rho_{0}(t_{0})-\rho_{1}(t_{0})=1-2\epsilon=e^{-2\kappa t_{0}}.$
(41)

This appropriately starts at unity and decays to zero rather than $50\%$. An
appropriate measure of the memory lifetime is simply the area under the
fidelity curve

$\tau=\int_{0}^{\infty}dtF(t)=\frac{1}{2\kappa}.$ (42)

Our goal now is to try to increase the memory lifetime using the 3-bit
repetition code. From the single bit result we can now compute the probability
$P_{n}$ that $n$ errors have occurred in a 3-bit repetition code memory. The
results are of course still given by eqns (7-10). The only difference now is
that the value of $\epsilon$ depends how long the logical bit has been stored
in the memory. If our FTMAJ error-correction circuit were perfect, we would
want to apply it as frequently as practically possible to keep the 3-bit
repetition code within the controllable space. However, in the context of
fault tolerance, we are forced to recognize that the ECC itself makes errors
with probabilities given by eqns (31-34). When $\epsilon_{\mathrm{M}}$ is non-
zero, there is an optimum waiting time between error corrections. If we
correct too frequently, the imperfections of the ECC dominate. If we wait too
long between corrections, the natural error rate in the memory dominates.

To analyze this situation, let us define the time interval $t_{0}$ to be the
time delay between applications of the FTMAJ error correction circuit to fix
any errors that have occurred. One cycle of the memory ECC is illustrated in
Fig. 11. Following [7], it is convenient to assume that the FTMAJ is applied
at the beginning time $t$ and this is followed by the memory storage time
$t_{0}$ when the cycle repeats. We can then use $t_{0}$ as a variational
parameter to optimize the performance of the memory.

Let us assume that the system state at time $t$ is within the controllable
space (that is, there is at most 1 error among the three bits). We then apply
the FTMAJ circuit and obtain an initial state with an error distribution given
by eqns (31-34). The bits then idle for a time $t_{0}$ before the cycle
repeats. We want to know the probability that the system is still within the
controllable space at time $t+t_{0}$ before the cycle repeats.

Figure 11: Fault-tolerant memory operation for the 3-bit repetition code.
Shaded ellipses indicate wire bundles that represent logical bit in the
repetition code. Time increases from left to right. The dashed rectangle
outlines one cycle of error correction followed by memory waiting time $t_{0}$
before the correction cycle repeats. FTMAJ is the fault-tolerant ECC shown in
Fig. 10(b-c). The lifetime of the memory is computed by assuming that the
input at time $t$ at the beginning of the cycle (far left edge of the dashed
rectangle) lies within the controllable space (i.e., has at most one error)
and then computing the probability that the memory errors have not taken the
system out of the controllable space at time $t+t_{0}$.

Following [7], it is useful to define the reliability (success probability) of
each individual majority voter

$R_{M}=1-\epsilon_{M}.$ (43)

The reliabilty of each bit of the memory is dependent on the waiting time and
from eqn (38) is given by

$R_{0}=1-\epsilon=\frac{1}{2}\left[1+e^{-2\kappa t_{0}}\right].$ (44)

Because the majority voter and the memory bit are in ‘reliability series’ and
their failures are statistically independent, the reliability of the
combination is simply the product of the individual reliabilities [7]

$R_{M0}=R_{M}R_{0}.$ (45)

The reliability of the FT memory operation over the time interval $t_{0}$ is
the probability that the system remains within the controllable space

$R=R_{M0}^{3}+3R_{M0}^{2}(1-R_{M0}).$ (46)

The first term describes the case of zero failures and the second term
describes the case of one failure. Using eqns (43-44) and expanding eqn (46)
to second order in $\epsilon$ and $\epsilon_{M}$ yields

$R\approx 1-3(\epsilon+\epsilon_{M})^{2}.$ (47)

We can define an effective logical bit flip rate $\kappa_{\mathrm{eff}}$ via

$R=\frac{1}{2}\left[1+e^{-2\kappa_{\mathrm{eff}}t_{0}}\right]\approx
1-\kappa_{\mathrm{eff}}t_{0},$ (48)

where the approximation in the second equality will be justified later.

For small $\epsilon$ we have from eqn (40) that $\epsilon\approx\kappa t_{0}$
and hence

$\frac{\kappa_{\mathrm{eff}}}{\kappa}\approx
3(\epsilon+2\epsilon_{\mathrm{M}}+\epsilon_{\mathrm{M}}^{2}/\epsilon).$ (49)

Minimizing this with respect to $t_{0}$ is the same as minimizing this with
respect to $\epsilon$ (for the case of small $\epsilon$) and so the optimal
value of $t_{0}$ is set by

$\epsilon\approx\epsilon_{\mathrm{M}},$ (50)

as can be seen in Fig. 12. This makes sense because if
$\epsilon\ll\epsilon_{\mathrm{M}}$, we are correcting too often and errors
from the ECC are dominating. Conversely if $\epsilon\gg\epsilon_{\mathrm{M}}$,
we are waiting too long and memory errors are taking us out of the
controllable space and the ECC is unable to help. Finally, we note that if
$\epsilon_{\mathrm{M}}\ll 1$, then our approximation $\epsilon\ll 1$ is
justified _a posteriori_. Using this optimal value of $\epsilon$ (and
therefore $t_{0}$) we finally obtain our key result

$\frac{\kappa_{\mathrm{eff}}}{\kappa}\approx 12\epsilon_{\mathrm{M}}.$ (51)

Thus the error correction ‘gain’ (the factor by which the lifetime is extended
by the 3-bit encoding relative to the single bit lifetime $\tau=1/\kappa$) is
(again assuming $\epsilon_{\mathrm{M}}\ll 1$)

$G_{\mathrm{ECC}}\approx\frac{1}{12\epsilon_{\mathrm{M}}}.$ (52)

Note that because of the approximations we have made, this is actually a lower
bound on the gain. The gain takes a significant hit from the relatively large
prefactor of 12 in eqn (51). In order to achieve a gain of 10, we would need
to be able to achieve $\epsilon_{\mathrm{M}}\approx 0.0083$. Another
interesting point is that, because the circuit is fault tolerant (to first
order in $\epsilon,\epsilon_{\mathrm{M}}$) the error correction gain
approaches infinity as $\epsilon_{\mathrm{M}}\rightarrow 0$, but keeping the
optimal $\epsilon=\epsilon_{\mathrm{M}}$ in this limit requires the time delay
$t_{0}$ to scale towards zero as

$t_{0}=\frac{\epsilon_{\mathrm{M}}}{\kappa}.$ (53)

Hence even with perfect majority voters and correction operations, we
ultimately will be limited by the speed of these perfect operations.

Figure 12: Effective error rate for an error-corrected quantum memory based on
the 3-qubit repetition code. $K$ is the physical qubit bitflip rate,
$\epsilon_{\mathrm{M}}$ is the majority voting error probability and
$\epsilon$ is the memory error that grows with waiting time $t_{0}$ as given
by eqn (40). To the left of the minimum, the fidelity is limited by the errors
in the majority voting. To the right of the minimum, the fidelity is limited
by the memory errors associated with the wait time.

Finally it is important to note that while the fidelity of the logical memory
will decay more slowly than that of a single bit of physical memory, there is
a prefactor in front of the exponential that is smaller than unity because of
the cost of encoding (state preparation) and decoding which is more difficult
for 3 bits than for 1 bit. Hence even though for long times the FT memory may
have much higher fidelity, for very short times, it will be slightly worse.
This is a feature common to all error correction circuits.

All of the above results are illustrated with particular examples in Fig. 13,
which is worth studying closely. In the right panel, one clearly sees that the
$R_{M}=1.0$ curve deviates from unity only quadratically at short times,
indicating that the system can perfectly correct single errors. The
$R_{M}=0.925$ curve has a small linear slope caused by the errors in the
majority voting circuit. These errors also cause the offset from unit
reliability at zero time. However the downward slope is less than for a single
physical qubit and the two curves cross at $\kappa t_{0}\approx 0.03$. The
break-even point is reached at $\kappa t_{0}\approx 0.6$ where the physical
error probability $\epsilon$ is now large enough that the repetition code
fails to improve it.

Figure 13: Reliability $R$ of FT memory operation for one cycle of error
correction followed by memory idle for time $t_{0}$. The x-axis is
dimensionless time $\kappa t_{0}$, where $\kappa$ is the single physical flip
rate. Dot-dash curve is for perfect majority voting units with reliability
$R_{M}=1.0$. Solid curve is for the case $R_{M}=0.925$. The dashed curve is
the unencoded single physical bit memory reliability. Right-hand panel shows a
close-up of the curves for small times. Note: these plots do not include any
errors from the final readout of the memory after many correction cycles.

Assuming the desired state of a single bit can be prepared without error with
probability $1-\epsilon_{1}$, find the probability that a 3-bit repetition
code logical state can be prepared within the controllable space using the
FTMAJ circuit. Now think about how at the very end of the memory time,
decoding from the 3-bit repetition code into a single bit must be performed.
How much do the infidelities associated with the combined encoding and
decoding operations reduce the fidelity at short times relative to the use of
a single physical bit for memory? Assume the existence of a MAJ circuit that
can handle 5 inputs and has error probability $\epsilon_{\mathrm{M}}$. Repeat
the above analysis to obtain the optimal value of the error correction gain
$G_{\mathrm{ECC}}$. How does it scale with $\epsilon_{\mathrm{M}}$ and why?

###  2.7 Fault-Tolerant Classical Gate Operations

So far we have discussed only memory operations. The desired memory operation
is simply the identity–we want to get back what we put in. To do computation
we of course need completely general types of gates, not just the identity.
Let us consider the NAND gate (NOT-AND). This gate has two inputs and one
output and it is universal for classical computation–any desired Boolean
function can be represented with a circuit constructed solely of NAND gates.
Fig. 14 gives the standard schematic representation for the NAND gate and its
truth table is shown in Table 1.

Table 1: Truth table for the NAND gate. Input A | Input B | Output Q
---|---|---
0 | 0 | 1
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0
Figure 14: Standard circuit diagram symbol for the NAND gate which has two
input bits, A and B, and one output bit Q.

Let us assume that each physical NAND gate has a probability $\epsilon$ of
failing. Hence the reliability is

$R_{0}=1-\epsilon.$ (54)

This is the same as eqn (44) except that here, unlike the case of the memory,
we take $\epsilon$ to be a constant that does not change with operating time.
We take the conservative point of view that if the NAND gate fails to give the
correct answer for any of its 4 possible inputs, we consider that it always
fails (even though the output may be correct some of the time). Let us again
consider the 3-bit repetition code. The corresponding fault-tolerant logical
NAND is shown in Fig. 15.

Figure 15: Fault-tolerant logical NAND gate for the 3-bit repetition code.
Shaded ellipses indicate wire bundles that represent logical bits in the
repetition code. The dashed rectangle encloses the components whose
reliability determines overall reliability of the logical NAND.

We see that the design is similar to the memory repetition code. The wire
bundle representing logical input bit A(B) feeds each of the A(B) inputs of
the three NAND gates. The three Q output lines are sent through the same
majority voting error-correction circuit that was used for the fault-tolerant
memory circuit. We use the components enclosed within the dashed rectangle to
compute the circuit reliability. As with the memory, we define the circuit
reliability to be the probability that if the logically encoded input(s) all
lie in the controllable space, then so does the output bundle. Unlike the
memory operation, the NAND operation has two inputs which gives it more ways
to fail. The analog of eqn (45) is thus

$R_{M0}=R_{M}^{2}R_{0}.$ (55)

The difference arises because the output of the physical NAND is reliable only
if the physical NAND is reliable and both of the two majority voters that feed
it are also reliable. With this difference in the definition of $R_{M0}$, eqn
(46) for the overall reliability of the logical circuit operation remains
valid. Inserting eqn (55) into eqn (46) and expanding to second order in the
failure probabilities yields

$R\approx 1-3[2\epsilon_{M}+\epsilon]^{2}.$ (56)

The fault-tolerance gain is therefore

$G_{\mathrm{NAND}}=\frac{\epsilon}{3[2\epsilon_{M}+\epsilon]^{2}}.$ (57)

Unlike the case of the fault-tolerant memory in which $\epsilon$ was a
variational parameter, here the parameters are fixed. However, for the
particular case $\epsilon=\epsilon_{M}$, we obtain
$G_{\mathrm{NAND}}=\frac{1}{27\epsilon_{M}}$. We see that the gain is less
than for the fault-tolerant memory because of the additional hardware parts
count for the NAND gate associated with the fact that it has two inputs.

Draw schematic circuits using only NAND gates and fan in/out that realize the
following gates a) NOT b) AND c) XOR (exclusive OR) d) NOR (NOT OR) e) MUX
(direct one of many inputs to one output conditioned on the state of control
bits) f) DEMUX (direct one input to one of many outputs conditioned on the
state of control bits) g) MAJ gate for the 3-bit repetition code

###  2.8 Recursion and Fault-Tolerance Thresholds

We have now seen two related examples for the construction of fault-tolerant
circuits, one for memory and one for the universal NAND gate. These circuits
are fault-tolerant in the sense that, if the physical error probability is
below the break-even value, the logically encoded circuit has higher
reliability than the minimal physical circuit. This is true despite that the
fact that the encoded circuit contains more elements and the error-correction
component of the circuit may itself be faulty. The key question that now
arises is, ‘Can we make the error rate arbitrarily low?’ The answer is yes,
provided that the physical error rate is sufficiently small and the design is
fully fault-tolerant. One way, not necessarily the optimal way, to achieve
this goal is to recursively iterate the encoding. The zeroth level of
recursion is the physical memory bits and NAND gates. The first level error
correction is a $n$-bit repetition code scheme as described above (with
$n=2m+1$). The second level of recursion is to make a similar $n$-bit
repetition encoding using the level-1 memory bits and NAND gates (that are
themselves encoded). In theory, this recursion can be repeated as often as
needed until the error probability is below any specified level. Table 2 shows
the example of a recursively constructed memory circuit based on an $n$-bit
repetition code. We see that the hardware count grows exponentially with the
recursion level. However the logical error probability falls doubly
exponentially. The reason for this is that the error correction gain gets
larger and larger as the error rate falls with each iteration. Thus the
logical error probability falls exponentially with the hardware cost.

Table 2: Recursive fault tolerance for a memory circuit that uses $n$ physical bits to encode one logical bit that can correct a single error. The hardware cost grows exponentially with recursion level, but the error probability falls double exponentially. The error correction gain at the first recursion level is defined to be $G=1/(c_{n}\epsilon)$. The coefficient $c_{n}$ depends on the particular code. If the code can correct more than one error, the logical error rate falls even faster with recursion level.  Recursion | Hardware | Leading Error | Error Correction
---|---|---|---
Level | Overhead | Probability | Gain
0 | $1$ | $\epsilon$ | $1$
1 | $n^{1}$ | $\sim c_{n}\epsilon^{2}$ | $G$
2 | $n^{2}$ | $\sim c_{n}(c_{n}\epsilon^{2})^{2}=c_{n}^{3}\epsilon^{4}$ | $G^{3}$
3 | $n^{3}$ | $\sim c_{n}^{7}\epsilon^{8}$ | $G^{7}$
L | $n^{L}$ | $\sim(1/c_{n})(c_{n}\epsilon)^{2^{L}}$ | $G^{(2^{L}-1)}$

We see that fault tolerance is a collective phenomenon that appears only in
the ‘thermodynamic limit’ of infinite hardware resources. While this can never
be reached, the key point is that, in principle, we can approach exponentially
close to perfect operations. In practice however, it seems reasonable to argue
on physical grounds that all fault tolerance is only approximate. If we define
the effective error probability at level $j$ in the recursion to be
$\epsilon_{j}$, we have for a code that corrects errors to first order the
recursion relation

$\epsilon_{j+1}=c_{n}(\epsilon_{j})^{2},$ (58)

where $c_{n}$ is a constant that depends on the particular code. Under
recursion, the error probability falls to zero, provided that the initial
error, $\epsilon_{0}\equiv\epsilon$ is below the fault-tolerance threshold
$\epsilon^{*}=1/c_{n}$.

Since this is physics and not mathematics, we might more generally expect the
recursion relation to look something like this

$\epsilon_{j+1}=\lambda\epsilon_{j}+c_{n}(\epsilon_{j})^{2},$ (59)

where $\lambda\ll 1$ is a constant. The $\lambda$ term in this purely
phenomenological expression represents the fact that once we have pushed the
errors down to some extremely small level, we will discover that our error
model is not exactly correct and something is going wrong. By (crude) analogy
with a Landau-Ginsburg free energy expansion, we might ask what symmetry would
guarantee that $\lambda$ vanishes. In this case the ‘symmetry’ is the
assumption that all qubits have uncorrelated errors. These correlated errors
could occur for some physical reason (e.g. someone unplugged the power supply
to the computer) or because the procedure designed to correct single-bit
errors is not perfectly fault tolerant and has a small probability of causing
two-bit errors.

This symmetry may be a very good approximation but is unlikely to be exactly
true. For small but non-zero $\lambda$, the error rate will initially fall
doubly exponentially but once $\epsilon_{j}\ll\lambda\epsilon^{*}$ the
recursion relation becomes well approximated by

$\epsilon_{j+1}=\lambda\epsilon_{j}.$ (60)

Hence the flow slows from double exponential to single exponential decay. One
might think it is good news that the error rate is falling exponentially, but
don’t forget that the hardware cost is rising exponentially. Hence, the error
rate is converging only as the inverse of a polynomial (rather than
exponentially) in the hardware cost. This is what it means to be non-fault
tolerant. You can keep making the error smaller but it becomes exponentially
expensive in hardware to achieve an exponentially small error probability.

##  3 Quantum Error Correction For Two-Level Systems (Qubits)

Q: Is quantum information carried by waves or particles? A: Yes! Q: Is quantum
information analog or digital? A: Yes!

We are now ready to enter the remarkable and magic world of quantum error
correction. In the last 20 years there has been tremendous experimental
progress and the coherence times of superconducting qubits have risen more
than five orders of magnitude. Even if this progress can be continued, it is
good to recall the fundamental law of quantum information science:

‘There is no such thing as too much coherence.’

No matter how good the hardware is (and presently it is much worse than
standard classical hardware), or how good it becomes in the future, there will
always be demand for quantum computers that can run longer (execute algorithms
with greater ‘circuit depth’). The current grand challenge in the field is to
develop (nearly) fully fault-tolerant systems with dramatically enhanced
reliability, fidelity of operations and memory coherence times. Without robust
quantum error correction, large-scale quantum computation will most likely be
impossible.

In the author’s view, the fact that quantum error correction is even possible
in principle is much more amazing and counter-intuitive than the possibility
of quantum computation itself. Naively, it would seem that quantum error
correction is completely impossible. Recall that classical error correction
codes work by copying information about the data into ancillary bits. We saw
above that the simplest example of such a classical error correcting code is
the repetition code which works by simply making redundant copies of the data
and then making measurements to enforce majority voting to predict the correct
state of the data and recovery from errors. There are a number of seemingly
insurmountable difficulties in applying this approach to the quantum case.
First, the _no-cloning theorem_ [13, 14] (described below) does not allow us
to copy an unknown quantum state of a qubit onto ancilla qubits. Recall that
the classical 3-bit EEC described above used ‘fanout’ by 3x to send the same
bit state to 3 different MAJ units.

The no-cloning theorem tells us ‘There is no such thing as quantum fanout.’

Second, in order to determine if an error has occurred, we would have to make
a measurement, and the back action (state collapse) from that measurement
would itself produce random unrecoverable errors.

There is a third fundamental difference between quantum and classical gates.
Let us recall the classical NAND gate discussed above. We saw that it has two
inputs but only one output. From the one bit of output it is (in general)
impossible to deduce which of the 4 input states produced it. That is, the
NAND gate is irreversible–information is lost in going from the input to the
output. Such information loss is impossible in a quantum system because every
gate is represented by a unitary operation that maps the Hilbert space onto
itself. Every unitary $U$ has by definition an inverse $U^{-1}=U^{\dagger}$.
Hence quantum gates are reversible and information cannot be destroyed by a
gate. The only way that a quantum gate can cause loss of information is if it
entangles a system with an unobservable bath which quickly scrambles the
information and makes it effectively unrecoverable. This is precisely what
decoherence is–the bath acquiring information about the system and causing
‘measurement-induced dephasing’ [15, 16]

Charles Bennett [17] invented classical logic that is reversible. In such a
setup every gate must of course have as many wires (bits) at the output as at
the input. This is relevant to thermodynamically reversible classical
computation engines for which the only energy cost comes from erasing
information to reset the computer. This changes the entropy by $\Delta
S=k_{\mathrm{B}}\ln 2$ per bit. Irreversibly pushing this entropy into a heat
bath costs energy $T\Delta S$. The computation itself can in principle cost no
energy at all. Bennett’s analysis is interesting in the study of the trade-off
between Shannon entropy of information and thermodynamic entropy. It is also a
kind of classical precursor to reversible quantum computation.

It is important to understand another feature of the quantum case which makes
it more subtle than the classical case. In the classical case, a bit of
information $b$ can be encoded in two different voltage levels of a circuit,
say 0 and +5 volts. For example, voltage 0 can represent $b=0$ and +5 volts
can represent $b=1$. The only other possibility is the reverse: voltage zero
represents $b=1$ and +5 volts represents $b=0$. There are only two possible
encodings and they differ simply by the NOT operation. If Alice sends Bob a
message without telling him which encoding she is using, it is an easy task
for him to try to read the message and if it makes no sense, he can take the
complement of the message (i.e., apply the NOT operation to all the bits) and
successfully read the message.

Things are very different in the quantum case. The states of a qubit are
defined by the co-latitude $\theta$ and longitude $\varphi$ on the Bloch
sphere using the standard parametrization

$\displaystyle|+\hat{n}\rangle$ $\displaystyle=$
$\displaystyle\cos\left(\frac{\theta}{2}\right)|\uparrow\rangle+\sin\left(\frac{\theta}{2}\right)e^{i\varphi}|\downarrow\rangle$
(61) $\displaystyle|-\hat{n}\rangle$ $\displaystyle=$
$\displaystyle+\sin\left(\frac{\theta}{2}\right)|\uparrow\rangle-\cos\left(\frac{\theta}{2}\right)e^{i\varphi}|\downarrow\rangle.$
(62)

These basis states are the eigenstates of $\hat{n}\cdot\vec{\sigma}$, with
eigenvalues $\pm 1$ which can represent bit values $|b=0\rangle$ and
$|b=1\rangle$ respectively. Note however, that the quantization axis $\hat{n}$
is the unit vector

$\hat{n}=\left(\sin(\theta)\cos(\varphi),\sin(\theta)\sin(\varphi),\cos(\theta)\right)$
(63)

defined by two real numbers and hence requires an infinite number of bits to
specify. When Alice measures $\hat{n}\cdot\vec{\sigma}$ for a qubit prepared
in an unknown state, she obtains either $+1$ or $-1$ and thus acquires
precisely one classical bit of information, just as she would for a randomly
chosen classical bit. This upper bound on the amount of classical information
(1 bit) that can be accessed via measurement is called the _Holevo bound_ [18,
19].

Each choice of quantization axis effectively corresponds to a different
encoding of the information. Since Alice can choose an arbitrary quantization
axis, the number of possible encodings is infinite. Let us define Bob’s basis
choice to be the standard basis $|\uparrow\rangle,|\downarrow\rangle$,
corresponding to quantization axis $\hat{z}=(0,0,1)$. What happens if Alice
chooses to use the quantization axis $\hat{n}$ to encode her message? If
Alice, sends Bob the state $|+\hat{n}\rangle$, Bob will obtain the measurement
result +1 with probability

$p_{+}=\langle\uparrow|+\hat{n}\rangle\langle+\hat{n}|\uparrow\rangle=\cos^{2}\left(\frac{\theta}{2}\right),$
(64)

and measurement result -1 with probability

$p_{-}=\langle\downarrow|+\hat{n}\rangle\langle+\hat{n}|\downarrow\rangle=\sin^{2}\left(\frac{\theta}{2}\right).$
(65)

If Alice chooses $\hat{n}=+\hat{z}$ ($\theta=0$) or $\hat{n}=-\hat{z}$
($\theta=\pi$), then we essentially have the classical result. There is no
randomness and the message Bob receives will either exactly match the message
Alice sent or will be its exact complement (i.e., differ by a NOT operation).
However as the quantization axis moves away from $\pm\hat{z}$ the measurement
result will become more and more random and for the case that $\hat{n}$ lies
along the equator of the Bloch sphere, Bob’s result will be completely
uncorrelated with the message Alice intended.

######  Box 2.

No Cloning Theorem: The no-cloning theorem states that it is impossible to
make a copy of an unknown quantum state. The essential idea of the no-cloning
theorem is that in order to make a copy of an unknown quantum state, you would
have to measure it to see what the state is and then use that knowledge to
make the copy. However measurement of the state produces random back action
(state collapse) and it is not possible to fully determine the state. This is
a reflection of the fact that measurement of a qubit yields one classical bit
of information which is not enough in general to fully specify the state via
its latitude and longitude on the Bloch sphere. Of course if you have prior
knowledge, such as the fact that the state is an eigenstate of $\sigma^{x}$,
then a measurement of $\sigma^{x}$ tells you the eigenvalue and hence the
state. The measurement gives you one additional classical bit of information
which is all you need to have complete knowledge of the state. A more formal
statement of the no-cloning theorem is the following. Give an unknown state
$|\psi\rangle=\alpha|\uparrow\rangle+\beta|\downarrow\rangle$ and an ancilla
qubit initially prepared in a definite state (e.g. $|\downarrow\rangle$),
there does not exist a unitary operation $U$ that will take the initial state
$|\Phi\rangle=\left[\alpha|\uparrow\rangle+\beta|\downarrow\rangle\right]\otimes|\downarrow\rangle$
(66) to the final state $\displaystyle U|\Phi\rangle$ $\displaystyle=$
$\displaystyle\left[\alpha|\uparrow\rangle+\beta|\downarrow\rangle\right]\otimes\left[\alpha|\uparrow\rangle+\beta|\downarrow\rangle\right],$
(67) $\displaystyle=$
$\displaystyle\alpha^{2}|\uparrow\uparrow\rangle+\alpha\beta[|\uparrow\downarrow\rangle+|\downarrow\uparrow\rangle]+\beta^{2}|\downarrow\downarrow\rangle.$
unless $U$ depends on $\alpha$ and $\beta$. The proof is straightforward. The
RHS of eqn (66) is linear in $\alpha$ and $\beta$, whereas the RHS of eqn (67)
is quadratic. This is impossible unless $U$ depends on $\alpha$ and $\beta$.
For an unknown state, we do not know $\alpha$ and $\beta$ and therefore cannot
construct $U$.

######  Box 3.

Quantization Axis as Encoding Viewing the choice of quantization axis as an
encoding choice naturally leads us to the concept of intrinsic randomness in
the results of quantum measurements. How else can we reconcile the fact that
all quantum measurement results of $\hat{n}\cdot\vec{\sigma}$ are discrete
($\pm 1$) with the fact that surely the physics is continuous as $\hat{n}$ is
continuously varied between the two ‘classical’ encodings $+\hat{z}$ and
$-\hat{z}$? It is only randomness in the discrete measurement results that
allows something to be continuous–namely the probability distribution which
evolves continuously as $\hat{n}$ is varied.

A peculiar feature of quantum measurements that is important to note is that,
because the state collapses when Bob measures it, he always obtains one of the
eigenvectors of the measurement operator and has no idea if the act of
measurement caused any back action which makes the state now different from
what Alice sent. That is, if Bob makes a measurement of
$\hat{m}\cdot\vec{\sigma}$ for some arbitrary axis $\hat{m}$, he is asking the
question, ‘Does the spin lie along the $\pm\hat{m}$ direction?’ Remarkably,
the answer is always, yes! It does not matter what the initial state actually
was. (This only affects the probabilities of the different outcomes.) This
foundational notion in quantum information has been succinctly summarized by
Sasha Korotkov in the following statement:  ‘In quantum mechanics, you don’t
see what you get.
You get what you see! Of course if Alice sends Bob many copies of the same
state, Bob can obtain an estimate of $\langle\vec{\sigma}\rangle$ by making
measurements of each spin component. He can then align his decoding frame to
Alice’s encoding frame.

_No-cloning theorem prevents superluminal communication._ Bob and Alice are
far apart from each other but share a single Bell pair
$|B_{0}\rangle=\frac{1}{\sqrt{2}}\left(|\uparrow\rangle|\downarrow\rangle-|\downarrow\rangle|\uparrow\rangle\right).$
Show that if cloning an unknown state is possible, the relativistic
prohibition on superluminal communication can be violated. Hint: Let Alice
choose to measure her half of the Bell pair in either the $X$ basis or the $Z$
basis. This choice determines a one-bit message that she wishes to send. (a)
Describe in detail a protocol that Bob can employ to immediately and reliably
read this message if, and only if, cloning is possible. (b) Explain how, by
choosing an arbitrary measurement axis $\hat{n}$, Alice could send an
arbitrarily large number of bits to Bob using only a single Bell pair.
Estimate how many copies of his qubit Bob would have to clone, to reliably
receive $M$ bits from Alice.

Adaptive frame estimation Suppose that Alice and Bob want to establish a
common quantization axis for their joint experiments. Alice agrees to send Bob
$N\gg 1$ copies of the same state $|+\hat{n}\rangle$. Bob is free to make each
measurement with an arbitrary choice of quantization direction
$\hat{n}^{\prime}$. Describe qualitatively how Bob should adaptively choose
his measurement directions based on past measurement results so as to converge
as rapidly as possible on Alice’s choice of quantization axis? Suppose that
Bob has managed to find an axis $\hat{n}^{\prime}$ that is close to Alice’s:
$|\hat{n}^{\prime}-\hat{n}|=\epsilon\ll 1$. Estimate how many additional
measurements Bob will need to make to reduce the error to $\epsilon/2$. That
is, describe the asymptotic convergence of the optimal adaptive measurement
algorithm.

It turns out to be surprisingly difficult to isolate the key features that
give a quantum computer its extraordinary power. Part of the answer can be
found in its analog character–quantum superposition states have continuous
real (or complex) amplitudes. This analog character is worrisome however
because it might mean that small errors will destroy the extra power of the
computer just as they do for classical analog computers444There is a no-go
theorem for error correction in classical analog computers. The continuous
states of analog computers are all equally valid, and thus one cannot tell if
an error has shifted one of them.. Remarkably, the situation is saved by the
fact that the quantum computer also has characteristics that are digital.
Because any measurement of the state of a qubit always yields a binary result,
_measured_ quantum errors are discrete even though the errors themselves are
continuous. This is a novel situation in which state collapse is our friend.
555We will not discuss the case of autonomous error correction in which
information about errors is gradually acquired by continuous quantum non-
demolition monitoring. The fact that this is possible is also related to the
ability of QND measurements to gradually project the system onto a discrete
error state. This dual analog/digital character makes it possible to perform
quantum error correction and (in principle) obtain nearly ideal behavior from
imperfect and noisy hardware. I personally feel that this discovery by Peter
Shor in 1995 [20, 21] and by Andrew Steane in 1996 [22, 23] is even more
amazing than the concept of quantum computation (on ideal hardware) itself.
The reader may wish to consult the reviews by Raussendorf[24] and by
Gottesman[25, 26, 27].

But now an important question emerges: can we really take advantage of state
collapse and use it as a resource to help us correct errors? Isn’t quantum
error correction impossible because the act of measurement to check if there
is an error would collapse the state, destroying any possible quantum
superposition information? Also we have to be able to perform quantum error
correction on unknown states–and even in situations where a qubit does not
have its own definite state because it is entangled with other qubits during
the course of a calculation. Remarkably however, one can encode the
information in such a way that the presence of an error can be detected by
measurement, and if the code is sufficiently sophisticated, the error can be
corrected, just as in classical computation. The key will be collapsing the
state onto a definite error state without learning anything about the logical
information being stored.

We discussed above the fact that classically there are only two possible
encodings for 1 bit of information in one physical bit. Therefore, the only
classical physical error that exists is the bit flip.666Excluding the
possiblity of erasure errors in which the bit is lost or destroyed. Quantum
mechanically there are other types of errors (e.g., phase flip, energy decay,
erasure channels, etc.). Some of these errors correspond to random unitaries
applied by the environment (or accidentally by the imperfect control circuits)
to the qubit; e.g., $\sigma^{x}$ produces bit flip and $\sigma^{z}$ produces
phase flip. We can even have ‘coherent errors’ corresponding to unitary
rotations around an arbitrary axis $\hat{m}$

$U=e^{-i\frac{\theta}{2}\hat{m}\cdot\vec{\sigma}}=\cos\frac{\theta}{2}\hat{I}-i\sin\frac{\theta}{2}\hat{m}\cdot\vec{\sigma}.$
(68)

The second equality shows that this operation produces a coherent
superposition of four possibilities: no error (identity), bit flip
($\sigma^{x}$), phase flip ($\sigma^{z}$), and both
($\sigma^{y}=i\sigma^{x}\sigma^{z}$). Any error correction scheme thus has to
deal with situations where we have quantum uncertainty about whether there is
an error and what type it might be! Furthermore, some errors correspond to
irreversible, non-unitary quantum operations, e.g., energy relaxation
described by

$\sigma^{-}=\frac{1}{2}\left[\sigma^{x}-i\sigma^{y}\right].$ (69)

For a more complete discussion of quantum operations see Chap. 8 in [19].

Despite these significant additional complications and subtleties, quantum
codes have been developed [20, 21, 22, 23, 25, 27, 28, 19] (using a minimum of
5 qubits) which will correct all possible quantum errors. By concatenating
these codes to higher levels of redundancy, even small imperfections in the
error correction process itself can be corrected. Thus quantum superpositions
can in principle be made to last arbitrarily long even in an imperfect noisy
system provided the noise is sufficiently weak and is uncorrelated on
different qubits. It is this remarkable insight that makes quantum computation
possible. Many other ideas have been developed to reduce error rates. Kitaev
in particular has developed novel theoretical ideas for topologically
protected qubits (toric and surface codes) which are impervious to local
perturbations [29, 30, 31]. The surface code model for superconducting qubits
is being actively pursued, but technological advances will likely be required
to reach the break-even point [32].

Certain topological field theories contain excitations that have non-abelian
braiding statistics. That is to say, moving the defects around each other in
space moves the system from one degenerate ground state to another. In certain
cases these braiding operations can be used to perform quantum computations.
Because local perturbations in the Hamiltonian cannot mix different
topologically protected states, the hope is that such a system might realize
‘topologically protected’ qubits that avoid the necessity of quantum error
correction. This dream has not yet been realized, but much effort is being
devoted to creating quantum materials that are (hopefully) appropriate to the
task [33].

Let us begin our study of quantum error correction by considering the quantum
version of the repetition code. Recall that the minimal classical repetition
encoding step involves making two copies of the first data bit and then using
majority voting to correct for (single) bit-flip errors. Unfortunately, the
no-cloning theorem prevents replication of an unknown qubit state because
there is no unitary transformation $U$ which takes

$[\alpha|0\rangle+\beta|1\rangle]\otimes|00\rangle\longrightarrow[\alpha|0\rangle+\beta|1\rangle]^{\otimes
3}.$ (70)

Of course such a unitary _can_ be used to prepare this state if we know the
parameters $\alpha$ and $\beta$. However, as discussed in Box 2, the no-
cloning theorem prevents us from doing this for an unknown state because, from
the linearity of quantum mechanics and the fact that the RHS is a non-linear
function of the amplitudes $\alpha,\beta$, it follows that in general $U$ must
be a function of those same amplitudes. The key point for quantum error
correction is that we have to be able to correct errors in unknown states such
as occur in the middle of large computations where the bits are highly
entangled with each other. Using the quantum circuit illustrated in Fig. 16,
one can however perform the repetition code transformation:

$[\alpha|0\rangle+\beta|1\rangle]\otimes|00\rangle\longrightarrow[\alpha|000\rangle+\beta|111\rangle],$
(71)

since this is in fact a unitary transformation and the RHS is still a linear
function of $\alpha,\beta$. The qubits are entangled but the original state
has not be cloned. The encoding circuit requires no knowledge of the
amplitudes $\alpha,\beta$ and is carried out using two controlled-NOT (CNOT)
gates described in Box 4.

Just as in the classical case, these three physical qubits form a single
logical qubit. The two logical basis states are

$\displaystyle|0_{\mathrm{L}}\rangle$ $\displaystyle=$
$\displaystyle|000\rangle$ (72) $\displaystyle|1_{\mathrm{L}}\rangle$
$\displaystyle=$ $\displaystyle|111\rangle.$ (73)

The analog of the single-qubit Pauli operators for this logical qubit are
readily seen to be

$\displaystyle X_{\mathrm{L}}$ $\displaystyle=$ $\displaystyle
X_{1}X_{2}X_{3}$ $\displaystyle Y_{\mathrm{L}}$ $\displaystyle=$
$\displaystyle iX_{\mathrm{L}}Z_{\mathrm{L}}=-Y_{1}Y_{2}Y_{3}$ $\displaystyle
Z_{\mathrm{L}}$ $\displaystyle=$ $\displaystyle Z_{1}Z_{2}Z_{3},$ (74)

and they obey the usual commutation relations of the Pauli matrices.

We see that this logical encoding complicates things considerably because now
to do even a simple single logical qubit rotation we have to perform some
rather non-trivial three-qubit joint operations. It is not always easy to
achieve an effective Hamiltonian that can produce such joint operations, but
this is an essential price we must pay in order to carry out quantum error
correction. In fact, it is the very ‘unnaturalness’ of these logical
operations that makes it difficult for the environment to carry them out and
thereby destroy the stored information. We have to find a way to beat the
environment at this game. Further below we will expand on the idea that
quantum error correction is an adversarial game and discuss in more detail
what capabilities we need relative to those of the environment if we are to
win the game.

######  Box 4.

The CNOT Gate: CNOT is a two-qubit gate that flips the target qubit, if and
only if, the control qubit is in the $|1\rangle$ state:
$\mathrm{CNOT}=\left(\frac{I_{1}+Z_{1}}{2}\right)X_{2}+\left(\frac{I_{1}-Z_{1}}{2}\right)I_{2}.$
(75) The first parentheses enclose the projector onto the up state for the
control qubit (qubit 1). The second parentheses enclose the projector onto the
down state for the control qubit. Thus if qubit 1 is in
$|\uparrow\rangle=|1\rangle$, then $X_{2}$ flips the second qubit while the
remaining term vanishes. Conversely when qubit 1 is in
$|\downarrow\rangle=|0\rangle$, the coefficient of $X_{2}$ vanishes and only
the identity in the second term acts. In the classical context one can imagine
measuring the state of the control bit and then using that information to
control the flipping of the target bit. However in the quantum context, it is
crucially important to emphasize that measuring the control qubit would
collapse its state. We must therefore avoid any measurements and seek a
_unitary_ gate which works correctly when the control qubit is in $|0\rangle$
and $|1\rangle$ and even when it is in a superposition of both possibilities
$\alpha|0\rangle+\beta|1\rangle$. It is this latter situation which will allow
us to generate entanglement. When the control qubit is in a superposition
state, the CNOT gate causes the target qubit to be both flipped and not
flipped in a manner that is correlated with the state of the control qubit.
These are not ordinary classical statistical correlations (e.g. clouds are
correlated with rain), but rather special (and powerful) quantum correlations
resulting from entanglement.

Prove that the CNOT gate operation is a) Hermitian b) Squares to the Identity
c) From (a) and (b), prove that CNOT is unitary.

Figure 16: Quantum circuit to encode a single physical qubit into a logical
qubit based on the 3-qubit repetition code. The entangled state of the
logically encoded bit is created using two CNOT operations to entangle the two
ancillae with the first qubit. The circuit is ‘read’ from left to right, but
each operation corresponds to a unitary gate applied right to left. The solid
circle denotes the control qubit and the open circle denotes the target qubit
of the CNOT gate. The target qubit is flipped if and only if the control qubit
is in the 1 state. Since the control qubit is in a superposition state, the
initial product state turns into an entangled state.

It turns out that this simple code cannot correct all possible quantum errors,
but only a single type of error on at most one qubit. This fact is consistent
with the counting argument we used in the classical case. With three classical
bits we have 8 states which gives us enough ‘room’ to describe one data bit
and four possible error states (no error or one bit flip at three possible
locations). Similarly the 3-bit quantum repetition code can correct one bit
flip or one phase flip but not both. For specificity, let us take the error
operating on our system to be a single bit flip, either $X_{1},X_{2}$, or
$X_{3}$. These three together with the identity operator, $I$, constitute the
set of operators that produce the four possible error states of the system we
will be able to correctly deal with. Following the formalism developed by
Daniel Gottesman [25, 27, 24], let us define two _stabilizer_ operators

$\displaystyle S_{1}$ $\displaystyle=$ $\displaystyle Z_{1}Z_{2}$ (76)
$\displaystyle S_{2}$ $\displaystyle=$ $\displaystyle Z_{2}Z_{3}.$ (77)

These stabilizers have two nice properties: they commute with each other
(i.e., $[S_{1},S_{2}]=S_{1}S_{2}-S_{2}S_{1}=0$) and they commute with all
three of the logical qubit operators listed in eqn (74). The first property
ensures that they can both be measured simultaneously and the latter property
means that the act of measurement does _not_ destroy the quantum information
stored in any superposition of the two logical qubit states. Said another way,
the logical qubit basis states have been chosen to be $+1$ eigenstates of
$S_{1}$ and $S_{2}$. Thus every superposition of the two logical basis states
is also a $+1$ eigenstate of the two stabilizers, and hence measurement of the
stabilizer does not collapse states in the logical space in any way.

Furthermore the stabilizers each commute or anticommute with the four error
operators in such a way that we can uniquely identify what error (if any) has
occurred. Each of the four possible error states (including no error) is an
eigenstate of both stabilizers with the eigenvalues listed in Table 3.

Prove that when the important minus sign is included in the definition of the
logical operators introduced above, they obey the correct Lie algebra for
Pauli operators
$[X_{\mathrm{L}},Y_{\mathrm{L}}]=2iZ_{\mathrm{L}},\,\,[Y_{\mathrm{L}},Z_{\mathrm{L}}]=2iX_{\mathrm{L}},\,\,[Z_{\mathrm{L}},X_{\mathrm{L}}]=2iY_{\mathrm{L}}.$
(78)

Table 3: Stabilizer eigenvalues for the 4 different correctable error states of the 3-bit quantum repetition code. error | $S_{1}$ | $S_{2}$
---|---|---
$I$ | $+1$ | $+1$
$X_{1}$ | $-1$ | $+1$
$X_{2}$ | $-1$ | $-1$
$X_{3}$ | $+1$ | $-1$

Measurement of a stabilizer yields one bit of classical information and is
referred to as the error syndrome777‘Error syndrome’ can also refer to the
full collection of stabilizer measurement results.. Thus measurement of the
two stabilizers yields two bits of classical information which uniquely
identify which of the four possible error states the system is in and allows
the experimenter to correct the situation by applying the appropriate error
operator, $I,X_{1},X_{2},X_{3}$ to the system to cancel the original error.

It is instructive to compare the stabilizer measurements to the majority
voting algorithm used in the classical 3-bit repetition code. In the classical
case, the simplest way to do majority voting is to measure each bit and see if
one is different from the others. If we were to do this in the quantum case,
it would correspond to measuring $Z_{1},Z_{2},Z_{3}$ and then multiplying the
measurement results to form $S_{1}$ and $S_{2}$. This leads to disaster
because now, in addition to learning the values of $S_{1}$ and $S_{2}$, we
have learned the values of each of the qubits. Hence the quantum superposition
is destroyed. The stabilizers are two-qubit joint parity operators. They tell
us whether two qubits are in the same state without telling us what that state
is!

$\displaystyle Z_{1}Z_{2}|00\rangle=+|00\rangle$ (79) $\displaystyle
Z_{1}Z_{2}|11\rangle=+|11\rangle$ (80) $\displaystyle
Z_{1}Z_{2}|01\rangle=-|01\rangle$ (81) $\displaystyle
Z_{1}Z_{2}|10\rangle=-|10\rangle$ (82)

It is this remarkable ability to identify errors without learning the state in
which the error has occurred that permits quantum error correction for unknown
states. Once again, we see the importance of learning only the information we
need to fix the error and nothing more. Any extra information we learn causes
dangerous back action on the fragile quantum state we are trying to protect.

######  Box 5.

Measuring Joint Parity Note that coupling a measurement apparatus to compound
operators like $Z_{1}Z_{2}$ is somewhat unnatural because it requires a 3-body
interaction (two-qubits and one object in the measurement apparatus). This
operator cannot distinguish between two very different states
$|\uparrow\uparrow\rangle$ and $|\downarrow\downarrow\rangle$ (and it is
essential that we not be able distinguish between them). A coupling to
$Z_{1}+Z_{2}$ would be more natural (since it only requires two-body
interactions). While $Z_{1}+Z_{2}$ cannot distinguish between
$|\uparrow\downarrow\rangle$ and $|\downarrow\uparrow\rangle$, it does
distinguish the two states with parallel spins from each other. Similarly it
is critical that we not measure $Z_{1}$ and $Z_{2}$ separately and then
multiply the results. This would cause state collapse in a way that would
destroy the information we are trying to recover since these two operators do
not individually commute with the logical operators $X_{\mathrm{L}}$ and
$Y_{\mathrm{L}}$. From a ‘computer science’ point of view, one can measure
$Z_{1}Z_{2}$ by performing two CNOT operations on an ancilla qubit, the first
controlled by $Z_{1}$ and the second by $Z_{2}$, followed by reading out the
state of the ancilla. From the physics point of view, a measurement of
$Z_{1}Z_{2}$ can be achieved through the universal controllability of a
qubit/cavity system in the strong-dispersive regime. A protocol for multi-
qubit syndrome measurements in this regime was described theoretically by [34]
and carried out experimentally by [35]. A somewhat different scheme was used
in the first superconducting qubit quantum error correction experiment [36].

As in the classical repetition code, we are relying on the errors being rare
so that simple majority voting helps rather than hurts. If there are two bit-
flip errors, this procedure fails. Finally we note that there is a third
stabilizer

$S_{3}=Z_{1}Z_{3}=S_{1}S_{2},$ (83)

which we have not utilized because it is simply the product of the first two
stabilizers and hence does not provide any additional information. However in
building a fully fault-tolerant quantum computer one has to take into account
the possibility that the measurements of the error syndromes (stabilizer
eigenvalues) could be faulty. If one measures all three stabilizers, one can
use the redundancy of the resulting 3 classical bits of information (a
‘measurement code’) to help ameliorate the effects of stabilizer measurement
errors [37].

If the single bit-flip error probability is $\epsilon\ll 1$ and the single
syndrome measurement error probability is $\delta\ll 1$, find the optimal
(i.e., maximum likelihood) error recovery scheme for the 3-qubit quantum
repetition code.

###  3.1 Coherent Errors

We now have our first taste of the fantastic power of quantum error
correction. We have however glossed over some important details by assuming
that either an error has occurred or it hasn’t (that is, we have been assuming
we are in a definite error state). At the next level of sophistication we have
to recognize that we need to be able to handle the possibility of a quantum
superposition of an error and no error. After all, in a system described by
smoothly evolving superposition amplitudes, errors can develop continuously.
Suppose for example that the correct state of the three physical qubits is

$|\Psi_{0}\rangle=\alpha|000\rangle+\beta|111\rangle,$ (84)

and that there is some perturbation to the Hamiltonian such that after some
time there is a small rotation of the qubits. Since our code only corrects bit
flips, let us assume that this rotation is around the $x$ axis. In general,
all three qubits will develop different such errors simultaneously. For
simplicity, let us take the special case where only the second qubit is
perturbed. Then the state of the system is

$\displaystyle|\Psi\rangle$ $\displaystyle=$ $\displaystyle
e^{-i\theta_{2}X_{2}}|\Psi_{0}\rangle$ (85) $\displaystyle=$
$\displaystyle\cos(\theta_{2})|\Psi_{0}\rangle-i\sin(\theta_{2})X_{2}|\Psi_{0}\rangle.$
(86)

What happens if we apply our error correction scheme to this state? The
measurement of each stabilizer will always yield a binary result, thus
illustrating the dual digital/analog nature of quantum information processing.
With probability $P_{0}=\cos^{2}(\theta_{2})$, the measurement result will be
$S_{1}=S_{2}=+1$. In this case the state collapses back to the original ideal
one and the error is removed! Indeed, the experimenter has no idea whether
$\theta_{2}$ had ever even developed a non-zero value. All she knows is that
if there was an error, it is now gone. This is the essence of the Zeno effect
in quantum mechanics: repeated observation can stop (sufficiently smooth)
dynamical evolution. (It is also, once again, a clear illustration of
Korotkov’s maxim that in quantum mechanics ‘You get what you see.’) Rarely
however (with probability $P_{2}=\sin^{2}\theta_{2}$) the measurement result
will be $S_{1}=S_{2}=-1$ heralding the presence of an $X_{2}$ error. The
correction protocol then proceeds as originally described above. Thus error
correction still works for superpositions of no error and one error. A simple
extension of this argument shows that it works for an arbitrary superposition
of all four correctable error states (but of course fails for cases with 2 or
3 errors).

###  3.2 Errors due to entanglement with a bath

There remains however one more level of subtlety we have been ignoring. The
above discussion assumed a classical noise source modulating the Hamiltonian
parameters. However in reality, a typical source of error is that one of the
physical qubits becomes entangled with its environment. We generally have no
access to the bath degrees of freedom and so for all intents and purposes, we
can trace out the bath and work with the reduced density matrix of the logical
qubit. When we ignore the bath, the operation on the system under study
becomes non-unitary. Clearly the system is generically not in a pure state.
How can we possibly go from an impure state (containing the entropy of
entanglement with the bath) to the desired pure (zero entropy) state? Ordinary
unitary operations on the logical qubit preserve the entropy so clearly will
not work. Fortunately our error correction protocol involves applying one of
four possible unitary operations _conditioned on the outcome of the
measurement of the stabilizers_. The wave function collapse associated with
the measurement gives us just the non-unitarity we need and the error
correction protocol works even in this case. Effectively we have a Maxwell
demon which uses Shannon information entropy (from the measurement results) to
remove an equivalent amount of von Neumann entropy from the logical qubit!

To see that the protocol still works, we generalize eqn (86) to include the
bath

$|\Psi\rangle=\sqrt{1-|\epsilon|^{2}}|\Psi_{0}\rangle|\mathrm{Bath}_{0}\rangle+\epsilon
X_{2}|\Psi_{0}\rangle|\mathrm{Bath}_{2}\rangle.$ (87)

For example, the error could be caused by the second qubit having a coupling
of strength $g$ to a bath operator ${\mathcal{O}}_{2}$ of the form

$V_{2}=g\,X_{2}{\mathcal{O}}_{2},$ (88)

acting for a short time $\epsilon\hbar/g$ so that

$|\mathrm{Bath}_{2}\rangle\approx(-i){\mathcal{O}}_{2}|\mathrm{Bath}_{0}\rangle.$
(89)

Notice that once the stabilizers have been measured, then either the
experimenter obtained the result $S_{1}=S_{2}=+1$ and the state of the system
plus bath collapses to

$|\Psi\rangle=|\Psi_{0}\rangle|\mathrm{Bath}_{0}\rangle,$ (90)

or the experimenter obtained the result $S_{1}=S_{2}=-1$ and the state
collapses to

$|\Psi\rangle=X_{2}|\Psi_{0}\rangle|\mathrm{Bath}_{2}\rangle.$ (91)

Both results yield a product state in which the logical qubit is unentangled
with the bath. Hence the algorithm can simply proceed as before and will work.

Finally, there is one more twist in this plot. We have so far described a
measurement-based protocol for removing the entropy associated with errors. It
is our ability to carry out unitary operations conditioned on the result of
measurements that allows us to remove errors and hence entropy from the
system. One downside of this technique is that measurements typically require
sending signals between the room-temperature control electronics and (at least
in the case of superconducting qubits) the computer sitting at the bottom of
the dilution refrigerator. There are a number of technical challenges
associated with this, but they can be overcome with high-speed real-time FPGA
control systems [38]. There exists another route to the same goal in which
purely unitary multi-qubit operations are used to move the entropy from the
logical qubit to some ancillae, and then the ancillae are reset to the ground
state to remove the entropy. The reset operation could consist, for example,
of putting the ancillae in contact with a cold bath and allowing the qubits to
spontaneously and irreversibly decay into the bath.

Fig. 17 illustrates application of this idea to the 3-qubit repetition code.
The top three qubits are the repetition code. The first four CNOT gates
transfer the values of the two joint parities, $Z_{1}Z_{2}$ and $Z_{2}Z_{3}$
into the bottom two ancillae qubits. The remaining Toffoli (Controlled-
Controlled-NOT) gates effect the error correction. In the last step the
ancillae must be reset to the ground state before the QEC process can repeat.
The first experiment carrying out QEC in superconducting qubits used a
simplified version of this protocol that required only three qubits [36]. An
important recent experiment [39] successfully used an autonomous scheme to
correct errors in a bosonic qubit (that stores information in superpositions
of small numbers of microwave photons in a resonator).

Figure 17: Example protocol for quantum error correction without measurements.
The first part of the circuit (not shown) encodes the information in the
topmost qubit into a 3-qubit repetition code to protect it against bit-flip
errors. The second part of the circuit uses C-NOT gates to map the two error
syndromes (joint parities) $S_{1}=Z_{1}Z_{2}$ and $S_{2}=Z_{2}Z_{3}$ onto the
$q_{4}$ and $q_{5}$ ancillae qubits respectively. The CC-NOT (Toffoli) and the
NOT gates then use the syndrome information to carry out the appropriate bit-
flip operations required for error correction. The 4th and 5th ancillae qubits
must then be reset prior to reuse. Any entropy associated with errors in
qubits 1-3 is removed to the cold bath via this irreversible reset process.

Because the ancillae are in a mixed state with some probability to be in the
excited state and some to be in the ground state, the bath ends up in a mixed
state containing (or not containing) photons resulting from the decay. Thus
the entropy ends up in the bath. It is important for this process to work that
the bath be cold so that the qubits always relax to the ground state and are
never driven to the excited state. We could if we wished, measure the state of
the bath and determine which error (if any) occurred, but in this protocol, no
actions conditioned on the outcome of such a measurement are required.

From a ‘computer science’ point of view, one can measure $Z_{1}Z_{2}$ by
performing two CNOT operations on an ancilla qubit, the first controlled by
$Z_{1}$ and the second by $Z_{2}$, followed by reading out the state of the
ancilla. From the physics point of view, a measurement of $Z_{1}Z_{2}$ can be
achieved through the universal controllability of a qubit/cavity system in the
strong-dispersive regime. A protocol for multi-qubit syndrome measurements in
this regime was described theoretically by [34] and carried out experimentally
by [35]. A somewhat different scheme was used in the first superconducting
qubit quantum error correction experiment [36].

Because the unitary Hadamard gate

$H=\frac{1}{\sqrt{2}}[X+Z]$ (92)

interchanges $X$ and $Z$ operations ($HXH=Z,HZH=X$), it is straightforward to
make an analogous three-qubit quantum repetition code for phase-flip errors
(which generally occur more frequently than bit-flip errors). The 9-qubit Shor
code [20, 19] concatenates phase-flip and bit-flip repetition codes to protect
against both types of errors. It consists of a 3-qubit repetition code to
protect against phase-flip errors. Each element of this repetition code is
itself a logical qubit consisting of a 3-qubit repetition code to protect
against bit-flip errors.

The 9-qubit Shor code [20, 19] has beautiful symmetry and simplicity and
enjoys certain technical advantages in performing logical operations. However
it is not the smallest possible code that can correct any single qubit error.
Using the fact that there are four types of errors ($I,X,Y,Z$) for each qubit,
show that the smallest code that can store 1 data bit and the information on
the location and error type for up to one error requires the use of $N=5$
qubits [40, 41, 42].

Quantum error correction protocols based on logical qubits constructed from
physical qubits were first executed experimentally in 2001 in NMR [43, 42,
44], then in 2004 in trapped ions[45], in 2005 in quantum optics [46, 47], in
2012 in superconducting qubits [36, 48] and in 2014 in diamond nitrogen-
vacancy (NV) centers [49, 50, 51]. Despite considerable progress [52, 53, 54,
55, 56, 57], logical qubit lifetimes are still below the break-even point
(where carrying out the protocol extends rather than shortens the lifetime of
the quantum information) and are in the range of $10-90\%$ of the lifetime of
the best constituent physical qubit components.

Quantum error correction is extremely challenging to carry out in practice.
The first error correction protocol to reach the break-even point was achieved
by the Yale group [38]. This was done not using two-level systems as qubits
but rather by storing the quantum information in the states of a harmonic
oscillator (a superconducting microwave resonator containing superpositions of
$0,1,2,\ldots$ photons). As of the time of this writing, the record for
extending the lifetime of a logical qubit is held by the Devoret group at Yale
using the GKP bosonic code [58] to reach a factor of $\sim 2.3$ beyond the
break-even point [59]. Bosonic codes and error correction offer a number of
practical advantages and will be the focus of the second half of these notes.

###  3.3 Quantum Error Correction as an Adversarial Game

It is interesting to view quantum error correction as an adversarial game
between one player who is trying to keep a quantum computation running as long
as possible and a noise demon who is trying to destroy the fidelity of the
computation. As we saw in our discussion of classical error correction, it is
never possible to strictly beat the noise demon and have the computation to be
perfectly reliable for all time. It is however possible to extend the lifetime
(circuit depth) exponentially in the hardware overhead (double exponentially
in the concatenation level of the code). The faster and more accurate is the
error correction circuit, the more rapidly you gain from concatenation.

The quantum game is more subtle. The noise demon has considerable powers–in
fact has universal control allowing arbitrary quantum operations (unitary and
non-unitary) on each of the individual qubits. This combined with a two-qubit
entangling gate (e.g. CNOT) would be enough for the demon to carry out
universal computation. We thwart this by constraining (i.e., assuming) the
noise processes on individual qubits to be uncorrelated. On the other hand, we
are running an algorithm on the quantum computer and carrying multi-qubit gate
operations which will propagate the demon’s noise throughout the system unless
our QEC codes are properly designed.

Remarkably, we have found that QEC can be carried out using only CNOT and
Hadamard gates plus Pauli $Z$ and $X$ gates conditioned on measurements of $Z$
Pauli operators (since we can measure $X$ Pauli operators by applying $H$ and
then measuring $Z$). For the case of non-measurement based autonomous
protocols, we also require qubit reset.

The limited set of operations required for QEC is a subset of the Clifford
group (see Box 6). The Gottesman-Knill theorem (see Box 6) [60, 61] tells us
that Clifford group operations are inadequate for universal control of a
computer (despite the two-qubit entangling gate CNOT being a member of the
group). Despite this fact, Clifford operations can be used to defeat a noise
demon that can make random arbitrary continuous rotations of qubits. This is
because, as noted previously, measurement of stabilizers (that are themselves
Clifford operators) discretizes the continuous errors that develop and turns
them into discrete Pauli errors.

If the noise demon has the power to make correlated errors on the qubits, then
it has full computational power and defeating it is much more challenging, but
not impossible if the correlations are short-ranged and sufficiently weak [62,
63, 64] that this additional power granted to the demon does not let it
propagate errors too rapidly. In general, one has to use carefully designed
QEC codes that can handle multiple qubit errors and beat them back before they
spread throughout the system.

When we come to bosonic codes for continuous variable systems (harmonic
oscillators), we will find that Gaussian operators (operations that can be
carried out with time-evolution under quadratic Hamiltonians) are the analog
of the Clifford group operations, in the sense that they are usually easier to
implement, and they are non-universal and can be efficiently simulated
classically. However, unlike the qubit case where Clifford group operations
are sufficient to carry out QEC, there is a no-go theorem [65] that says that
Gaussian noise channels cannot be corrected with Gaussian operations. We will
therefore require more complex resources to carry out continuous-variable
quantum error correction. As we will see, recent dramatic experimental
progress has made those resources available within circuit QED.

######  Box 6.

Clifford Group and the Gottesman-Knill Theorem The unitary Pauli matrices
$\hat{I},X,Y,Z$ multiplied by phase factors $i^{m},m\in\\{0,1,2,3\\}$ form a
group under multiplication; e.g. $XY=iZ$. This has a natural extension to
strings of Pauli operators over $N$ qubits. The $N$-qubit Clifford group was
defined by Gottesman to be the normalizer of the $N$-qubit Pauli group, i.e.,
the set of unitaries that map (via conjugation) Pauli operators into other
Pauli operators. Thus $V$ is an element of the Clifford group if for every
element $P$ of the Pauli group, $P^{\prime}=VPV^{\dagger}$ is also an element
of the Pauli group. Clearly $e^{i\varphi}V$ is Clifford if $V$ is Clifford,
but such global phase factors can generally be ignored. Clearly the Clifford
group contains the Pauli group but is larger. The entire Clifford group
(including the Pauli subgroup) can be generated from only three unitary gates:
controlled-NOT, Hadamard (H) and S where $\displaystyle\mathrm{CNOT}_{12}$
$\displaystyle=$
$\displaystyle\frac{\hat{I}_{1}+Z_{1}}{2}\hat{I}_{2}+\frac{\hat{I}_{1}-Z_{1}}{2}X_{2},$
(93) $\displaystyle\mathrm{H}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}[X+Z]=\frac{1}{\sqrt{2}}\left(\begin{array}[]{cc}+1&+1\\\
+1,&-1\end{array}\right),$ (96) $\displaystyle S$ $\displaystyle=$
$\displaystyle\sqrt{Z}=\left(\begin{array}[]{cc}+1&0\\\
0,&+i\end{array}\right).$ (99) This small gate set is very powerful and can
generate highly entangled $N$-qubit states. Hadamard creates superpositions
$\mathrm{H}|0\rangle=|+\rangle\equiv\frac{1}{\sqrt{2}}[|0\rangle+|1\rangle])$
(100) and, when combined with a CNOT, can create entangled Bell states
$\mathrm{CNOT}_{12}\mathrm{H_{1}}|00\rangle=\frac{1}{\sqrt{2}}[|00\rangle+|11\rangle].$
(101) The Gottesman-Knill theorem tells us that surprisingly, despite the fact
that the Clifford gates can generate huge entangled superposition states of
$N$ qubits starting from a single state $|0\rangle^{\otimes N}$, such circuits
are easy to simulate classically [61]. To see why this is so, notice that the
starting state can be uniquely defined by its stabilizers (the list of
operators for which it is a $+1$ eigenstate). For example the stabilizers of
$|0\rangle^{\otimes N}$ are simply $\\{Z_{1},Z_{2},\ldots,Z_{N}\\}$. Applying
H to qubit $m$ produces a superposition state, but we do not need to keep
track of the superposition amplitudes, we need only update the list of
stabilizers by making the replacement $Z_{m}\rightarrow X_{m}$. Similarly, if
we use H and CNOT to create a Bell pair from qubits $\ell,m$, we replace the
pair of stabilizers
$\\{Z_{\ell},Z_{m}\\}\rightarrow\\{X_{\ell}X_{m},Z_{\ell}Z_{m}\\}$. Single-
qubit stabilizers are replaced by two-qubit stabilizers, but the total number
of stabilizers remains the same. We can efficiently simulate Clifford circuits
by simply updating the list of Cliffords. It can also be shown that we can
efficiently compute the expectation values of any physical observables by
examining the updated list of stabilizers. Because they can be efficiently
simulated classically, Clifford circuits plus computational basis measurements
do not capture the full power of universal quantum computers. One hint as to
why this is so, is that you cannot use such circuits to detect violations of
the Bell inequalities. The latter requires being able to rotate detectors (or
equivalently states) by $\pi/4$, not simply $\pi/2$. For this we need a non-
Clifford gate such as the $T$ gate
$T=\sqrt{S}\equiv\left(\begin{array}[]{cc}1&0\\\
0,&e^{i\pi/4}\end{array}\right)$ (102) which is needed to create what is
colloquially known in the field as ‘magic.’ Once we include the $T$ gate, the
group size becomes infinite and we can create an arbitrarily good
approximation to any state in the $N$-qubit Hilbert space [19].

##  4 Quantum Operations and Kraus Representations of Error Channels

As mentioned previously, errors that entangle portions of the quantum computer
with its environment appear to be non-unitary quantum operations if we do not