PHYS483: Quantum information processing—Lecture Notes

Henning Schomerus, Lancaster University

Contents |αψi = α|ψi. Furthermore, any two states |ψi, |χi

can be combined into new states by a forming a
I. Quantum mechanics 1 superposition |ψ + χi = |ψi + |χi.
A. States 1 The vector space is a Hilbert space, i.e., it is
B. Operators 2
C. Dynamics 2 equipped with a scalar product that associates a
D. Measurements 2 complex number hψ|χi to any pair of states |ψi, |χi.
E. Density matrix 3 The scalar product is positive definite, hψ|ψi > 0 for
F. Two-state systems 3 |ψi 6= 0|ψi, and fulfills hψ|χi = hχ|ψi∗ . Furthermore,
G. Composite systems and entanglement 4 it is linear in the second argument, but conjugate
H. Bell inequalities 5
linear in the first argument, i.e., hψ|αχi = αhψ|χi,
II. Classical computation 6 hαψ|χi = α∗ hψ|χi, hψ+ϕ|χi = hψ|χi+hϕ|χi, hψ|ϕ+χi =
A. von Neumann architecture 6 hψ|ϕi + hψ|χi.
B. Binary representation of information 6 Formally, the scalar product can be interpreted
C. Quantifying classical information 6
D. Operations 7
as a product hψ| · |χi between the vectors |χi and
E. Unary and binary gates 7 the entities hψ|, which form the dual vector space.
F. Reversible gates 7 They represent the left states in the scalar product
G. Complexity of computational tasks 8 and therefore are also conjugate linear: hαψ +βχ| =
H. Practical issues 8 α∗ hψ| + β ∗ hχ|. The particular notation introduced
III. Quantum information representation and here is the so-called Dirac notation. In this no-
manipulation 8 tation, a dual vector is also called a bra, and an
A. Quantum bits 8 ordinary vector is called a ket, alluding to the fact
B. Quantum information 9 that in the scalar product hψ|χi they form a bracket
C. Quantum gates as unitary operations 10
D. Single-qubit gates 10
(bra-ket). p
E. Two-qubit gates 11 We call ||ψ|| = hψ|ψi the length of the vector
F. Composition of gates 11 |ψi. A vector with hψ|ψi = 1 is called normalized.
G. Function gates 12 The procedure of passing from a vector |ψi to the
normalized vector |ψi/||ψ|| is called normalization.
IV. Quantum Communication 13
A. Superdense coding 13 Two states |ψi, |χi fulfilling hψ|χi = 0 are said to be
B. Quantum teleportation 14 orthogonal to each other.
C. Secure communication 14 A basis is a collection of vectors |ni, n =
1, 2, 3, . . . , N such that any vector can be written as
V. Quantum Computation 15 PN
A. Adding numbers 15 a superposition |ψi = n=1 ψn |ni, where the com-
B. Deutsch-Josza algorithm 15 plex coefficients ψn are unique. The coefficients ψn
C. Grover’s quantum search algorithm 16 give a representation of the state, and can be writ-
D. Quantum Fourier transformation 18 ten as a column vector
E. Applications: From phase estimation to prime  
factorization 18 ψ1
 ψ2 
VI. Error correction and practical issues 20
ψ =  . .
 
A. Errors and error correction 20  .. 
B. Practical requirements 21
ψN
VII. Further reading 23
The corresponding dual vector is written as a row
∗
vector ψ † = (ψ1∗ , ψ2∗ , . . . , ψN ). While there are many
I. QUANTUM MECHANICS possible bases, in which the same vector is rep-
resented by different coefficients, the number N of
A. States basis states required to obtain all vectors is always
the same, and is called the dimension of the vector
The state of a quantum system is described by a space (N may be ∞).
vector |ψi. These vectors form a complex linear vec- An orthogonal basis fulfills hn|mi = 0 for any
tor space, which entails, in particular, the follow- n 6= m. If furthermore hn|ni = 1 for all n one
ing properties: Any state |ψi can be scaled by any speaks of an orthonormal basis. In such a basis,
complex number α, i.e., we can form new states the coefficients representing a state are given by
 2

ψn = hn|ψi,
P and the scalar product takes the form Two important types of operators are hermitian
hψ|χi = n ψn∗ χn = ψ † χ. operators Ĥ and unitary operators Û . For any two
states |ψi, |χi, hermitian operator fulfill hψ|Ĥχi =
hĤψ|χi, while unitary operators fulfill hÛ ψ|Û χi =
B. Operators hψ|χi. This entails Ĥ = Ĥ † and Û † = Û −1 . Both
classes of operators have the nice property that
An operator  converts any state |ψi into an- their sets of normalized eigenvectors form an or-
other state |Âψi = Â|ψi. Linear operators fulfill thonormal basis. For hermitian operators, the
Â(α|ψi + β|χi) = αÂ|ψi + β Â|χi. Operators can be eigenvalues an are real, while for unitary operators
added according to the rule (Â+B̂)|ψi = Â|ψi+B̂|ψi, they fulfill |an | = 1.
and multiplied according to the rule (B̂ Â)|ψi =
B̂(Â|ψi).
C. Dynamics
In an orthonormal basis, linear operators are
represented by N × N -dimensional square matri-
The time evolution of quantum states is gov-
ces
erned by the Schrödinger equation
 
A11 A12 . . . A1N d
 A21 A22 . . . A2N  i~ |ψ(t)i = Ĥ(t)|ψ(t)i,
A= .

.. . . .. 
 dt
 .. . . . 
AN 1 AN 2 . . . AN N where Ĥ is a hermitian operator called Hamilto-
nian. Given an initial state |ψ(t0 )i, the general
solution can be written as |ψ(t)i = Û (t, t0 )|ψ(t0 )i,
with coefficients Anm = hn|Âmi ≡ hn|Â|mi. They
then act on vectors by matrix multiplication, i.e., where Û (t, t0 ) is a unitary operator called the
time evolution operator. This operator fulfills the
|ϕi = Â|ψi is represented by coefficients ϕn = d
P Schrödinger equation i~ dt Û (t, t0 ) = Ĥ(t)Û (t, t0 )
m Anm ψm . In a given representation, the operator
addition and multiplication rules translate to the with initial condition Û (t0 , t0 ) = I.ˆ
usual prescriptions of matrix addition and multi- In the particular case Ĥ = const(t) of a time-
plication. independent Hamiltonian, the time evolution op-
erator takes the form
PIn Dirac notation, operators are written as  =
nm Anm |nihm|, and the action of an operator is
obtained from the multiplication rule hm| · |ψi = Û (t, t0 ) = exp[−i(t − t0 )Ĥ/~],
hm|ψi.
where the exponential function of an operator is
The action of an operator is particularly simple P∞
defined as exp  = k=0 Âk /k! . Using the eigen-
in its eigenrepresentation, defined by a basis ful- P
filling Â|ni = an |ni. The numbers an are called representation Ĥ = n En |nihn| of the Hamiltonian
P
eigenvalues, and the vectors |ni are called eigen- we can write Û (t, t0 ) = n exp[−i(t − t0 )En /~]|nihn|.
vectors. If the eigenvectors form an orthonormal
basis, the matrix Anm is diagonal, Anm = 0 if n 6= m
and Ann = an . In Dirac notation, the operator can D. Measurements
P
then be written as  = n an |nihn|.
Measurements deliver information about observ-
A particularly simple operator is the identity
ˆ which leaves all states unchanged, able properties (observables) of quantum systems.
operator I, Quantum mechanics associates to each observable
ˆ
I|ψi = |ψi. Every state is therefore an eigenstate A a hermitian operator Â. The eigenvalues an of Â
of I,ˆ with eigenvalue 1. Consequently, in any or- are the (only) possible outcomes of the experiment.
thonormal basis this operator takes the same form Each outcome occurs with a probability given by
Iˆ = n |nihn|. Representations are simply obtained
P

by multiplying out the identities |ψi = I|ψi ˆ and P (A = an ) = |hn|ψi|2 = hψ|nihn|ψi = hψ|Ên |ψi,
ˆ ˆ
 = I ÂI. For a fixed orthonormal P basis, it is where |ni is the eigenvector associated with an ,
useful to decompose the identity Iˆ = Ên as the
and Ên = |nihn| is the associated projection opera-
sum of projection operators Ên = |nihn|, which fulfill P
tor. The average hAiψ = n Pn an of the outcome of
Ên Êm =0 if n 6= m, and Ên2 = Ên . many identical experiments, known as the expec-
For all operators we can define an adjoint op- tation value of A, can be calculated directly from
erator † by hψ|† χi = hÂψ|χi. For many opera- the quantum state using hAiψ = hψ|Â|ψi.
tors, we can also define an inverse operator Â−1 by In the simplest case, a measurement with out-
ÂÂ−1 = Iˆ come an transforms the state of the system into the
 3

eigenstate |ni. In general, however, the values of Here, tr B̂ denotes the trace of an operator, which
one observable alone do not suffice to uniquely de- in any given orthonormal basis can be calculated
termine the state of a system. Instead, a complete
P P
as tr B̂ = n hn|B̂ni = n Bnn .
description requires to measure a larger set Â(l) Normalization of states carries over to the prop-
of simultaneous observables. Such observables erty tr ρ̂ = 1. Moreover, the density matrix is her-
commute with each other, [Â(l) , Â(m) ] = 0, where mitian and positive definite. P This entails that in its
[Â, B̂] = ÂB̂ − B̂ Â is the commutator. This property eigenrepresentation ρ̂ = n pn |nihn|, all eigenval-
guarantees that one can find a joint eigenbasis, ues arePnonnegative, pn > 0; they also sum up to
given by states |ψa i = |a(1) , a(2) , a(3) , . . .i fulfilling unity, n pn = 1. (The nonvanishing eigenvalues
Â(l) |ψa i = a(l) |ψa i. These states are only fully spec- pn are only identical to the values Pi if the states
ified by knowledge of the eigenvalues a(l) of the full |ψi i used to define the ensemble are orthogonal to
set of simultaneous observables, which we here each other.)
grouped into a vector a with components al = a(l) . For a pure ensemble, pn = 1 for one state, while
In this situation, a specific measurement out- all the other pm = 0 (m 6= n). In this case, ρ̂ =
(l) |nihn| = Ên is a projection operator, and therefore
come an for a single observable Â(l) delivers only
fulfills ρ̂2 = ρ̂. It follows that for a pure state 2
P 2tr ρ̂ =
incomplete information about the quantum sys- 2
1. For a mixed state, however tr ρ̂ = n pn < 1.
tem. In order to describe the effect of such a
The quantity P = tr ρ̂2 , also known as the pu-
measurement, let us introduce the projection op-
(l) P rity, therefore easily distinguishes pure from mixed
erator Ên = (l) |ψa ihψa | onto all states that
l a =a
n states. The maximally mixed state is described by
(l)
share the given eigenvalue an . A measurement the density matrix ρ̂ = N1 Iˆ (where N is the Hilbert
(l) space dimension), and has purity P = 1/N .
with outcome an then occurs with probability
Pn = hψ|Ên |ψi, and transforms the quantum state In a given representation, the density matrix of a
into the (not yet normalized) state |χn i = Ên |ψi. pure state |ψi can be obtained from ρ = ψψ † , which
The normalized post-measurement state is given is useful for specific calculations.
p The time evolution of the density matrix follows
by |ψn i = 1/Pn |χn i. Since the other observables
from the Schrödinger equation, and is given by
remain undetermined, such an incomplete mea- d i
surement does not force the system into a unique dt ρ̂ = ~ [ρ̂, Ĥ]. The general solution can be written
final state. as ρ̂(t) = Û (t, t0 )ρ̂(t0 )Û † (t, t0 ), where Û is the unitary
time evolution operator defined in section I.C.

E. Density matrix
F. Two-state systems
An ensemble is a large collection of physically
identical quantum systems, which however can be Given an orthonormal basis |0i, |1i of a two-state
system, each state |ψi = α|0i  is represented
 + β|1i
described by different states. When all the states
are identical the ensemble is said to be pure, other- α
by a two-component vector . Each hermitian
wise it is mixed. In general, we specify β
Pthat a frac-
tion Pi of states is in state |ψi i, where i Pi = 1 and operator Ĥ = a0 Iˆ + ax X̂ + ay Ŷ + az Ẑ can be formed
hψi |ψi i = 1. Starting from a pure ensemble with all from four elementary operators with matrix repre-
members in state |ψi, such a mixed ensemble is sentation
       
obtained, e.g., by measurement of an observable, 1 0 0 1 0 −i 1 0
I= ,X= ,Y = ,Z= .
with Pi and |ψi i obtained as described in the pre- 0 1 1 0 i 0 0 −1
vious section. In the ensemble, expectation values The matrices X, Y and Z are the Pauli matrices,
P
are defined by hAi = i Pi hψi |Â|ψi i. most familiar from the description of the spin of
By construction, a mixed ensemble cannot be an electron where they are often denoted as σx , σy
described by a single quantum state. However, it and σz , respectively. They fulfill X 2 = Y 2 = Z 2 = I,
is possible to define a statistical operator ρ̂, most XY = −Y X = iZ, Y Z = −ZY = iX, ZX = −XZ =
commonly known as the density matrix, which al- iY .
lows to calculate all expectation values in a given It is useful to characterize the state of a two-state
mixed ensemble. This operator is given by system by the vector of expectation values

P~ = (hXi, hY i, hZi),
X
ρ̂ = Pi |ψi ihψi |,
i
which is known as the polarization vector. For a
and the expectation values are obtained by normalized pure state |ψi = α|0i + β|1i,

hAiρ = tr (Âρ̂). P~ = (2 Re α∗ β, 2 Imα∗ β, |α|2 − |β|2 )

 4

is of unit length, and therefore lies on a sphere 1. When a state is separable, |ψi = |ϕi|χi, the out-
called the Bloch sphere. In terms of spherical polar come of such measurements only depends on |ϕi.
coordinates on this sphere, However, when the system is entangled, measure-
ments on one subsystem cannot be described by
|ψi = cos(θ/2)|0i + eiφ sin(θ/2)|1i. a single state of that system. It is then still pos-
The azimuthal angle φ = arg α∗ β of this vector is sible to describe these measurements by a density
also known as the phase of the state. For a mixed matrix
state, |P~ | < 1 so that the vector lies within the X
ρ̂1 = hnk|ψihψ|mki|nihm|,
sphere. In terms of these expectation values, the
nmk
density matrix can be written as
1
 
1 known as the reduced density matrix. This means
1 + Pz Px − iPy
ρ= = (I+Px X+Py Y +Pz Z). that all expectation values can be computed ac-
2 P x + iPy 1 − P z 2
cording to hAi = tr Âρ̂1 . Analogously, measure-
The purity of this density matrix is given by P = ments of the second subsystem P are described by a
1 ~ 2 reduced density matrix ρ̂2 = nkl hnk|ψihψ|nli|kihl|.
2 (1 + |P | ).
If a state |ψi is separable, the reduced density ma-
trices are pure, i.e., tr ρ̂21 = tr ρ̂22 = 1. If the state
G. Composite systems and entanglement |ψi is entangled, the reduced density matrices are
both mixed, i.e., tr ρ̂21 = tr ρ̂22 < 1.
An important example where simultaneous ob- Reduced density matrices can also be defined
servables occur are composite systems (say, a sys- when the composite system is already in a mixed
tem composed of parts 1 and 2), where incom- state, described by a density matrix ρ̂. They are
plete information can be acquired by measuring then given by
an observable of a subsystem (say, part 1). Start- X X
ing from an orthonormal basis |ni (n = 1, . . . , N1 ) ρ̂1 = hnk|ρ̂|mki|nihm|, ρ2 = hnk|ρ̂|nli|kihl|.
for system 1 and |miP (m = 1, . . . , N2 ) for system 2, nmk nkl
the joint state |ψi = nm ψnm |nmi of the compos-
ite system can be written by using combined ba- These constructions are also called partial trace,
sis states |nmi, sometimes also written as |ni|mi and then written as ρ̂1 = tr2 ρ̂, ρ̂2 = tr1 ρ̂. This
or |ni ⊗ |mi. The corresponding dual basis vec- designation becomes clear when one considers the
tors are denoted by hnm|. The Hilbert space di- block form
mension of the composite system is therefore given  (2) (2) 
ρ11 ρ12 · · ·
by N = N1 N2 . General operators can be written as  (2) (2)
ρ =  ρ21 ρ22 · · · 
P 
 = nmkl Ank,ml |nkihml|. Operators acting on sub-
.. .. . .
system 1 will be denoted by Â1 , and have represen- . . .
P (1)
tation Â1 = nmk Anm |nkihmk|. Operators acting
on subsystem 2 will be denoted by Â2 , and have of the density matrix in the composite basis, where
(2)
P (2)
representation Â2 = nkl Akl |nkihnl|. This results ρnm are N2 × N2 -dimensional matrices. Then,
in the convenient block matrix form  (2) (2) 
 (1) tr ρ11 tr ρ12 · · ·
(1)   (2)  (2) (2)
A11 I A12 I · · · A 0 ···
X
ρ1 =  tr ρ21 tr ρ22 · · ·  , ρ2 = ρ(2)
nn .
 
 (1) (1) (2)
···  .. ..
A1 =  A21 I A22 I · · ·  , A2 =  0 A , ..
  n
. . .. . . .
.. .. .. . .
. . . . . .
In this more general case of a composite system
where I is the N2 × N2 -dimensional identity ma- with a mixed density matrix, the purities of both
trix. Here, the basis states are ordered as reduced density matrices do not need to be identi-
|1, 1i, |1, 2i, . . . , |1, N2 i, |2, 1i, |2, 2i, . . .. cal, and cannot simply be used to decide whether
Sometimes, the state of a composite system can the system is entangled or not; this is discussed in
still be written as the product |ϕi|χi of two states, more detail below.
where |ϕi describes system 1 and |χi describes sys- As an (important) example, consider the compo-
tem 2. Such states are called separable. This sition of two two-state systems. Pure states can be
requires that the coefficients can be written as written as |ψi = α|00i + β|01i + γ|10i + δ|11i, and are
ψnm = ϕn χm . States that are not separable are normalized if |α|2 + |β|2 + |γ|2 + |δ|2 = 1. The entan-
called entangled. glement of such a state is often characterized by
In order to determine whether states are separa- the concurrence
ble or entangled, it is useful to consider measure-
ments of observables of one subsystem, say system C = 2|αδ − βγ|,
 5

which fulfills 0 ≤ C ≤ 1. For separable states, is only the case of two composite two-level sys-
C = 0, i.e., the concurrences vanishes. For en- tems, for which entanglement measures can be
tangled states, C > 0. States with C = 1 are called computed efficiently from the 4 × 4 dimensional
maximally entangled. Examples of maximally en- density matrix ρ of the composite system in the
tangled states are the four Bell states standard basis. In order to obtain the concur-
rence, one needs to compute the four eigenvalues
λi of the matrix ρ(Y1 Y2 )ρ∗ (Y1 Y2 ), where Y1 and Y2
r
1
|β00 i = (|00i + |11i), are the Y Pauli matrix acting on subsystem 1 and
2
r 2, respectively. When the eigenvalues are ordered
1
|β01 i = (|01i + |10i), such that λ1 > λ2 >√λ3 > √ λ4 , the√ concurrence
√ is
2 given as C = max (0, λ1 − λ2 − λ3 P − λ4 ). The
r
1 entanglement of formation E = mindec i Pi E(ψi ) is
|β10 i = (|00i − |11i), generalized by minimizing the averaged pure-state
2
r entanglement ofPformation over all possible decom-
1
|β11 i = (|01i − |10i). positions ρ̂ = i Pi |ψi ihψi | of the density matrix
2 (where the states |ψi i do not need to be orthogonal).
For the pure state given above, the full density Remarkably, both entanglement measures √ are re-
matrix lated by the general formula E = h( 21 + 12 1 − C 2 ),
where h(x) = −x log2 x − (1 − x) log2 (1 − x).
α
 
 
β ∗ ∗ ∗ ∗ A B
ρ =   (α , β , γ , δ ) = H. Bell inequalities
γ C D
δ
Entanglement is physically significant because
can be conveniently written in block form, where it results in correlations that cannot be described
A, B, C, and D are 2 × 2-dimensional matrices. The by classical probabilities. These correlations can
reduced density matrix be uncovered by statistical tests, known as Bell in-
  equalities. The most transparent inequality is the
tr A tr B CHSH inequality due to Clauser, Horn, Shimony,
ρ1 = and Holt. Consider the composition of two two-
tr C tr D
state systems; to be explicit, think of the spins
can then be obtained by taking traces of the of two electrons with basis states |0i = | ↑i and
blocks, which here results in |1i = |↓i. On each spin we carry out two different
experiments, described by observables Â1 , Â01 , B̂2 ,
|α| + |β|2 αγ ∗ + βδ ∗
 2 
ρ1 = . and B̂20 , which measure whether the spin points
γα∗ + δβ ∗ |γ|2 + |δ|2 into a particular direction. To the outcome of each
experiment we designate the value 1 or −1, depend-
Similarly, ing on whether the spin is found to be aligned par-
allel or antiparallel to the measurement direction,
|α|2 + |γ|2 αβ ∗ + γδ ∗
 
ρ2 = A + D = . respectively. Now consider the expectation value
βα∗ + δγ ∗ |β|2 + |δ|2
of
The purity of these reduced density matrices is re- F̂ = (Â1 + Â01 )B̂2 − (Â1 − Â01 )B̂20 .
lated to the concurrence,
Classically, for each combination of outcomes,
tr ρ̂21 = tr ρ̂22 2
= 1 − C /2. F is either 2 or −2, and therefore on average
hF i ≤ 2, which is the CHSH inequality. Quantum-
Furthermore, we have the identity det ρ̂1 = C 2 /4. mechanically, the average is obtained by an ex-
0
For composite systems in a pure state, the pectation
p value. Let us choose p Â1 = Z, Â1 = X,
0
reduced density matrix also delivers the en- B̂2 = − 1/2(X + Z), and B̂2 = 1/2(Z − X), so that
√
tanglement of formation E = −tr (ρ̂1 log2 ρ̂1 ) = F̂ = − 2(X1 X2 +Z1 Z2 ), which is represented by the
−tr (ρ̂2 log2 ρ̂2 ), which is identical to the von Neu- matrix
mann entropy of the mixed states of the subsys- 
1 0 0 1

tems (see section III.B). √  0 −1 1 0 
In their form discussed above, these measures of F = − 2 .
0 1 −1 0 
entanglement only apply to pure states of a com- 1 0 0 1
posite system. Entanglement measures for multi-
component systems with a mixed density matrix Furthermore,p assume that the system is in the Bell
are an active field of research. Well understood state |β11 i = 1/2(|↑↓i − |↓↑i), represented by the
 6

vector Consider a register with N binary digits (bits).


0
 This can represent N = 2N different numbers.
p  1  When we add a register with M bits, this increases
ψ= 1/2  . to N M = 2N +M (where M = 2M ). However, since
−1 
0 physically we simply added components, the data
√ capacity of the composed register is far more con-
We then find hF̂ i = ψ † F ψ = 2 2, which violates veniently specified by describing it as an (N + M )-
the CHSH inequality. The reason are quantum- bit register. The desired additive measure of stor-
mechanical correlations that arise as a conse- age capacity is therefore N = log2 N , M = log2 N ,
quence of the entanglement of the Bell state. where log2 is the logarithm with base 2 (such that
Quantum computation taps into this resource to log2 2 = 1). This is nothing else but the entropy
achieve tasks that are classically impossible.
N
X
II. CLASSICAL COMPUTATION S=− pn log2 pn
n=1
A. von Neumann architecture
of a system with N microstates, which are all occu-
Computers store and process information. All pied with equal probability pn = N −1 . The entropy
common computers feature a combination of in- S defined here is known as the Shannon entropy,
put and output devices, memory, processing unit, and differs from the entropy in thermodynamics
and control unit, which is known as the von Neu- only by a multiplicative factor kB ln 2 (where kB is
mann architecture. This architecture is designed Boltzmann’s constant).
to store and process information flexibly by means
of programs, which encode a sequence of instruc- The entropy is a convenient measure of informa-
tions. These features also apply to the proposed tion content particularly when one considers that
quantum computers. The difference between both we usually do not make best use of the register
types of devices consists in how they represent and states. E.g., the ASCII code only has 7 bits (the
manipulate the information. In this section, we de- 8th bit in a byte can therefore be used to check
scribe how this works for classical computers. for errors, i.e., it adds redundancy). [Link].r, in
[Link] we. only use. printable. [Link], and some.
[Link] (such as e.) occur far more. [Link]
B. Binary representation of information than [Link] (such as q). The different register
states then no longer occur with equal probability
Classical computers represent information digi- pn , which is exploited by compression algorithms
PN −1
tally as binary numbers x = n=0 xn 2n , where the (frequent symbols—or combinations of symbols—
binary digits (or bits) xn can take values 0 or 1, are abbreviated by short bit sequences). The en-
and can be presented as a sequence xN −1 . . . x2 x1 x0 tropy tells us to how many bits a data stream can
(sometimes, leading zeros are dropped). For exam- be ideal compressed—this is Shannon’s noiseless
ple, the binary number 11 is identical to the dec- channel coding theorem.
imal number 3, and the binary number 100010 is The entropy can also be used to quantify the
identical to the decimal number 34. These num- degradation of the information content due to
bers can be interpreted in many different ways — transmission errors. Assuming that bits are
they may represent a letter (as in the ASCII code), flipped randomly with error rate p, the capacity of
or the color or brightness of a pixel on a computer a channel reduces by a factor C = 1 + p log2 p + (1 −
monitor. They therefore represent various types of p) log2 (1 − p). Another source of errors are lost data
information. packages—this is especially prevalent in wireless
transmission and satellite communication.
C. Quantifying classical information Errors can be detected and corrected by adding
additional bits—naively, by repeatedly sending the
From a physical perspective, the transmission of same data stream; more effectively, by adding
large amounts of binary data results in an irreg- other means of redundancy, such as using the
ular sequence of discrete events which is best de- 8th bit in the ASCII code for a parity check. For-
scribed in the language of statistical mechanics. tunately, Shannon’s noisy channel coding theorem
This provides means to precisely quantify the in- ensures the existence of error-correction codes
formation content of the data, as well as its degra- which make the error probability arbitrarily small
dation due to imperfections in transmission and (see section VI.A for examples of error-correction
manipulation processes. schemes).
 7

E. Unary and binary gates

There are four unary gates (i.e., gates that take

one bit as input): The identity gate Id x = x which
lets the bit intact, the not gate NOT x = 1 − x which
inverts (or flips) the value of the bit, and the two re-
set gates ALWAYS TRUE x = 1, ALWAYS FALSE x =
0, for which the output is independent of the input.
There are 16 binary gates (gates that take two
bits as input), of which the following ones are par-
ticularly noteworthy: The and gate x AND y = xy,
which outputs TRUE only if both x and y are TRUE,
the or gate x OR y = x + y − xy, which outputs TRUE
if at least one of x and y are TRUE, the exclusive-
or gate x XOR y = x + y − 2xy ≡ x ⊕ y (where ⊕
denotes addition modulo 2), and the negated-and
gate x NAND y = 1 − xy. These gates are not inde-
pendent; for example, we can write
x XOR y = (x OR y) AND (x NAND y).
Indeed, it is possible to write all unary and binary
operations only using the NAND gate (e.g., NOT x =
x NAND x). Together with the capability to replicate
(or copy) information, this is sufficient to achieve
all possible operations.
FIG. 1 Circuit representation of elementary classical
gates.
F. Reversible gates

With exception of Id and NOT, the gates dis-

cussed so far are irreversible: knowing only the
D. Operations output, it is impossible to infer the input. It is
noteworthy that one can also implement classi-
cal computations with a set of reversible gates,
Consider a memory unit which contains N bits.
which have additional output channels that al-
Such a unit is also called a register. The specified
low to infer the input values (see Fig. 2). The
register can represent N = 2N binary numbers,
most important example is the controlled-not gate
which range from 0 to 2N − 1. In order to carry
x CNOT y = (x, x XOR y), which flips the target
out computations, we need facilities to transform
any of these numbers into any other number in the
same range. It turns our that this is possible with
a sequence of operations which act either only on
one bit (called unary operations), or on a pair of
bits (called binary operations). Furthermore, be-
cause bits only take two possible values, these op-
erations can be formulated using the concepts of
Boolean logic, the mathematical discipline of TRUE
and FALSE statements, which are conventionally
associated with the values 1 and 0, respectively.

Each type of logical operation is called a gate.

Graphically, a gate is represented by a box, with
horizontal lines to the left representing input chan-
nels and horizontal lines to the right representing
output channels (see Fig. 1). The operation of the
gate is specified by a truth table, which specifies
the output values as function of the input values.
Below, for compactness, we express these outputs FIG. 2 Circuit representation of some reversible classi-
as simple algebraic functions of the inputs. cal gates.
 8

bit y if the control bit x is TRUE, and otherwise H. Practical issues

leaves the target bit unchanged (the first bit there-
fore controls whether the second bit is flipped or In order to build a workable computer, the the-
not). Because x CNOT 0 = (x, x), this gate can oretical concepts presented here must be com-
be used to copy information. Another example plemented by practical considerations. Available
is the SWAP gate x SWAP y = (y, x), which inter- computers preferably use irreversible logics based
changes the values of the two bits. As indicated on gates which dissipate energy, not least because
in Fig. 2, this can be implemented by combining this provides a much larger degree of stability than
three CNOT gates. The figure also shows two im- reversible gates. For efficiency, they use more than
portant reversible three-bit gate, the Toffoli gate a minimally required set of gates, which reduces
(also known as CCNOT gate), which transforms the number of necessary operations. Furthermore,
(x, y, z) → (x, y, (x AND y) XOR z), and the Fredkin they use many different methods to physically rep-
gate (also known as controlled swap), which trans- resent the bits, e.g., by means of different voltages
forms (0, y, z) → (0, y, z) and (1, y, z) → (0, z, y). A in components of the electronic circuit in the pro-
universal set of reversible gates needs to include cessing unit, or by different magnetization of do-
at least one of these three-bit gates. mains in hard-disk storage units. Over the years,
the feature size of electronic circuits has shrunken
steadily, which slowly but surely brings them close
to the threshold where they become susceptible to
quantum effects. As we will see in the next sec-
tions (III-V), these effects are not necessarily un-
welcome, as they can be exploited to achieve tasks
that are hard to achieve with classical computers,
G. Complexity of computational tasks which leads to the concept of a quantum computer.
However, quantum computation is far more error
prone than classical computation, which brings
We will later see that quantum computers can about a new range of practical issues that are dis-
achieve certain tasks in a relatively small number cussed in section VI.B.
of operations. In order to gauge their efficiency,
it is useful to distinguish computational tasks by
their complexity. Let us assume we want to operate III. QUANTUM INFORMATION REPRESENTATION AND
on registers with N bits, and denote the number of MANIPULATION
operations required for specific a task (such as the
multiplication of two numbers with N/2 bits) by T . This section introduces quantum bits (qubits)
If T grows as a polynomial with N , the task is rela- and quantum gates, and discusses some underly-
tively simple; this pertains, e.g., to arithmetic and ing concepts such as quantum parallelism (arising
algebraic tasks, such as matrix inversion. Prob- from the superposition principle), entanglement as
lems of this kind are grouped into complexity class a resource for computation, and the no-cloning
P . Many problems, however, are much harder, and theorem. These concepts clearly distinguish quan-
require a number of operations T which grows ex- tum computers from classical computers, and are
ponentially with N . A notable example is the fac- the reason why (in principle) the former are far
torization of large numbers into prime factors, for more powerful than the latter.
which no algorithm in P is known. For this specific
problem it is, however, easy to verify that the solu-
tion (once found) is correct — this simply requires A. Quantum bits
multiplication of the factors, which is a task in P .
Such problems are called nondeterministic polyno- Quantum computers encode information into
mial, and grouped in class NP. Interestingly, there the quantum state of a composite system, con-
are problems to which all other NP problems can sisting of a number of two-state systems known
be reduced; such problems are called NP-complete, as qubits (quantum bits). Taken individually, each
and a large number of them is known. What is qubit can be described by a quantum state |ψi =
not known is the answer to the fundamental ques- α|0i+β|1i. The basis states |0i and |1i form the com-
tion whether the complexity classes P and NP ac- putational basis, and represent classical bits with
tually differ — one cannot exclude that there is values 0 and 1. What is special about qubits is that
an undiscovered algorithm which solves an NP- their general state |ψi can also be a superposition
complete problem in a polynomial number of op- of 0 and 1, which cannot be realized by a classical
erations. If such an algorithm would be identified, bit. In this case, |α|2 and |β|2 give the probabilities
it could be used to solve all NP problems much to find 0 or 1 in a measurement of the qubit in the
more efficiently than presently possible. computational basis [associated with the operator
 9

(I − Z)/2], which on the Bloch sphere depend on with parts A and B: SA , SB < SAB . Quantum me-
the polar angle θ. Measurements of other observ- chanically, the entropy S(ρ̂A ) of a subsystem fol-
ables (like X or Y ) give access to other combina- lows by inserting the reduced density matrix, and
tions of α and β, which also depend on the phase can be larger than the entropy of a composed sys-
φ = arg(α∗ β) of the qubit. However, since measure- tem. This is in particular the case when an entan-
ments change the state of the qubit, it is not pos- gled systems is in a pure state. The entropy of the
sible to directly encode information into the com- composite system vanishes, but it is finite for each
plex numbers α and β; this distinguishes quantum of its parts because the reduced density matrices
computers from analog computers. are mixed (see section I.G). For composite systems
An N -bit quantum register contains N qubits. that are already in a mixed state, this leads to the
The state of the register is then formed using the more sophisticated measures of entanglement also
N = 2N computational basis states |xN −1 . . . x1 x0 i, mentioned in that section.
where xN −1 . . . x1 x0 is the binary code of numbers In terms of data compression, the von Neumann
PN −1
x = n=0 xn 2n ranging from 0 to 2N − 1. Here, we entropy plays a similar role as the Shannon en-
will not drop leading zeros (thus, for N = 4 we write tropy: it describes how many qubits are necessary
0010 for the decimal number 2) because they de- to transmit a certain amount of (quantum) infor-
scribe the state of some of the qubits. Sometimes, mation (this can be quantified via Schumacher’s
we denote these states by the corresponding num- noiseless channel coding theorem).
bers x; e.g., for a 4-bit register, |3i ≡ |0011i and How much information can be transmitted via
|0i ≡ |0000i. a single qubit? Assume that the incoming data
Just as the individual qubits, the register may be stream is composed of states described by a den-
brought into a superposition of the computational sity matrix ρ̂i , which can be assumed to be mixed
basis states. For instance, one can form the state because of limitations in the preparation or trans-
N
2X −1
mission of the qubit states. It then can be shown
−N/2
X
−N/2 that the maximally accessible amount of infor-
|Ψi ≡ 2 |xN −1 . . . x1 x0 i = 2 |xi,
mation I perPqubit cannot exceed a certain P limit,
xn =0,1 x=0
I < S(ρ̂) − n Pi S(ρ̂i ) ≡ χ, where ρ̂ = i Pi ρ̂i ,
which contains all binary numbers between 0 and and Pi is the fraction of qubits with density matrix
2N − 1 at the same time. All these numbers there- ρ̂i . This inequality is known as the Holevo bound,
fore can be manipulated at once by a single physi- and the quantity χ is the Holevo information. Note
cal operation on the register. This feature is some- that when all ρ̂i are pure, S(ρ̂i ) = 0, and therefore
times described as quantum parallelism, and will χ = S(ρ̂).
be frequently exploited in Section V. The Holevo bound implies that a single qubit
The state |Ψi given above is still separable, and cannot transmit more than one bit of classical in-
therefore can be obtained by operating on the in- formation. However, as embodied by the super-
dividual qubits. The real power of the register is dense coding scheme discussed next, if sender
unleashed when one considers that the qubits in and receiver possess as an additional resource a
the register can also be entangled, which can be number of shared entangled qubits, it is possi-
achieved by manipulating pairs of qubits. We next ble to transmit two bits of classical information
explore how entanglement is linked to information via a single (entangled) qubit. Indeed, the appli-
and then have a look at a number of basic quan- cations below show that entanglement is a useful,
tum operations on the register which enable to ex- non-classical resource for communication. En-
ploit these special features of qubits. tanglement can also be used for error correction
schemes, as will be discussed in section VI.A.
In order to quantify entanglement of a (many-
B. Quantum information body) state |ψi, it is useful to determine how many
maximally entangled Bell pairs one could gener-
Quantum mechanically, the entropy of a system ate (by local operations within each subsystem, and
with density matrix ρ̂ is given by the von Neumann classical communication) if one had many copies of
entropy the state |ψi. This results in the entanglement of
S(ρ̂) = −tr ρ̂ log2 ρ̂. formation, which is an additive measure of entan-
glement, and therefore constitutes the appropriate
This is identical to the Shannon entropy, with the counterpart to the information measure provided
probabilities pn replaced by the eigenvalues of ρ̂. by the Shannon entropy. As discussed in Sec. I.G,
It follows that a system in a pure state has von- for pure states the entanglement of formation sim-
Neumann entropy S = 0. ply reduces to the von Neumann entropy of the
Classically, the entropy of a subsystem A is al- subsystems. This applies even for the case that
ways less than the entropy of a composite system each subsystem has more than two possible quan-
 10

tum states. For mixed states, however, explicit ex-

pressions are only known for some special cases,
such as for two qubit-systems (see again Sec. I.G).

C. Quantum gates as unitary operations

Since solutions of the Schrödinger equation can

be written as a time-dependent unitary transfor-
mation of the initial state, all quantum gates are
represented by unitary operators, |ψf i = Û |ψi i,
where |ψi i is the initial state of the register, and |ψf i
is the final state of the register. Computational al-
gorithms furthermore complement these gates by
mechanisms to prepare the register in an initial
state, as well as mechanisms to read out the final
state (which can be achieved by measurements).
In the remainder of this section we concentrate on
the unitary quantum gates.
First, a general observation: Because unitary
operators can be inverted, all quantum gates are
reversible: the input state can be inferred from
|ψi i = Û † |ψf i. This also entails an important con-
straint onto quantum operations: The no-cloning
theorem, according to which it is impossible to FIG. 3 Circuit representation of elementary quantum
transfer the state of a control qubit to a target gates.
qubit without erasing the state of the control qubit.
Even though the quantum gates are reversible,
a universal set of gates can be formed using only unary gates ALWAYS TRUE/FALSE do not have
unary and binary gates; no three-bit gates are re- unary quantum analogues.
quired. On the other hand, we need to consider Clearly, I and X do not exhaust all possible
a larger variety of such gates — besides achieving transformations of a qubit. On the Bloch sphere,
the classical logical tasks, we need gates that put X represents a rotation by 180◦ about the x axis,
qubits into non-classical superpositions of 0 and while I leaves the state untouched. However, we
1, and gates that establish entanglement between can also operate, e.g., with Z, which flips the phase
the qubits. Fortunately, this can be achieved by of the qubit (this advances the azimuthal angle φ
using a finite number of unary gates, plus a single by π). The most general single-qubit transforma-
binary gate. Circuit representations of these gates tions correspond to rotations of the Bloch sphere
are shown in Fig. 3. about an arbitrary axis n̂ = (nx , ny , nz ), by an arbi-
trary angle ϕ. Such general rotations can be writ-
ten as
D. Single-qubit gates
Rn̂ (ϕ) = exp[−iϕ(nx X + ny Y + nz Z)/2]
All unary (single-qubit) gates can be represented
as 2×2-dimensional unitary matrices, = cos(ϕ/2)I − i sin(ϕ/2)(nx X + ny Y + nz Z).
  which act on
α
the two component vector ψ = representing Fortunately, not all rotations are independent:
β
the state |ψi = α|0i + β|1i. Just as hermitian ma- E.g., following from the identity Y = iXZ, Y (a 180◦
trices, these can be generated by combining the rotation about the y axis) can be obtained by com-
Pauli matrices X, Y , and Z, as well as the identity bining X and Z (rotations about the x and z axis,
matrix I. The latter leaves the state of the qubit respectively).
unchanged, and therefore constitutes the quan- An example of a set of elementary rotations
tum analogue to the identity gate Id. Furthermore, which can be combined to generate all possible ro-
considering that X|0i = |1i and X|1i = |0i, X repre- tations is given by the following three gates: the
sents the analogue to the classical NOT gate. For a π/8-gate
general state |ψi = α|0i + β|1i of the qubit, applica-  
tion of this gate yields X|ψi = β|0i + α|1i. Because 1 0 √
T = ,
they are irreversible, the two remaining classical 0 (i + 1)/ 2
 11

the phase gate In block notation,

 the matrix C12 can also be
I 0

1 0
 written as C12 = . Replacing X by an ar-
0 X
S = T2 = ,
0 i bitrary unary gate U delivers controlled versions
of each unary gate, denoted as controlled-U gates.
and the Hadamard gate An example is the controlled phase flip, which is
  obtained for U = Z. Another notable two-qubit gate
1 1 1 1 is the quantum version of the SWAP gate, which is
H = √ (X + Z) = √ .
2 2 1 −1 represented by the matrix
Here, T and S generate 45◦ and 90◦ rotations about 
1 0 0 0

the z axis, respectively, while H generates a 180◦ 0 0 1 0
rotation about the (1, 0, 1) direction. Starting, say, S12 =  .
0 1 0 0
from the initial state |0i, these operations can be 0 0 0 1
used to bring the qubit into any general superpo-
sition state α|0i + β|1i.
Below, we will also often use ϕ-rotation gates F. Composition of gates
about the Y axis, which have the form
  In order to manipulate the information in the
cos(ϕ/2) − sin(ϕ/2)
R(ϕ) = cos(ϕ/2)I−i sin(ϕ/2)Y = .register, we need to apply unary and binary gates
sin(ϕ/2) cos(ϕ/2)
to the individual qubits. Unary gates U operating
on the nth qubit in the register will be denoted by
Un . Analogously, binary gates acting on qubits n
E. Two-qubit gates
and m will be denoted by Unm . Here, order of the
indices matters — in general, Unm 6= Umn . In par-
General two-qubit gates are represented by 4 ×
ticular, for controlled gates, we will use the first
4-dimensional unitary matrices, which act on the
index to refer to the control qubit, while the sec-
four component vector
ond index refers to the target qubit.
 
α We can now combine unary and binary gates to
β achieve arbitrary operations on the register. For
ψ=  instance, the realization of the SWAP gate in terms
γ
δ of three CNOT gates, already known from the clas-
sical case, takes the form S12 = C12 C21 C12 .
representing a state |ψi = α|00i+β|01i+γ|10i+δ|11i. The combination of quantum gates allows to
The most important gate is the quantum version achieve tasks that would require more compli-
of the controlled-not gate CNOT, which negates the cated gates if done classically. Some examples
target qubit if the control qubit is in |1i, and leaves are listed in Fig. 4. Consider the operation U =
the target unchanged if the control qubit is in |0i; H1 H2 C12 H1 H2 , which first applies Hadamard gates
the control qubit always remains in its initial state. to the two qubits, then acts with a CNOT gate,
If qubit 1 is the control bit, this is represented by
the matrix
1 0 0 0
 
0 1 0 0
C12 =  ;
0 0 0 1
0 0 1 0

for reversed roles we have

1 0 0 0
 
0 0 0 1
C21 =  .
0 0 1 0
0 1 0 0

Starting, say, from

p p the separable state |ψi =
p 1/2(|0i+|1i)|0i = 1/2(|00i+|10i), we find C12 |ψi =
1/2(|00i + |11i), i.e., one of the Bell states. The FIG. 4 Quantum circuits which implement the exchange
CNOT gate can therefore be used to entangle two of control and target bit, as well as the realization of a
qubits. controlled-controlled-U gate.
 12

qubit register with initial state |0i = |000 . . . 000i into

X
U |ψi = 2−N/2 |xN −1 . . . x2 x1 x0 i ≡ |Ψi,
xn =0,1

the superposition of all states of the computational

basis, which represents all binary numbers in the
range of the register. (c) When the initial state is
another computation basis state |xi, the action of
a Hadamard gate on an individual qubit can be
written as
|0i + (−1)xn |1i 1 X
H|xn i = √ =√ (−1)xn zn |zn i.
2 2 zn =0,1
FIG. 5 Reduction of the Toffoli gate to unary and binary
quantum gates. In analogy to Fig. 2, the Fredkin gate is
obtained by two additional CNOT operations.
When we act with Hadamard gates on all the
qubits in the register, we obtain the expression
Y X
and finally again applies Hadamard gates. Using Hn |xi = 2−N/2 (−1)x·z |zi,
matrix multiplications, we find that for all initial n z
states, this is equivalent to U = C21 . Therefore,
where x · z = x0 z0 + x1 z1 + . . . + xN −1 zN −1 denotes
amazingly, decorating the gate with single-qubit
the bitwise product of x and z.
operations allows to exchange the roles of the con-
trol and target qubits. Classically, this exchange
would require additional binary gates. Similarly,
we can obtain classical three-bit gates by combi- G. Function gates
nation of unary and binary gates. For instance,
as shown in the figure, a general controlled- An important class of gates encountered in the
controlled-U gate can be obtained by controlled-V following applications implement functions f : x →
gates, where V 2 = U . f (x), where x is an N -bit input, and f (x) is an M -
The Toffoli gate (controlled-controlled-not, CC- bit output (see Fig. 7). In general, such functions
NOT), which classically has to be introduced sepa- are not invertible. The bottom panel of the figure
rately to achieve unversal reversible computations, shows a strategy to implement reversible versions
follows for V = (1 − i)(I + iX)/2, such that V 2 = X. of these functions: add auxiliary output channels
Just as in the classical case, the Fredkin gate which keep track of the input, and auxiliary input
is obtained by two additional CNOT operations, channels which when set to 0 gives the desired out-
F123 = C32 T123 C32 . Up to a phase factor, the Toffoli come. (The auxiliary channels are called ancillas,
gate can also be achieved by using Y -rotations, and also feature prominently in error correction,
section VI.A.) This can be achieved using the bit-
eiϑ T123 = R3 (−π/4)C13 R3 (−π/4)C23 R3 (π/4)C13 R3 (π/4) wise XOR operation

(see Fig. 5). Here, the phase factor ϑ changes the f ⊕ y = fM . . . f1 f0 ⊕ yM . . . y1 y0

sign of the basis state |100i, but leaves all other = (fM ⊕ yM ) . . . (f1 ⊕ y1 )(f0 ⊕ y0 ).
basis states unchanged.
Figure 6 shows combinations of gates which
serve as frequent components of the quantum al-
gorithms discussed in the following section. (a)
The gate C12 H1 entangles qubits 1 and 2 that are
initially prepared in computational basis states:
p
C12 H1 |00i = 1/2(|00i + |11i) ≡ |β00 i,
p
C12 H1 |01i = 1/2(|01i + |10i) ≡ |β01 i,
p
C12 H1 |10i = 1/2(|00i − |11i) ≡ |β10 i,
p
C12 H1 |11i = 1/2(|01i − |10i) ≡ |β11 i.
Q
(b) Application of U = n Hn (i.e., acting with the FIG. 6 Creating entanglement and superpositions using
Hadamard gate on each qubit) transforms an N - Hadamard gates.
 13

Functions with single-bit output are called

Boolean functions (because their output can be in-
terpreted as 0=FALSE, 1=TRUE). If the input x is
also only a single bit, there are exactly four func-
tion gates, which can be implemented in terms of
elementary gates as shown in Fig. 8. If the auxil-
iary input state is set to |yi = |0i, they implement
reversible versions of the four classical unary op-
erators discussed in section II.E.

IV. QUANTUM COMMUNICATION

FIG. 8 (a) Boolean function gates with single-bit input.

Quantum communication concerns the transfer
(b) Implementation in terms of elementary gates.
of information, and uses entanglement as a re-
source in order to achieve classically impossible
tasks. In the sections below we discuss three ex-
amples: the transmission of two bits of informa-
tion by sending a single qubit (superdense cod-
ing); the transfer of the quantum state of one qubit
to another qubit at a distant location (teleporta-
tion), and the generation of unbreakable encryp-
tion codes for secure communication. All these
tasks can be achieved with current technology.

A. Superdense coding

Superdense coding is a simple scheme which

illustrates how entanglement can facilitate the
transmission of information. The scheme is il-
lustrated in Fig. 9(a). Here and in the follow-
ing, double-lines indicate classical transmission or
control channels. By convention, sender and re- FIG. 9 Circuit representations of (a) superdense cod-
ceiver are designated the names Alice and Bob (or ing and (b) quantum teleportation. Double-lines denote
classical communication channels. The dashed box in-
A and B), respectively. Initially, Alice and Bob each
dicates operations carried out by the sender (Alice); all
are in possession of a single qubit. In the dis- other operations are carried out by the receiver (Bob).
tant past (say), they met and prepared these qubits
in the entangled Bell state |β00 i = √12 (|00i + |11i).
Now, Alice and Bob are located at distant loca- necessary—e.g., A&B could have received their en-
tions (this handed down tale is intended to con- tangled qubits from an appropriate, distantly lo-
vey how the scheme will exceed classical expecta- cated two-photon source). Alice can now decide
tions, but most of these embellishments are not whether she wishes to carry out two operations on
her qubit—first a NOT operation (X), then a phase
flip (Z). This results in the state Z1M1 X1M2 |β00 i,
where Mi = 1 if the operation was carried out,
and Mi = 0 if it was not carried out. Consider-
ing each case separately, we see that this trans-
forms the state into |βM1 M2 i, i.e., into one of the
four Bell states. Alice then sends her qubit—just
the single one—to Bob, who can use a CNOT and
a Hadamard gate to transform the qubit pair back
to the computational basis states, H1 C12 |βM1 M2 i =
|M1 M2 i [this is just the inverse of the entanglement
procedure in Fig. 6(a)]. A measurement of both
qubits in the computational basis therefore allows
him to infer both M1 and M2 . In effect, using en-
FIG. 7 Function gates. tanglement as a resource, Alice has sent Bob two
 14

bits of information. the two bits M1 and M2 that Alice is sending. How-
ever, Eve could still send an arbitrary qubit to Bob,
which would result in him obtaining random val-
B. Quantum teleportation ues for M1 and M2 , as well. This can be detected
when Alice and Bob compare parts of their mes-
Quantum teleportation addresses the task of sages.
transferring the unknown and arbitrary state of Quantum key distribution.—To make communi-
one qubit to another, possibly distant qubit. Be- cation both secure and reliable, one can generate
cause of the no-cloning theorem, this requires to an encryption key shared by Alice and Bob. The
erase all information from the first qubit. How this message can then be sent classically using a sim-
can be achieved is shown in Fig. 9(b). Before con- ple encryption technique (e.g., by using XOR oper-
sidering the details, note the striking similarities to ations, which flips bits according to a shared se-
the circuit for superdense coding—most notably, quence of 0’s and 1’s.).
Alice and Bob again share a Bell pair, and the set (a) The BB84 protocol (due to Bennett and Bras-
of operations they carry out is just interchanged. sard) is a protocol that does not require entangle-
However, Alice is now also in possession of an ex- ment. Alice prepares qubits randomly in one of the
tra qubit, whose state |ψi = α|0i + β|1i she wishes following four states:
to transmit to Bob. She does not know the com- p
plex amplitudes α and β, and she cannot send the |0i, |1i, |±i = 1/2(|0i ± |1i).
qubit itself, but she can send classical informa-
tion along a transmission line (e.g., by phone). To These are the eigenstates of the Z and X opera-
succeed, she first entangles the two qubits in her tor. Alice makes sure that she uses a prepara-
possession by applying a CNOT and a Hadamard tion method that tells her which state she has pre-
gate. This results in the three-qubit state pared (e.g., this can be done by making random X
and Z measurements on qubits with density ma-
1 ˆ She then sends these qubits to Bob,
trix ρ̂ = 12 I).
H1 C12 |ψi|β00 i = [α(|0i + |1i)(|00i + |11i)
2 who, for each qubit, randomly measures either X
+β(|0i − |1i)(|10i + |01i)] or Z. When he measures X and the qubit was in
1 state |+i, he will obtain 1 with certainty, while if
= [|00i(α|0i + β|1i) + |01i(α|1i + β|0i) the state was |−i, he will obtain −1 with certainty.
2
+|10i(α|0i − β|1i) + |11i(α|1i − β|0i)], If the state was |0i or |1i, he will obtain 1 or −1
with 50% probability. In contrast, if Bob measures
where the second line follows by reordering the Z, he will obtain certain measurement outcomes 1
terms. Next she measures the two qubits in her and −1 for the states |0i and |1i, respectively, while
possession, and sends her measurement results the states |±i result in random measurement out-
M1 and M2 to Bob. This allows him to infer how comes. Bob now tells Alice which measurements
the post-measurement state |ϕi of his qubit is re- he did for each qubit, and Alice tells Bob which
lated to the former state |ψi: measurements she did to prepare the qubits (they
only communicate the type of measurement, X or
M1 M2 = 00 ⇒ |ϕi = α|0i + β|1i = |ψi Z, but not their outcomes). For these instances,
M1 M2 = 01 ⇒ |ϕi = α|1i + β|0i = X|ψi their measurements will have resulted in the same
M1 M2 = 10 ⇒ |ϕi = α|0i − β|1i = Z|ψi outcome, which results in a shared sequence of 0’s
M1 M2 = 11 ⇒ |ϕi = α|1i − β|0i = XZ|ψi. and 1’s that they can use for encryption.
An eavesdropper listening to the key distribution
Therefore, in order to obtain |ψi, he simply applies would be able to make measurements on an inter-
Z M1 X M2 to his qubit. cepted qubit, but without knowledge of its prepa-
ration would not be able to then forward the same
qubit to Bob. This would introduce errors into the
C. Secure communication key (at a rate of 25%), which can be detected when
Alice and Bob compare small samples of their key
Secure quantum communication schemes rely (this part of the key would then be discarded).
on the no-cloning theorem, which prevents an The BB84 scheme is simple and robust, and has
eavesdropper (’Eve’) to listen to a communication been implemented experimentally using photons,
line (either, Eve will not acquire any information, for which the four states correspond to polariza-
or her actions can be detected). tions in x̂, ŷ, x̂ + ŷ, and x̂ − ŷ direction. (E.g., in
Secure communication based on superdense cod- 1997, the scheme was demonstrated using a 23
ing.—If Eve would intercept the qubit sent between km long transmission line beneath Lake Geneva.)
Alice and Bob, she only possesses a qubit with re- (b) The EPR protocol (due to Eckert) uses pair-
ˆ which is independent on
duced density matrix 12 I, wise entangled qubits prepared in the Bell state
 15

reversible logics, we first illustrate this by an ex-

ample, namely, the computation of the sum of two
numbers.
Binary numbers can be added just like decimal
numbers, bit by bit starting with the least signifi-
cant bits, and carrying over bits to the next more
significant bit. Consider, e.g., the sum 3 + 3, which
in binary code is 11 + 11. We first add the last
two bits (i.e., the least significant bits), resulting
in 1 + 1 = 10. The last bit of this (0) is the last bit
of our result, while the first bit needs to be carried
over. We then add the first two bits, and to this the
carry-on bit, giving 1+1+1 = 11. This again results
in a carry-on bit. There are no further bits to be
processed, so the carry-on bit becomes the most
significant bit. Our result now has three bits: 110,
which is the same as 4 + 2 + 0 = 6.
In classical computers, these operations can be
carried out using half-adder and full-adder com-
ponents, which can be realized using elementary
binary gates as shown in Fig. 10. Because of
x + y = y + x, the depicted circuit is irreversible
FIG. 10 Classical adder circuits.
(furthermore, it requires to copy bits). Figure
11 shows that the same operations can also be
achieved quantum mechanically using a combina-
q
1
|β00 i = 2 (|00i + |11i), which can also be written tion of reversible CNOT and CCNOT gates, which
q
as |β00 i = 12 (|+i|+i + |−i|−i). Alice and Bob make generate additional outputs that can be used to re-
verse the calculation.
random measurements of X and Z on each of their
Adding two numbers with reversible gates does
qubits, and then communicate to each other to
not increase the efficiency of the algorithm. This is
find out for which qubits they did the same mea-
in contrast to the following examples, which con-
surement. For each of these instances, they are
cern true quantum algorithms that solve specific
then guaranteed to have found the same outcome.
tasks more efficiently than classical algorithms.
Again, an eavesdropper would introduce errors,
and can be detected by sacrificing a small random
sample of the key. B. Deutsch-Josza algorithm
In combination with classical encoding schemes
that encode messages into longer bit sequences Efficient quantum algorithms generally exploit
(see error correction, in section VI.A) these proto- the quantum parallelism to carry out many cal-
cols can be made reliable against a finite error rate, culations in one step, which is particularly use-
and secure even against sophisticated eavesdrop- ful if one is interested in a global property of
pers attacks that involve the collective manipula- these calculations. This is nicely illustrated by the
tion of the whole qubit stream.

V. QUANTUM COMPUTATION

This section discusses the most important

quantum-computation algorithms, associated with
the names Deutsch and Josza, Shor, and Grover.
To get a feeling of algorithms we start with the sim-
ple, classical example of adding two numbers.

A. Adding numbers

The discussion in Section III implies that quan-

tum computers can achieve, at least, the same
tasks as a classical computer. Since this requires FIG. 11 Reversible half adder and full adder circuits.
 16

FIG. 13 Grover search algorithm.

FIG. 12 Deutsch and Deutsch-Josza algorithms. |xi, resulting in

X |0i − |1i
|ψ2 i = Uf |ψ1 i = 2−N/2 (−1)f (x) |xi √ .
Deutsch-Josza algorithm, which allows to estab- x
2
lish a specific feature of certain Boolean functions
f : x → {0, 1} that specifically fall into one of the fol- In the final step, Hadamard gates are applied to all
lowing two classes: either the function is constant but the last qubit. Using the result shown in Fig.
(i.e., the output bit f is either always 1, or always 6(c), this delivers the final state
0), or it is balanced (i.e., the output bit is 0 for one XX |0i − |1i
half of the input values, and 1 for the remaining |ψ3 i = 2−N (−1)x·z+f (x) |zi √ .
half). z x
2
Assume that we are given a function f (x) which
is guaranteed to be either constant or balanced, Let us now have a look at the amplitude of
but at the outset we do not know to which of the the P state with |zi = |0i, which is given by
two classes it belongs. Classically, we need at least 2−N x (−1)f (x) . If f (x) is balanced, this amplitude
two function evaluations to find out that a function vanishes. On the other hand, if f (x) = c is con-
is balanced—and this is only in the fortunate case stant, this amplitude takes the value ±1 (depend-
that we immediately pick two inputs for which the ing on whether c = 0 or c = 1). Therefore, if f
outputs differ. In order to certify that a function is constant, a measurement of all qubits will find
is constant we need 2N /2 + 1 = 2N −1 + 1 function them all taking the value 0, while this will never
evaluations—that’s because if the function is bal- happen if the function is balanced. Remarkably,
anced, we may by chance first pick 2N /2 inputs using quantum parallelism, the distinction of both
that all result in the same output. In contrast, us- cases has been achieved with a single operation of
ing quantum gates, the Deutsch-Josza algorithm, the function gate.
shown in Fig. 12, requires only a single function A notable ingredient of the Deutsch-Josza is the
evaluation to determine whether the function is introduction of conditional phase factors (such as
constant or balanced. (The upper panel of the fig- (−1)f (x) ) in front of each of the computational basis
ure shows the Deutsch algorithm, the special case states. This strategy is also at the core of the prac-
of a function f (x) with single-bit input, which is tically more important algorithms discussed next.
addressed on worksheet 3.)
Starting from the initial state |ψ0 i = |0 . . . 001i,
Hadamard gates are used to form the superposi- C. Grover’s quantum search algorithm
tion
Grover’s quantum search algorithm exploits
Y X |0i − |1i |0i − |1i quantum parallelism to speed up the search for
|ψ1 i = Hn |ψ0 i = 2−N/2 |xi √ = |Ψi √ solutions among a large set of candidate solutions.
n x
2 2
A prime example is the search for entries in a
database which match to a given key. Let us enu-
(see also Fig. 6(b)). If f (x) = 1, the function gate merate all entries by an integer index x, and as-
changes the state of the last qubit into |1i−|0i
√
2
= sume for simplicity that the size of the database is
− |0i−|1i
√ ; for f (x) = 0, the state of this qubit re- N = 2N . The entries matching the key can then be
2
|0i−|1i characterized by an oracle function f (x), which is
mains √
2
. Therefore, the function gate intro- a Boolean function that returns f (x) = 1 if entry x
duces factors (−1)f (x) in front of each basis state matches to the key; otherwise, f (x) = 0.
 17

Assume that there are M  N entries matching

the key. Classically, we need to make ≈ N /M  1
queries of the database (or calls of the oracle func-
tion) to find one of these entries. The Grover p algo-
rithm, shown in Fig. 13, only requires O( N /M)
calls of the oracle function—not an exponential
speedup, but still sizeable when the database is
large.
The first step initializes the index register in the
now very familiar equal-superposition state |Ψi.
This is followed by a sequence of operations G,
known as the Grover iterate, in which the ora-
cle gate Ô is called once. Its action is defined to
flip the phase of all solutions: Ô|xi = (−1)f (x) |xi.
As we have seen in the Deutsch-Josza algorithm,
this can be achieved with a function gate acting
as Ôf |xi|qi = |xi|f p
(x) ⊕ qi, where the oracle qubit
q is initialized as 1/2(|0i − |1i) (Fig. 13 reserves
N 0 workspace qubits for the implementation of the FIG. 15 Two-bit Grover search algorithm.
oracle). The Grover iterate also contains a con-
ditional phase gate P = 2|0ih0| − I, ˆ which inverts
the phase of all computational basis states with and therefore lies in the X,Y plane. The unit vector
exception of the state |0i. This is embedded into p p
Hadamard gates, resulting into Ψ = ( M/N , 1 − M/N ) = (sin θ/2, cos θ/2)
Y
ˆ
Y
ˆ can be parameterized in terms of the angle θ/2
P 0 = ( Hn )(2|0ih0| − I)( Hn ) = 2|ΨihΨ| − I.
betweenp Ψ and the Y paxis. For M  N , θ =
n n
2 arccos 1 − M/N ≈ 2 M/N is small, such that
The Grover iterate can therefore be written as Ψ is almost parallel to the Y axis.
Per definition, the oracle function acts as
ˆ Ô.
G = (2|ΨihΨ| − I)
Ô(α|Xi + β|Y i) = −α|Xi + β|Y i,
The purpose of the Grover iterate is to rotate the
initial state into the direction of the equal super- which amounts to a reflection about the Y axis.
PM
position of solutions |Xi ≡ √1M m=1 |xm i, where The phase gate P 0 performs another reflection, now
we have enumerated all solutions as xm , m = about the Ψ axis. As a result, the state is rotated
1, 2, 3, . . . , M. This rotation takes place in a plane by an angle θ towards
p the X axis. Repeating this
PN −M rotation ≈ (π/4) N /M times rotates the state vec-
spanned by |Xi and |Y i = √N1−M m=1 |ym i, the
tor close to the X axis—the misalignment will be
equal superposition of all non-solutions ym , m = less than θ/2. With high probability, a measure-
1, 2, 3, . . . , N − M. Figure 14 illustrates how this ment of the final state will therefore deliver a solu-
works. The initial state can be written as tion xm of the search problem.
p p
|Ψi = M/N |Xi + 1 − M/N |Y i, An instructive example is a two-bit search with
one solution x1 , depicted in Fig. 15. Panel (a)
shows a realization of the P gate with H, X, and
CNOT gates (as a matter of fact, this realizes −P ,
but an overall phase factor of a quantum state is
non-detectable). Depending on the binary repre-
sentation of x1 , the oracle function takes one of
four possible forms, which can be implemented us-
ing Toffoli (CCNOT) and X (NOT) gates as shown in
panel (b). For N = 4 = 22 , M = 1, the angle of the
initial state vector Ψ with the Y axis is θ/2 = 30◦ .
The Grover iterate rotates the state by θ = 60◦ . A
single iteration therefore rotates the state onto the
X axis, which immediately identifies the matching
entry x1 . In contrast, a classical search would on
average require 2.25 oracle calls before the solution
FIG. 14 Geometric interpretation of the Grover search. is found.
 18

FIG. 16 Quantum Fourier transformation. The indicated swap gates simply invert the order of the output qubits,
which is convenient for subsequent applications.

D. Quantum Fourier transformation |0〉 H |fN−1〉

Consider the Fourier transformation

|0〉 H QFT-1 |f2〉
N
2X −1
|0〉 |f1〉
f˜(z) = 2−N/2 ω xz f (x) H

x=0 |0〉 H |f0〉

of an N -bit function f . Here, we abbreviated 0 1 2

N N |u〉 U2 U2 U2 U2
N−1
|u〉
ω = e2πi/2 , such that ω xz = e2πixz/2 (where xz
is an ordinary, not bitwise, multiplication). Clas-
sically, implementation of the Fourier transforma- FIG. 18 Phase estimation circuit.
tion takes O(2N ) elementary gate operations. In
contrast, its quantum-mechanical analogue, the
quantum Fourier transformation in a notation analogous to the one denoting frac-
tional decimal numbers. As shown in the figure,
N
2X −1 the required transformation of each qubit can be
UQF T |xi = 2 −N/2
ω xz |zi ≡ |x̃i, achieved efficiently by first applying a Hadamard
z=0 gate, followed by phase rotation gates
 
can be implemented with O(N 2 ) gate operations, 1 0
Rn =
which constitutes an exponential increase in ef- 0 exp(2πi/2n )
ficiency that can be exploited in a range of algo-
rithms. that are controlled by the less significant qubits.
The corresponding circuit is shown in Fig. 16. An instructive example is the three-bit quantum√
The verification that the depicted circuit computes Fourier transformation, where ω = exp(2πi/8) = i.
the quantum Fourier transformation can be based In this case, R1 = T is the π/8 gate, and R2 = S is
on the product representation the phase gate. The corresponding circuit is shown
in Fig. 17.
|x̃i = |zN −1 i|zN −2 i · · · |z0 i,
p n
where |zn i = 1/2(|0i + ω 2 x |1i). Because of the E. Applications: From phase estimation to prime
2π periodicity of the phase, the phase factors can factorization
N −n
be written as ω 2 x
= ei2π[Link]−1 xn−2 ···x0 , where we
introduced the binary fractions Phase estimation.—A key application of the
quantum Fourier transformation is the estimation
N
X −1 of the (reduced) phase φ of an eigenvalue λ = e2πiφ
x/2n = xk 2k−n ≡ xN −1 · · · xn .xn−1 · · · x0 of a unitary operator U , where 0 ≤ φ < 1. This
k=0 can be used for a problem called order finding,
which in itself is a central step in the prime fac-
torization of numbers. Phase estimation can also
be used for a problem know as quantum count-
ing. These problems are briefly discussed later; at
the moment it suffices to know that they involve
different operators U .
Given the eigenstate |ui corresponding to λ, φ
can be estimated efficiently as an N bit binary frac-
FIG. 17 Three-bit quantum Fourier transformation. tion φ ≈ 0.φN −1 φN −2 · · · φ0 using the circuit shown
 19
N
in Fig. 18. Since U |ui = λ|ui and λ = ω 2 φ , where N
N n |0〉 H⊗N x x QFT-1
ω = e2πi/2 , the controlled-U 2 operations in the |ψ1〉 Uf |ψ2〉 |ψ3〉
first part of
pthe algorithm transform the qubits into
2n (2N φ) |0〉 y y⊕f(x)
the state 1/2(|0i + ω |1i). With N -bit preci-
sion, 2N φ ≈ φ0 , where the integer number φ0 has
the N -bit representation φ0 = φN −1 φN −2 · · · φ0 . The FIG. 19 Period finding circuit. The indicated states are
intermediate state can therefore be approximated specified in the text.
by the product representation

|zN −1 i|zN −2 i · · · |z0 i = UQF T |φ0 i = |φ̃0 i states are |ψ1 i = |Ψi|0i and

of the Fourier-transformed N -bit estimate of 2N φ, N

2X −1 r−1
1 X ^0 ˆ
−N/2
whose binary digits φn are then recovered by an |ψ2 i = 2 |xi|f (x)i = √ |(n/r) i|f (n)i,
inverse Fourier transformation. x=0
r n=0
Quantum counting.—A straightforward applica-
tion of the phase estimation algorithm is the de- where, as before, (n/r)0 denotes the N -bit estimate
termination of the number M of solutions in an N - of 2N (n/r), and the tilde indicates the Fourier-
item search problem, as encountered in the Grover transformed state. Furthermore, we abbreviated
search. In the X-Y plane, the rotation by one r−1
Grover iteration can written as the 1 X
|fˆ(n)i = √ exp(−2πnix/r)|f (x)i.
  r x=0
cos θ sin θ
G= ,
− sin θ cos θ The inverse Fourier transformation converts this
into the final state
which is a unitary matrix with eigenvalues e±iθ .
We also know that |Ψi lies in the X-Y plane, and 1 X
r−1
therefore is a superposition of the two correspond- |ψ3 i = √ |(n/r)0 i|fˆ(n)i,
r n=0
ing eigenstates, which can be fed into the slot for
|ui.
Order finding.—Phase estimation can also be so that the measurement of the output qubits in
used to solve the following number-theoretic prob- the first register delivers an N -bit approximation
lem: given two numbers a and M without com- of 2N (n/r).
mon divisors, what is the order r of a mod M , de- Prime factorization.—In a loose mathematical
fined as the smallest positive integer r such that sense, the factors of an integer number M can
ar mod M = 1? Here, the modulo operation deter- also be interpreted as ’periods’ of that number.
mines the remainder of the division by M . The Indeed, it turns out that the order-finding prob-
order can be obtained by estimating the phase of lem is equivalent to the problem of prime num-
the eigenvalues λn = exp(2πin/r) of the operator ber factorization, and therefore can be solved effi-
U |xi = |ax mod M i (for x < M ; otherwise U |xi = |xi, ciently using phase estimation. This is embodied
which guarantees that U is unitary). Conveniently, in Shor’s factorization algorithm. Because the ac-
the sum of eigenfunctions curate description of this algorithm requires vari-
ous number-theoretic concepts, we here only men-
r−1 tion one key ingredient: assume we have randomly
1 X
|un i = √ exp(−2πinz/r)|az mod M i chosen a number a and found that the order r of
r z=0 a mod M is even (otherwise, start again with an-
P other randomly chosen a). Then b = ar/2 is still
is independent of r, n |un i = |1i. Therefore, ini- an integer, which fulfills
tializing |ui = |1i, the phase estimation algorithm
will deliver an approximation of n/r, where each b2 mod M = 1 ⇒ (b + 1)(b − 1)mod M = 0.
value n in the range 0 ≤ n < r appears with equal
probability 1/r. This suffices to reconstruct the or- Furthermore assume that b mod M 6= −1 (other-
der r (most efficiently, by a method based on con- wise, start again. . . ). It then follows that b+ = (b+1)
tinued fractions). or b− = (b − 1) shares a nontrivial factor with M .
Period finding.—Note that the order r is the pe- The largest factor (the greatest common divisor,
riod of the function f (x) = ax mod M , i.e., f (x) = gcd) can be found efficiently using Euclid’s algo-
f (x + r). It is noteworthy that a variant of the pro- rithm: given c > d, iterate the identity gcd(c, d) =
cedure above can be used to find the period of any gcd(d, c mod d) until the smaller number is a divisor
integer-valued function. The corresponding circuit of the larger number; the smaller number is then
is shown in Fig. 19. The indicated intermediate the gcd of c and d, which delivers a factor of M .
 20

VI. ERROR CORRECTION AND PRACTICAL ISSUES are not correlated, i.e., if they only affect one bit at
a time. This does not apply, e.g., to a data package
A. Errors and error correction loss, which yields undetermined values of a num-
ber of consecutive bits. The design of a resilient
Errors occur both in computation as well as in error correction scheme therefore also depends on
communication, and generally degrade informa- an adequate error model, which identifies the types
tion content. In classical computation, typical er- of errors that are most likely to occur.
rors are flipped bits or lost data packages. A pri- Quantum computation is sensitive to a wide
mary goal of hardware design is to make such range of additional types of errors that affect the
errors unlikely, which can be done, e.g., by uti- amplitudes of individual or collective qubit states.
lizing dissipation to stabilize the outcomes of ir- The implementation of gates is delicate because of
reversible gate operations. This goal competes their linear and reversible nature, which prevents
with other goals such as speed, capacity, size, the use of dissipation to stabilize the outcomes.
stability, longevity, energy consumption, and, of In particular, multi-qubit gate operations typically
course, costs, which along with practical limita- require precise control of interactions, which can
tions means that a certain amount of errors must also leak on to other qubits. Furthermore, multi-
be tolerated. To cope with them, classical com- qubit gates tend to propagate errors—e.g., an error
putation algorithms and communication protocols in the control bit of a CNOT gate will result in an
introduce a certain amount of overhead (redun- error of the target bit. To a larger extent than clas-
dancy) into the information. This can be used to sical codes, therefore, quantum codes must rely on
detect whether errors have occurred (a step called a good error model.
syndrome diagnosis), and preserves enough of the Consider, for example, a system designed to real-
information so that the errors can be corrected (by ize the Pauli X gate (NOT) by time evolution with a
recovery operations). Hamiltonian aX, which must be sustained for a set
A simple example is the code time ∆t = ~π/2a (see worksheet 2). Imperfections
0L → 000, 1L → 111, in the duration of this action will introduce errors
into the final states. Furthermore, the physically
which represents one logical bit of information realized Hamiltonian may differ from aX (e.g., it
(subscript L) in terms of three physical bits. If one may feature contributions proportional to Y and
of the physical bits is flipped this can be detected Z, as well as many-qubit terms arising from inter-
by comparison to the other bits, and subsequently actions), and all terms may fluctuate temporally.
corrected following the rules An important source of these contributions is
the dynamics of the environment, i.e., all physical
000, 001, 010, 100 → 0L ; 011, 101, 110, 111 → 1L .
components that are not directly participating in
Following this scheme, only errors affecting two or the computational tasks. For example, the uncon-
all three of the physical bits will result in an error trolled motion of charge carriers in parts of a de-
of the logical bit. A single-bit error probability p vice results in a fluctuating electromagnetic field.
will thus result in an error probability p2 (3 − 2p) for External influences of this kind are worrisome be-
the logical bit, which is much less than p if p is cause they generally cause the state of the quan-
small. tum register to become mixed: the register state
Classical error correction of many independent will depend on the environment, and therefore be-
single-bit errors can be achieved when k logical comes entangled with it; its reduced density ma-
bits of information are encoded into a sufficiently trix will therefore describe a statistical mixture.
large number n of physical bits. The number of This phenomenon, called dephasing or decoher-
differing bits of two code words is called their dis- ence, is undesirable because it negatively affects
tance, and the smallest distance occurring in a the usable amount of entanglement (as we have
code is the distance of the code, d. Correction of seen on worksheet 2 for the example of the equal
multiple errors then requires to identify the log- mixture of all four Bell states). Even more directly,
ical code word with the smallest distance to the perturbed relative phases of quantum states also
register state, which is reliable unless the num- negatively affect their superposition, i.e., quantum
ber of errors exceeds [(d − 1)/2] (here [·] denotes parallelism.
the integer part of a number). In other words, d Consequently, error correction schemes for
determines the number of erroneous physical bits quantum information need to cope with a much
that can be tolerated for reliable identification of larger variety of errors—in principle, a continuum
the logical bits. Classical error correction codes of errors, which can affect the phase and magni-
of this kind are therefore often characterized by tude of the amplitudes of the state. Moreover, they
the triple [n, k, d]. It should be noted that the dis- cannot establish redundancy by copying the infor-
tance is a useful characteristic only if the errors mation, which would violate the no-cloning theo-
 21

 Analogously, errors of the type Z can be cor-


logical qubit  rected using a three-qubitpcode |0L i = |+++i,
 |1L i = |−−−i, where |±i = 1/2(|0i ± |1i) are the

eigenstates of the X operator. Effectively, the roles
 |0〉 X X of X and Z are then interchanged.
ancilla qubits  Once we can cope with individual X and Z er-
 |0〉 X X
rors, schemes can be fused via concatenation to




















syndrome diagnosis recovery operations yield a code that can also correct combined errors.
This naturally leads to the Shor code, which uses
FIG. 20 Three-qubit code for correction of single-qubit 9 qubits to encode one logical qubit according to
flip (X) errors.
(|000i + |111i)(|000i + |111i)(|000i + |111i)
|0L i = √ ,
2 2
rem. Surprisingly, resilient quantum error correc-
(|000i − |111i)(|000i − |111i)(|000i − |111i)
tion strategies not only exist, but also get by with |1L i = √ .
a finite set of diagnosis and recovery operations—a 2 2
phenomenon known as error discretization.
Note how X errors can be detected by comparing
In order to see how this comes about, let us
three consecutive qubits, while Z errors are de-
specialize to single-qubit errors. Such errors can
tected by the relative phase of every third qubit;
generally be represented by a unitary 2 × 2 ma-
the latter can be diagnosed using the syndromes
trix U = a0 I + ax X + ay Y + az Z, which transforms
X1 X2 X3 X4 X5 X6 and X4 X5 X6 X7 X8 X9 .
an error-free physical qubit state |ψi = α|0i + β|1i
Since Y = iXZ, the Shor code also allows to
into the defective state U |ψi. The contribution X
correct Y errors—therefore, it offers protection
flips the qubit with a probability depending on the
against arbitrary single-qubit errors. On the other
coefficient ax . An individual flip can be detected
hand, considering that here [n, k] = [9, 1], this is
and corrected by adapting the classical three-bit
achieved with a rather large overhead. There are
scheme: Encode the two logical basis states into
more sophisticated codes that achieve the same
three physical qubits, such that |0L i = |000i and
task with less than 9 qubits, the minimum being
|1L i = |111i. A logical-qubit state is then described
5. This still exceeds what was required classically,
by a physical state |ψi = α|000i + β|111i. This is not
and moreover involves many more syndrome di-
a threefold copy of the logical qubit, which would
agnosis and recovery operations. Considering that
correspond to a separable product state—instead,
these operations are also prone to errors, it is clear
we here deal with an entangled three-qubit state.
that quantum error correction is still a challenging
Erroneous flips of the nth qubit (due to Xn ) result
task.
in admixture of the other three-qubit basis states.
More general schemes—in particular, codes
This can be detected by measurements of the error
based on the stabilizer formalism, which utilizes
syndromes S1 = Z1 Z2 and S2 = Z1 Z3 , and corrected
group theory—allow to cope with complex types of
by applying an operator U following the rules
errors affecting a collection of qubits, and also take
S1 = 1, S2 =1 → U = I, care of errors accumulated by faulty gate opera-
S1 = 1, S2 = −1 → U = X3 , tions. If the initial error rate falls below a cer-
S1 = −1, S2 =1 → U = X2 , tain threshold, these codes can be scaled up by
S1 = −1, S2 = −1 → U = X1 . adding more and more overhead, thereby allow-
ing (in principle) to achieve arbitrarily good (fault-
Figure 20 shows how these conditional opera- tolerant) quantum computation. However, while
tions can be achieved without doing any measure- present technology has advanced sufficiently to
ments, but instead utilizing CNOT and Toffoli gates enable reliable quantum communication, a uni-
involving two ancilla qubits. How does this circuit versal quantum computer is still far removed from
cope with the continuous set of possible errors? reality.
A single-qubit error moves the quantum state into
a subspace spanned by the computational basis
states with distance 0 and 1 to the logical qubits, B. Practical requirements
and in this basis is specified by four complex am-
plitudes. In the circuit, these amplitudes simply This brief concluding section juxtaposes the
determine the probabilities that the control bits main technological requirements for a workable
trigger the various CNOT operations. At the end of quantum computer and the key features of some
the procedure, the complex amplitudes are trans- specific physical implementations.
ferred to the two ancillary qubits, whose joint state As is clear from the preceding section, quan-
also resides in a four-dimensional space. tum information processing poses serious techni-
 22

cal challenges. E.g., fault tolerant computation re- ten corresponds to the ground state of the sys-
quires that the error rate of gate operations falls tem. This state can be prepared by allowing the
below a certain threshold, and can only be im- system to equilibrate (relax) at low temperature.
plemented when the system can be scaled up by Other states may be enforced by relaxation in
adding more and more components. The various presence of external fields (such as a magnetic
challenges have been canonized by diVincenzo into field for nuclear spins), or dynamically (e.g., by
a set of five core requirements, which are known as pumping of atomic transitions).
the DiVinzenco criteria: It is not necessary, however, that the preparation
1. Well-defined qubits. This requires to identify process is deterministic. E.g., a viable strategy
physical systems whose quantum dynamics is is to make a hard, complete measurement of the
essentially constrained to two quantum levels. register, thereby forcing it into a pure state that
Examples for naturally occurring two-level sys- is completely determined by the recorded mea-
tems are the spin of electrons and certain nu- surement outcomes.
clei, as well as the polarization of photons. In If initialization is not perfect, it can be combined
many proposed systems, however, the reduction with error correction schemes to enhance its ac-
to two levels is only approximate. Examples are curacy. In particular, if the state is not entirely
atoms in ion traps, photons stored in microcav- pure, the entropy can be transferred into ancilla
ities, the magnetic flux penetrating a supercon- qubits, so that the register state become puri-
ducting ring, and electrons confined to (normal fied. Such procedures also allow to carry out
conducting or superconducting) solid-state de- initialization in multiple steps.
vices, such as quantum dots. In all these cases,
care has to be taken that the system does not 3. Universal set of quantum gates. As discussed
populate the other available energy levels (i.e., in section III, a universal set of quantum gates
one needs to avoid leakage), which can be best can be obtained using single-qubit rotations on
done by making these levels energetically inac- the Bloch sphere, and at least one type of two-
cessible. qubit operations (such as CNOT). Alternative
constructions use a sufficiently large number
It is of course possible to design quantum com- of multi-qubit gates. Using facilities to swap
putation schemes that are not binary, and there- qubits, it is not necessary that each pair of
fore make use of more than two levels in the qubits can be coupled directly; still, the coupling
energetically accessible range ∆E of the register network needs to be sufficiently interconnected,
components. However, adding qubits provides and also should be scalable to a large number of
much better scalability. Each additional qubit qubits. This is a severe problem for many pro-
multiplies the register state dimension by a fac- posed implementations.
tor of two (resulting in 2N levels), and each qubit
can be addressed individually, which requires For each implementation, the precision of gate
energy resolution ∼ ∆E/N instead of resolution operations can be increased not only via error
∼ ∆E/2N for a comparable multi-level system. correction, but also using insight into the spe-
cific quantum dynamics of the system. E.g., echo
By convention, if there is a clear energy sep- and refocussing techniques in nuclear magnetic
aration between the two levels, the state with resonance employ judiciously timed magnetic-
the lower energy is designated |0i, and the state field pulses to average out the effects of spuri-
with the higher energy is designated |1i. As dis- ous qubit couplings and unwanted single-qubit
cussed in the context of error correction, the terms in the Hamiltonian. This exemplifies the
physical qubits can then be used to encode logi- natural tradeoff between precision and speed of
cal qubits, which allows to take care of the most gate operations, which is a general obstacle in
likely sources of errors specific to the chosen im- all implementations.
plementation.
4. Qubit-specific measurement. Ideally, to deter-
2. Initialization to a pure state. The quantum regis- mine the outcome of a computation one should
ter must start in a well-defined state. It is suf- be able to carry out ideal measurements on each
ficient to have a reliable method to prepare at physical qubit. In practice, a finite degree of
least one such state, since a universal quantum imperfection can be tolerated. This may be be-
computer would be able to transform this into cause the computation can be repeated, or be-
any other state. Utilities to prepare a larger va- cause it can be carried out on many systems in
riety of states further improves the efficiency of parallel. An interesting simplification occurs be-
quantum computation. cause algorithms often use quantum parallelism
Using the convention of labeling qubit levels ac- only during the calculation, but are designed to
cording to their energy, the register state |0i of- deliver a classical bit sequence xn as output.
 23

Such results can be amplified using a quantum ary qubits reside in registers, while flying qubits
fanout operation of the type α|x1 i|00i+β|x2 i|00i → propagate along quantum transmission lines.
α|x1 x1 x1 i + β|x2 x2 x2 i, which enhances the mea- Photons make ideal flying qubits, while nuclei
surement fidelity because the desired informa- and atoms typically serve as stationary qubits.
tion is now encoded in additional qubits. (Note In this respect, electrons in solid state devices
how the fanout operation differs from a copy op- are particularly flexible because they can move
eration prohibited by the no-cloning theorem; through conducting regions, but can also be
rather, it closely resembles error correction pro- confined electrostatically.
cedures.)
7. Transmit flying qubits between distant locations.
5. Long coherence times. This statement subsumes This can be achieved with high fidelity for pho-
various requirements for the protection of the tons, but is far more challenging for electrons.
quantum register state throughout the computa- In spintronics, e.g., the electronic spin can be
tion. In particular, one needs to preserve the ca- flipped by scattering off magnetic impurities in
pacity to use superposition and entanglement as the transmission line.
computational resources. As discussed before,
this capacity is in particular degraded by spu- At present, none of the various physical candi-
rious internal and external interactions. These date platforms score well on all of the core require-
effects can be broadly categorized depending on ments. The key challenge is to overcome the nat-
whether they affect the population probabilities ural trade-off between easy access of qubits (ini-
or interference of the register states (i.e., the tialization, control, readout), a high degree of iso-
modulus or complex phase of the amplitudes): lation (coherence), and scalability. On the other
Relaxation (on a time scale T1 ) affects the prob- hand, this trade-off can also be exploited to bal-
abilities, and often is combined with energy loss ance strengths in certain areas (e.g., a long co-
or gain (dissipation). Dephasing (on a time scale herence time) against weaknesses in other areas
T2 ) affects the phases, and generally reduces the (e.g., imprecise gates, whose errors can then be
purity and entanglement of the register state (de- corrected by running a more sophisticated, time-
coherence). consuming error correction scheme). That said,
any viable quantum computer is likely to be a hy-
In most systems, T1  T2 , i.e., the operabil-
brid device which combines the specific strengths
ity is limited by dephasing. A viable quantum
of the various physical platforms.
computer needs to carry out >10000 gate opera-
tions during this time. The polarization of pho-
tons and the spin of electrons in solid-state de-
VII. FURTHER READING
vices are two types of qubits which possess rea-
sonably long dephasing times (the latter lends a
main incentive to the field of spintronics). On the [1] M. A. Nielsen and I. L. Chuang, Quantum
other end of the scale, charge (as, e.g., carried Computation and Quantum Information (Cam-
by electrons confined in a quantum dot) couples bridge University Press, 2000).
strongly to electromagnetic fluctuations, which [2] J. Stolze and D. Suter, Quantum Computing—
discounts this degree of freedom for quantum A Short Course from Theory to Experiment,
computation purposes. 2nd edition (Wiley VCH, 2008).
These requirements are supplemented by two
[3] J. Preskill, Lecture notes, available at
additional criteria for reliable quantum communi-
[Link]
cation:
∼preskill/ph219/[Link]#lecture
6. Convert stationary and flying qubits. Station-