Quantum Computing Lecture Notes Mca Course
Quantum Computing Lecture Notes Mca Course
messages.pdf_cover_qr_code_label
messages.studocu_not_sponsored_or_endorsed_by_college
messages.downloaded_by
lOMoARcPSD|61948123
Quantum Computing
Lecture notes integrated with the book "Quantum Computation and
Quantum Information", Michael A. Nielsen, Isaac L. Chuang
Author
Alessio Bandiera
February 2, 2026
messages.downloaded_by
lOMoARcPSD|61948123
Contents
2 Mathematical foundations 20
2.1 Hilbert spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.1.1 Linear operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.2 Spectral theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.3 Projectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.4 Tensor product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.4.1 General definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.4.2 Kronecker product . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4 Quantum algorithms 75
messages.downloaded_by
lOMoARcPSD|61948123
Contents
Contents ii
messages.downloaded_by
lOMoARcPSD|61948123
Contents
Contents iii
messages.downloaded_by
lOMoARcPSD|61948123
Personal notes and summaries collected as part of the Quantum Computing course offered
by the degree in Computer Science of the University of Rome "La Sapienza".
Further information and notes can be found at the following link:
[Link] Anyone can feel free to report inaccuracies, im-
provements or requests through the Issue system provided by GitHub itself or by contact-
ing the author privately:
• Email: alessio.bandiera02@[Link]
• LinkedIn: Alessio Bandiera
The notes are constantly being updated, so please check if the changes have already been
made in the most recent version.
Suggested prerequisites:
TODO
Licence:
These documents are distributed under the GNU Free Documentation License, a
form of copyleft intended for use on a manual, textbook or other documents. Material
licensed under the current version of the license can be used for any purpose, as long as
the use meets certain conditions:
• All previous authors of the work must be attributed.
• All changes to the work must be logged.
• All derivative works must be licensed under the same license.
• The full text of the license, unmodified invariant sections as defined by the author if
any, and any other added warranty disclaimers (such as a general disclaimer alerting
readers that the document may not be accurate for example) and copyright notices
from previous versions must be maintained.
• Technical measures such as DRM may not be used to control or obstruct distribution
or editing of the document.
messages.downloaded_by
lOMoARcPSD|61948123
Quantum computing is a rapidly developing discipline that explores how the laws of
quantum mechanics can be used to process information. While classical computation is
based on bits that take values of either 0 or 1, quantum computation relies on quantum
bits, or qubits. A qubit can exist in a “superposition” of classical states, allowing it to
encode richer information than a single bit. Furthermore, qubits can exhibit particular
properties that enable forms of information processing with no classical counterpart. Such
properties provide the foundation for algorithms that promise to solve certain problems
more efficiently than their classical analogues.
The design of quantum algorithms requires a different perspective from that of classical
computation. In classical computer science, the majority of widely studied algorithms
are deterministic, meaning that for a given input they will always produce the same
output. Some algorithms are randomized, making use of probability to achieve efficiency
or simplicity, yet even in those cases the computation itself is ultimately classical in
nature. In fact, to achieve such randomness classical algorithms employ pseudo-random
number generation, which must ultimately produce finite sequences.
Quantum computation, by contrast, incorporates probability at its core. The act of mea-
suring a quantum system does not reveal a single, predetermined result, but rather yields
one outcome from a distribution of possible outcomes, with probabilities governed by
the system’s quantum state. This fundamental probabilistic characteristic distinguishes
quantum algorithms from their classical counterparts.
In fact, in the context of quantum computing we are often interested in probabilistic
algorithms: for such algorithms, a given input i can lead to a finite set of possible
outputs
Pn o1 , . . . , oN , each occurring with an associated probability p1 , . . . , pN — where
p
i=1 i = 1.
messages.downloaded_by
lOMoARcPSD|61948123
and they represent the classical bits 0 and 1 respectively — the notation above is called
“braket” notation and it will be explored in greater detail in the following chapter.
So what is a qubit? A qubit is the basic unit of information in quantum computing, which
represents a superposition of states simultaneously. Mathematically speaking, the state
of a qubit is a vector
1 0 α
|ψ⟩ = α |0⟩ + β |1⟩ = α +β =
0 1 β
where α, β ∈ C such that |α|2 + |β|2 = 1 are called probability amplitudes. But why
are we talking about probabilities in the first place? The “true” state of a qubit cannot
be observed, and we say that the qubit is in a superpotion of |0⟩ and |1⟩ in the sense
that α and β describe the probabilities of getting either states once the qubit is measured.
This is because to know the value of a qubit we have to measure it, and the measurement
operation itself will make the qubit collapse into either |0⟩ or |1⟩ with probabilities |α|2
and |β|2 respectively, i.e.
|0⟩ @ |α|2
α |0⟩ + β |1⟩
|1⟩ @ |β|2
where the @ notation (read as “at”) denotes the probabilty of the corresponding out-
come. Note that if we measure a collapsed qubit we will keep observing the same state
indefinitely.
In reality, to be precise qubits actually collapse into any multiple z |0⟩ or z |1⟩, where
z ∈ C is a complex number such that |z| = 1, but this is not relevant from a physical
point of view. In fact, for any θ physicists treat |ψ⟩ = |0⟩ and |ψ ′ ⟩ = eiθ |0⟩ as the same
physical state, because probabilities depend on squared magnitudes and thus
2
eiθ α = |α|2
(and the same applies for β too) even though |ψ⟩ and |ψ ′ ⟩ are different vectors mathe-
matically. Therefore, in general we can actually drop the global phases from the qubits
entirely.
messages.downloaded_by
lOMoARcPSD|61948123
In particular, we observe that the second matrix σx is exactly the matrix of the NOT
operator. For this reason, the NOT operator is also called X, and we will see the Z and Y
operators (representing the other two matrices, respectively) as well in later sections.
Another very important transformation is represented by the Hadamard gate, which is
the following matrix
1 1 1
H := √
2 1 −1
This matrix has the effect of “mapping” classical states into superpositions:
|0⟩ @ 12
1 1 1 1 1 1 1
H |0⟩ = √ =√ = √ (|0⟩ + |1⟩)
2 1 −1 0 2 0 2 |1⟩ @ 12
For instance, in this example given |0⟩ which represents the classical bit 0, we get a
qubit as output of the linear transformation. In general, the operation performed by the
Hadamard gate can be represented as follows:
1
∀a ∈ {0, 1} √ (|0⟩ + (−1)a |1⟩)
2
As a side note, as we mentioned at the beginning of the chapter quantum mechanics has
randomness intrinsically, and since the operation H |0⟩ returns a qubit that has 50% of
messages.downloaded_by
lOMoARcPSD|61948123
probability of being either |0⟩ or |1⟩ once measured, this operation provides a true random
number generator.
Lastly, can we represent qubits graphically? Well, we may be tempted to anwer negatively
to this question, since a qubit is described by two complex numbers α, β ∈ C, which implies
that we actually need 4 dimensions to correctly represent our vector. However, through
polar coordinates we can actually define a graphical representation which allows us to
“picture” qubits, through the so called Bloch sphere. First, consider a qubit
|ψ⟩ = α |0⟩ + β |1⟩
for some α, β ∈ C such that |α|2 + |β|2 = 1, as usual. Now, recalling that any complex
number z ∈ C can be actually written as follows
z = |z| eiθ
for some angle θ, we can rewrite our qubit as follows:
|ψ⟩ = |α| eiθα |0⟩ + |β| eiθβ |1⟩
= eiθα |α| |0⟩ + |β| ei(θβ −θα ) |1⟩
and finally, since |α|2 + |β|2 = 1 is precisely the equation of the circumference of radius
1, we usually rewrite the last equation as follows:
θ iφ θ
|ψ⟩ = cos |0⟩ + e sin |1⟩
2 2
where θ ∈ [0, π], φ ∈ [0, 2π). This formulation of the qubit |ψ⟩ allows us to represent it
inside the Bloch sphere: in fact, in this formulation the qubit is normalized, which implies
that it will lie on a 3 dimensional unit sphere, and it is described by the two phases θ and
φ — in 2D polar coordinates there is only 1 angle, as in 3D polar coordinates there are 2
angles.
messages.downloaded_by
lOMoARcPSD|61948123
{0, 1}2 = {0, 1} × {0, 1} = {(0, 0), (0, 1), (1, 0), (1, 1)}
To obtain all the possible states of |ψ⟩ and |ϕ⟩ we just have to compute the tensor product
between them, which is
α0 β0
|ψ⟩ ⊗ |ϕ⟩ = ⊗
α1 β1
α0 β0
α0 β1
=
α1 β1
α1 β1
1 0 0 0
0 1 0 0
= α0 β0 + α0 β1 + α1 β0 + α1 β1
0 0 1 0
0 0 0 1
0 1
At the beginning of the chapter we defined |0⟩ and |1⟩ to be and without
1 0
providing an explaination; now that we are dealing with more than 2 dimensions we can
messages.downloaded_by
lOMoARcPSD|61948123
show why such names are used. In fact, we will use the following naming convention
1 0 0 0
0 1 0 0
|00⟩ := |01⟩ := |10⟩ := |11⟩ :=
0 0 1 0
0 0 0 1
The basis of the 2D space formed by |0⟩ and |1⟩ is usually called computational basis,
since we can directly map |0⟩ to the classical 0, and |1⟩ to the classical 1. Alternatively,
it is also called Z basis, as opposed to the X basis which we will encounter in the next
chapters.
Let’s do an example of tensor product between two qubits defined in the Z basis: con-
sider
1 1
|ϕ⟩ = √ (|0⟩ + |1⟩) |ψ⟩ = √ (|0⟩ + |1⟩)
2 2
messages.downloaded_by
lOMoARcPSD|61948123
where the probabilities at the end refer to the two individual qubits. To recap, in general
the tensor product |ψ⟩ ⊗ |ϕ⟩ of two qubits encodes the superposition of 4 basis states,
namely |00⟩, |01⟩, |10⟩ and |11⟩. We will dive much deeper into the details of the tensor
product in the next chapter, but for now it suffices to know that the tensor product
satisfies the distributive property.
CNOT(a, b) = a ⊕ b
First, we observe that this function is clearly not invertible, since for instance if we know
that the output is 0 we still need the input a to evaluate if b was 0 or 1. Hence, because we
would like this computation to be invertible — and we will see why later in our discussion
— to solve this issue we usually pair the output of CNOT with a itself, so that we can
actually invert the computation:
CNOT(a, b) = (a, a ⊕ b)
We will start from this operator in order to construct its equivalent quantum gate.
messages.downloaded_by
lOMoARcPSD|61948123
So far we only dealt with transformations that expected only 1 qubit argument as input,
but the CNOT gate would certainly need 2 inputs to perform any computation, so how
do we provide two inputs to it? As we showed before, we know that
∀i, j ∈ {0, 1} |i⟩ ⊗ |j⟩ = |ij⟩
which directly implies that the vector |ij⟩ encapsulates two qubits at once without am-
biguity. Hence, we can actually leverage the tensor product to provide the input to the
CNOT matrix, such that the quantum CNOT will behave as follows
CNOT(|a⟩ ⊗ |b⟩) = |a⟩ ⊗ |a ⊕ b⟩
The matrix that behaves as such is the following
1 0 0 0
0 1 0 0
CNOT :=
0 0 0 1
0 0 1 0
which expects a 4 × 1 input vector, and outputs a 4 × 1 output vector as well. Laslty,
as for the CNOT operator, we can actually define controlled operators for both Y and Z,
which are respectively called CY and CZ operators.
In this example, we have 1 single input qubit, namely q, and the box labeled with an X
represents the NOT gate. We observe that, by convention, all qubits in quantum circuits
are assumed to be set to |0⟩.
In the following example, instead, it is represented how the Hadamard gate looks like in
quantum circuits.
messages.downloaded_by
lOMoARcPSD|61948123
Moreover, if we consider two qubits as inputs q0 and q1 , we can represent the CNOT
operator as follows:
We observe that q1 then becomes the output of the CNOT operation, and q0 remains
unchanged. Lastly, the measurement operation is represented with the following pi-
cure:
messages.downloaded_by
lOMoARcPSD|61948123
Lastly, another very important circuit is the following, which produces the so called
Greenberger-Horne-Zeilinger (GHZ) state
messages.downloaded_by
lOMoARcPSD|61948123
Whenever we have a state |ψ⟩ that cannot be represented as the tensor product of two sim-
pler quantum states, we say that the state is entangled — or that its possible outcomes
are entangled. In particular, entangled states describe a very weird phenomenon first
proposed as a thought experiment in a groundbreaking paper by Einstein, Podolsky
and Rosen (EPR) [EPR35], the so called EPR paradox.
The thought experiment involves a pair of particles prepared in such entangled state.
Einstein, Podolsky, and Rosen pointed out that, in this state, if the position of the first
particle were measured, the result of measuring the position of the second particle could
be predicted. If instead the momentum of the first particle were measured, then the
result of measuring the momentum of the second particle could be predicted. Einstein
famously called this phenomenon “spooky action at a distance”, and to the best of our
knowledge the theory of quantum mechanics says that if we have two engangled states,
and measure one of them — for instance, say that it collapses to |0⟩ — the other state
will instantaneously collapse to |1⟩ (and viceversa). They are perfectly anti-correlated,
even if the two states are phisically light-years away from each other. For instance, in our
previous example with |ψ⟩ (which we now know is actually |Ψ+ ⟩) is that if we have two
qubits q0 and q1 such that their total state is |ψ⟩,l whenever we measure one of them it
will collapse in either |01⟩ or |10⟩ with 50%, and the other qubit will collapse with the
opposing outcome.
To be precise, entanglement is not a way to tranfer information — collapsing happens
instantaneously, which would violate the fact that nothing can travel faster than light,
not even information. Instead, it is a way to share correlations nonlocally. In fact, it is
a phenomenon that concerns the whole quantum system considered: for instance, given
three qubits q0 , q1 , q2 , such that q1 and q2 are entangled, we might want to only measure
q0 ⊗ q1 , which in turn will make q2 collapse into some quantum state that has to be
mathematically computed in order to be predicted — this will be more clear when we will
describe quantum teleportation in Section 1.3.2.
To finish off this section, we can actually generate entangled states, or EPR pairs for
short, through quantum gates as such:
messages.downloaded_by
lOMoARcPSD|61948123
In particular, we observe that the first Hadamard gate will transform |0⟩ to √1
2
(|0⟩ + |1⟩),
and through the CNOT operation we obtain
1
|Φ+ ⟩ := √ (|00⟩ + |11⟩)
2
messages.downloaded_by
lOMoARcPSD|61948123
1: function QuantumTeleportation(q0 , q1 , q2 )
2: q1 ← H(q1 )
3: q2 ← CX(q1 , q2 ) ▷ entangle q1 and q2
4: q1 ← CX(q0 , q1 )
5: q0 , q1 ← measure(q0 , q1 )
6: if q1 == |1⟩ then
7: q2 ← X(q2 )
8: end if
9: if q0 == |1⟩ then
10: q2 ← Z(q2 )
11: end if
12: return q2
13: end function
There is quite a lot to unpack in this diagram. First, the quantum state that we want to
teleport is q0 , and it will be teleported in q2 at the end of the quantum computation.
In the first part of the circuit, we see that q1 and q2 are entangled (in an initial stage of the
process, not performed by Alice nor Bob) in the Bell state |Φ+ ⟩ thanks to the Hadamard
and the CNOT gates — as we described in previous sections. In a real-world scenario,
we will assume that q1 and q2 are given to Alice and Bob respectively (through some
quantum channel such as optical fibers or free-space links in order to avoid decoherence),
and quantum mechanics will guarantee that the teleportation will work even if our two
protagonists are thousands of kilometers away from each other.
After creating and entangling q1 and q2 (say for instance in a lab as preparation), we have
the part of circuit that concerns Alice: in fact, she must apply a CNOT to her entangled
messages.downloaded_by
lOMoARcPSD|61948123
messages.downloaded_by
lOMoARcPSD|61948123
Finally, Alice will perform the measurement on q0 and q1 , and what will happen is that
the whole quantum state of the quantum circuit will collapse as follows:
|00⟩01 ⊗ |ψ⟩2 @ 41
@ 41
|01⟩01 ⊗ X |ψ⟩2
|10⟩01 ⊗ Z |ψ⟩2 @ 41
|11⟩ ⊗ XZ |ψ⟩ @ 1
01 2 4
In fact, from this table we can easily explain the last part of the quantum teleportation
circuit, i.e. Bob’s part, as shown below.
Alice’s outcome Bob’s part Bob’s result
0 and 0 I |ψ⟩
0 and 1 X XX |ψ⟩ = |ψ⟩
1 and 0 Z ZZ |ψ⟩ = |ψ⟩
1 and 1 XZ XZXZ |ψ⟩ = |ψ⟩
Thus, in the end Bob was able to reconstruct |ψ⟩ correctly, at the cost of having measured
q0 , which means that Alice lost her superposition of states forever.
q0 • H •
q1 H • •
q2 X Z
As a final note, we observe that the circuit written in this form is rather unusual. Indeed,
it helps to visualize the fact that Alice performs the measurement before Bob can have
his qubit collapse, but in reality the measurement could have been done at the end of the
circuit and it would not have made any difference at all.
q0 • H •
q1 H • •
q2 X Z
Figure 1.11: The Quantum Teleportation circuit with the measurement moved at the end.
Indeed, all the quantum circuits we will present from now on will have their measurements
placed at the end of the whole computation. This idea is summed up below.
messages.downloaded_by
lOMoARcPSD|61948123
Algorithmically, this means that the following sequence of operations on two qubits q0 ,
q1
1: b ← measure(q0 )
2: if b then
3: q1 ← U (q1 )
4: end if
which performs an application of the U gate classically conditioned on the result of b, can
be equivalently rewritten as
1: q0 , q1 ← C-U (q0 , q1 )
2: b ← measure(q0 )
where that C-U is the controlled version of the U gate. To end the chapter, we will show
the validity of this postulate: in particular we will first show its validity for a 2-qubit
system — i.e. U acts on one qubit only — and the generalization for an n-qubit unitary
U is left as exercise in the next chapter, after we will have laid down all the mathematical
tools needed.
First, suppose that the complete state of the system |ψ⟩ is equal to
We observe that we cannot simplify the calculations by assuming that |ψ⟩ is equal to
some q0 ⊗ q1 , because this would already imply that the current state |ψ⟩ is not entangled,
making the proof less general. Let U be any unitary gate, and consider the following
quantum circuit:
First, we need to measure the first qubit, which means that the system turns into the
following state
|00⟩ + |01⟩ @ |α00 |2 + |α01 |2
|ψ⟩
|10⟩ + |11⟩ @ |α10 |2 + |α11 |2
messages.downloaded_by
lOMoARcPSD|61948123
1.4. Exercises
and the same reasning applies for the probability that it collapses to |1⟩. Then, we need
to apply U on the second qubit only in the cases in which the first input collapsed to |1⟩,
therefore
@ |α00 |2 + |α01 |2
|00⟩ + |01⟩
|ψ⟩
|1⟩ ⊗ U |0⟩ + |1⟩ ⊗ U |1⟩ @ |α10 |2 + |α11 |2
We observe that now we moved the application of the controlled U gate before the mea-
surement on the first qubit, so the state of the circuit can be computed as follows:
|ψ⟩
=α00 |00⟩ + α01 |01⟩ + α10 |10⟩ + α11 |11⟩
C−U (|ψ⟩)
−−−−−→α00 C−U |00⟩ + α01 C−U |01⟩ + α10 C−U |10⟩ + α11 C−U |11⟩
=α00 |00⟩ + α01 |01⟩ + α10 |1⟩ ⊗ U |0⟩ + α11 |1⟩ ⊗ U |1⟩
@ |α00 |2 + |α01 |2
measure(|ψ⟩0 ) |00⟩ + |01⟩
−−−−−−−−→
|1⟩ ⊗ U |0⟩ + |1⟩ ⊗ U |1⟩ @ |α10 |2 + |α11 |2
1.4 Exercises
Problem 1.1
Prove that the state √1 (|00⟩
2
+ |11⟩) is entangled.
Solution. By way of contradiction, suppose that it is not entangled, therefore there must
exist two qubits
α γ
q0 = q1 =
β δ
messages.downloaded_by
lOMoARcPSD|61948123
1.4. Exercises
and since 1
1 0 √
2
1 1 0 0 0
√ (|00⟩ + |11⟩) = √ + =
2 2 0 0 0
0 1 √1
2
Then, since αδ = 0, at least one between α and δ must be 0, meaning that at least one
between αγ and βδ must be 0, raising a contradiction .
messages.downloaded_by
lOMoARcPSD|61948123
Mathematical foundations
2
Now that we have introduced some preliminary concepts in quantum mechanics and quan-
tum computation, we can turn our attention to the mathematical foundations that
will allow us to develop a deeper understanding of the tools ahead. By the end of this
chapter, we will be ready to state the postulates of quantum mechanics in a precise form.
To prepare for that, we must first lay out several essential definitions and structures.
We will start our mathematical discussion with the definition of scalar product — we
will assume the definitions of vector space, basis and linear independence are already
known by the reader.
We see that the first property is the linearity of the scalar product, while the second
property is usually referred to as conjugate-symmetry. Scalar products are also called
inner products, and are used to define many other tools on top of the vector space con-
sidered.
messages.downloaded_by
lOMoARcPSD|61948123
Proposition 2.1
For any scalar product vector space V , any scalar product satisfies the following prop-
erty:
∀u, v, w ∈ V, α, β ∈ C ⟨αu + βv, w⟩ = α ⟨u, w⟩ + β ⟨v, w⟩
In particular, the scalar product that we are going to use for our purposes is defined as
shown below.
Proposition 2.2
The Hermitian product is a scalar product.
Proof. It suffices to prove all the properties of scalar products provided in the definition.
Then, we see that
• linearity can be proved as follows
n
X n
X n
X
⟨u, αv + βw⟩ = ui (αvi + βwi ) = α ui vi + β ui vi = α ⟨u, v⟩ + β ⟨u, w⟩
i=1 i=1 i=1
messages.downloaded_by
lOMoARcPSD|61948123
From now on, when we refer to a “scalar product” we will refer to the Hermitian prod-
uct.
Proposition 2.3
Given a scalar product vector space V , for any two vectors u, v ∈ V it holds that
⟨u, v⟩ = ⟨v, u⟩
⟨u, v⟩ = ⟨v, u⟩
n
X
= ui vi
i=1
n
X
= ui vi
i=1
n
X
= vi · ui
i=1
= ⟨v, u⟩
We are finally ready to explain the “braket” notation that we used from the beginning
of the previous chapter. This notation was invented by the Nobel Prize in Physics Paul
Dirac, and it works as follows: first, observe that the Hermitian product can be rewritten
as follows
v1
.
⟨u, v⟩ = u1 · · · un ..
vn
To be precise, this product would yield a 1 × 1 matrix, which can be interpreted as a
scalar. Through Dirac notation, we will write
⟨u, v⟩ = ⟨u|v⟩
where ⟨u| is called bra, and |v⟩ is called ket (as in “bra-ket”). In other words, we have
that |v⟩ is just a regular column vector v ∈ V
v1
..
|v⟩ = .
vn
messages.downloaded_by
lOMoARcPSD|61948123
defined over some scalar product vector space V , while ⟨u| is a linear map that acts as
follows:
u1
..
⟨·| : V → V : . 7→ u1 · · · un
un
We observe that from this very definition we can already see the power of the Dirac
notation: by writing
⟨u| · |v⟩
we are writing the product between a row conjugated vector u and a column vector v,
which will ultimately yield 1 × 1 vector containing exatcly ⟨u, v⟩! Therefore, this allows
us to write that
⟨u| · |v⟩ = ⟨u|v⟩
where the equality holds if and only if u and v are linearly independent.
∀v ∈ V ||v|| = ||v||
messages.downloaded_by
lOMoARcPSD|61948123
Let’s see the Dirac notation in action. Consider an orthonormal basis {e1 , . . . , en } for
some scalar product vector space V ; by definition, we know that we can write any vector
u ∈ V as follows
Xn
u= αi ei
i=1
= ⟨ei |α1 e1 + . . . + αn en ⟩
= α1 ⟨ei |e1 ⟩ + . . . + αn ⟨ei |en ⟩
Xn
= αj ⟨ei |ej ⟩
j=1
n
X
= αj δij
j=1
= αi
Indeed, with the scalar product we can compute the projection of u onto the i-th vector
of the basis. Hence, we can rewrite the first equation as follows:
n
X n
X n
X
|u⟩ = αi |ei ⟩ = ⟨ei |u⟩ |ei ⟩ = |ei ⟩ ⟨ei |u⟩
i=1 i=1 i=1
In particular, from the last equality by linearity of the scalar product we have that
n
! n
X X
|u⟩ = |ei ⟩ ⟨ei | |u⟩ =⇒ I = |ei ⟩ ⟨ei |
i=1 i=1
messages.downloaded_by
lOMoARcPSD|61948123
Given a scalar product vector space V , and a vector sequence {vm }m∈N defined over
V , we say that the sequence converges weakly to a vector v ∈ V if
In other words, this type of convergence requires all projections of vm along any fixed
direction w to approach the projection of v. Differently, the next type of convergence is
more strict.
Given a scalar product vector space V , and a vector sequence {vm }m∈N defined over
V , we say that the sequence converges strongly to a vector v ∈ V if
lim ||v − vm || = 0
m→+∞
In fact, this type of convergence requires the actual vectors of the sequence to get close
in norm to v. We observe the following proposition.
Proposition 2.4
Given a scalar product vector space V , and a vector sequence {vm }m∈N defined over
V , if the sequence converges strongly to some vector v ∈ V , it holds that
• the sequence also converges weakly
• the scalar products defined over V are continuous, i.e.
Given a scalar product vector space V , and a vector sequence {vm }m∈N defined over
V , we say that the sequence is a Cauchy sequence if it holds that
For example, let’s consider the space R2 equipped with the Euclidean norm
p
||v|| = x2 + y 2
messages.downloaded_by
lOMoARcPSD|61948123
For example, the space Rn is a Hilbert space. Indeed, since every finite vector space of
size n is isomporphic to Rn , we can immediately derive the following proposition.
Proposition 2.5
Finite-dimensional vector spaces are always complete.
messages.downloaded_by
lOMoARcPSD|61948123
1 0
For instance, the following matrix S = is a linear operator whose adjoint is
0 i
1 0
†
S = . In fact, we have that
0 −i
†
1 0 v1 v1
⟨u|S v⟩ = u1 u2 = u1 u2 = u1 v1 − iu2 v2
0 −i v2 −iv2
and since
1 0 u1 u1
Su = = =⇒ ⟨Su| = u1 iu2
0 i u2 iu2
but because iu2 = i · u2 = −iu2 this implies that
v1
⟨Su|v⟩ = u1 −iu2 = u1 v2 − iu2 v2
v2
Proposition 2.6
For any operators A, B defined over some Hilbert space H, it holds that
1. (AB)† = B † A†
2. for any scalar z it holds that (zA)† = zA†
3. (A† )† = A
4. (A + B)† = A† + B †
5. A · B = A · B
Proposition 2.7
Given an operator A defined over a scalar product vector space, it holds that
a†ij = aji
This property is incredibly useful, because it implies that the adjoint operator of A is its
transposed conjugate matrix. Most notably, for any column vector |x⟩ it holds that
⟨x| = |x⟩†
which further underlines the power of Dirac notation.
messages.downloaded_by
lOMoARcPSD|61948123
The reason why we say that A is “positive” if it satisfies such property becomes obvious
if we choose v to be an eigenvector of A. Let v be an eigenvector of A associated to some
eigenvalue λ of A; then
0 ≤ ⟨v|Av⟩ = ⟨v| λ |v⟩ = λ ⟨v|v⟩
However, by definition of scalar product we know that ⟨v|v⟩ ≥ 0 for any v, which must
imply that λ ≥ 0 as well. In other words, if A is positive all of its eigenvalues must be
positive.
Theorem 2.2
If an operator A is positive, then it is Hermitian.
At the beginning of the previous chapter we said that all quantum gates are unitary
transformations, but we did now provide a definition of unitarity.
In other words, U is unitary if and only if its adjoint operator is also its inverse. An
interesting characterization of unitary transformations is proved in the theorem right
after the following lemma.
Lemma 2.1
Given x, y ∈ H, if ⟨x|z⟩ = ⟨y|z⟩ for all z ∈ H, then x = y.
⟨x|z⟩ = ⟨y|z⟩
⇐⇒ ⟨x|z⟩ − ⟨y|z⟩ = 0
⇐⇒ ⟨x − y|z⟩ = 0
However, if this is true for every vector z ∈ H it means that the vector x − y is orthogonal
to every vector in H, which must imply that x − y is the 0 vector, thus
x − y = 0 ⇐⇒ x = y
messages.downloaded_by
lOMoARcPSD|61948123
Proof. Let U be a unitary operator, and fix any two vectors x, y ∈ H; then, we have that
Proof of the Claim. Since U is required to be surjective we only need to prove that
it is injective. By way of contradiction, suppose that U is not injective, i.e. there are
distinct x1 , x2 ∈ H such that U x1 = U x2 . Then, this implies that
U x1 = U x2 ⇐⇒ U (x1 − x2 ) = 0
⟨x1 − x2 |x1 − x2 ⟩ = 0 ⇐⇒ x1 − x2 = 0 ⇐⇒ x1 = x2
which is a contradiction .
Now, fix a vector y ∈ H; by surjectivity of U we know that
∃z ∈ H y = U z
messages.downloaded_by
lOMoARcPSD|61948123
⟨x|U † y⟩ = ⟨U x|y⟩
= ⟨U x|U z⟩
= ⟨x|z⟩
= ⟨x|U −1 y⟩
∀y ∈ H ⟨x|U † y⟩ = ⟨x|U −1 y⟩ =⇒ U † y = U −1 y
In particular, we observe that the second property of this proposition is very interesting:
the preservation of the scalar product, i.e. the property for which
means that the operator U does not change the geometric relationships between vectors
— i.e. their lengths and angles remain the same.
Proposition 2.8
Proposition 2.9
messages.downloaded_by
lOMoARcPSD|61948123
Proposition 2.10
If U is a unitary operator, then the rows and the columns of U are orthonormal.
Proof. Let U be a unitary operator, therefore U preserves the scalar product. In partic-
ular, we observe that
∀i, j ⟨U ei |U ej ⟩ = ⟨ei |ej ⟩ = δij
and since U ei and U ej are the i-th and j-th columns of U respectively, this immediately
proves that U ’s columns are orthonormal. To prove the same result for the rows, we first
observe that U T ei and U T ej are the i-th and j-th rows of U , respectively. However, by
the previous proposition we know that U is unitary if and only if U T is unitary, which
means that
∀i, j ⟨U T ei |U T ej ⟩ = ⟨ei |ej ⟩ = δij
which immediately concludes the proof.
Proposition 2.11
If A and B are two unitary operators, then AB is a unitary operator.
Clearly, from their definition we immediately see that both self-adjoint and unitary oper-
ators are normal.
Proposition 2.12
For any operator U in a Hilbert space H, if B is a base of H it holds that
X
U= U |b⟩ ⟨b|
b∈B
messages.downloaded_by
lOMoARcPSD|61948123
Proof. The formula derives directly from the resolution of the identity, and the linearity
of operators of Hilbert spaces
U =U ·I
X
=U· |b⟩ ⟨b|
b∈B
X
= U |b⟩ ⟨b|
b∈B
Therefore, if we know how U acts component-wise, we can reconstruct the operator acting
on the whole space as such.
To conclude this section, we introduce a definition that will be very useful in the next
chapter.
In other words, the trace of a matrix is the sum of the elements on its diagonal.
Proposition 2.13
In particular, we observe that the last property follows trivially from the cyclic prop-
erty:
tr(U AU † ) = tr(U † U A) = tr(IA) = tr(A)
However, most importantly, the following property holds.
messages.downloaded_by
lOMoARcPSD|61948123
Proposition 2.14
Proof. First, we observe that the definition of the trace can be rewritten in terms of the
Dirac notation n n
X X
tr(X) = xii = ⟨ei |X|ei ⟩
i=1 i=1
Proposition 2.15
Given a Hilbert space H, for any two vectors v, w ∈ H it holds that
Proof. From the same observation pointed out in the previous proof we see that
n
X
tr(|v⟩ ⟨w|) = ⟨ei |v⟩ ⟨w|ei ⟩
i=1
n
X
= ⟨w|ei ⟩ ⟨ei |v⟩
i=1
n
!
X
= ⟨w| |ei ⟩ ⟨ei | |v⟩
i=1
= ⟨w|I|v⟩
= ⟨w|v⟩
messages.downloaded_by
lOMoARcPSD|61948123
which should not come as a surprise anyway, since the elements on the diagonal of |v⟩ ⟨v|
are exactly the elements of the sum in the scalar product of ⟨v|v⟩. We will discuss the
importance of these equalities in the next chapter.
Proposition 2.16
tr(A† ) = tr(A)
messages.downloaded_by
lOMoARcPSD|61948123
messages.downloaded_by
lOMoARcPSD|61948123
2.3. Projectors
2.3 Projectors
Next, we are going to discuss projectors, which play a very important role in quantum
mechanics and quantum computing. We saw how scalar products are able to perform
projections over arbitrary directions, in fact we will use the Dirac notation to define precise
operators for our purposes. But as always, we first some preliminary definitions.
∀v ∈ V, w ∈ W ⟨v|w⟩ = 0
Given a scalar product vector space U , and a linear subspace V ⊂ U , the orthogonal
complement of V is defined as follows:
V ⊥ := {u ∈ U | ∀v ∈ v ⟨u|v⟩ = 0}
messages.downloaded_by
lOMoARcPSD|61948123
2.3. Projectors
Then, if we call
uV ⊥ := u − uV
we see that we can actually show that that uV and uV ⊥ are orthogonal to each other —
we will prove this fact in ??. With this observation, we can finally define the projector
operators.
Most importantly, given the map in the definition we have that the projector operator PV
is defined as follows n
X
PV := |fi ⟩ ⟨fi |
i=1
PV ⊥ : H → V ⊥ : u 7→ uV ⊥ := u − uV
∀u ∈ H u ∈ V ⇐⇒ PV u = u
and that
∀u ∈ H u ∈ V ⊥ ⇐⇒ PV u = 0
messages.downloaded_by
lOMoARcPSD|61948123
2.3. Projectors
Proof. We first prove the direct implication. Suppose that PV is the projector of a closed
subspace V ⊂ H, meaning that PV can be written as
n
X
PV = |fi ⟩ ⟨fi |
i=1
messages.downloaded_by
lOMoARcPSD|61948123
2.3. Projectors
Given a Hilbert space H, and two topologically closed subspaces V, W ⊂ H, we say that
PV and PW are orthogonal if it holds that V ⊥W . Now, fix a vector u ∈ H; by definition
PV u is a vector that lies inside V , therefore it holds that
PW (PV u) = 0
PW PV = PV PW = 0
Proposition 2.17
If P and Q are two orthogonal projectors, then P + Q is a projector.
Proof. Let {fi }ni=1 and {gi }ni=1 be the bases that define
n
X n
X
P := |fi ⟩ ⟨fi | Q := |gi ⟩ ⟨gi |
i=1 i=1
Then, by the previous theorem it suffices to show that P + Q is both idempotent and
Hermitian. To prove idempotency we see that
n n
! n n
!
X X X X
(P + Q)2 = |fi ⟩ ⟨fi | + |gi ⟩ ⟨gi | |fj ⟩ ⟨fj | + |gj ⟩ ⟨gj |
i=1 i=1 j=1 j=1
X X X X
= |fi ⟩ ⟨fi |fj ⟩ ⟨fj | + ⟨fi ⟩ ⟨fi |gj ⟩ ⟨gj | + |gi ⟩ ⟨gi |fj ⟩ ⟨fj | + |gi ⟩ ⟨gi |gj ⟩ ⟨gj |
i,j i,j i,j i,j
X X
= |fi ⟩ δi,j ⟨fj | + |gi ⟩ δi,j ⟨gj |
i,j i,j
Xn n
X
= |fi ⟩ ⟨fi | + |gj ⟩ ⟨gj |
i=1 j=1
=P +Q
messages.downloaded_by
lOMoARcPSD|61948123
2.3. Projectors
We observe that we used orthogonality to remove the inner sums in the third step. More-
over, Hermiticity can be easily proven by linearity of the adjoint:
n n
!†
X X
(P + Q)† = |fi ⟩ ⟨fi | + |gi ⟩ ⟨gi |
i=1 i=1
n
X X n
= (|fi ⟩ ⟨fi |)† + (|gi ⟩ ⟨gi |)†
i=1 i=1
n
X n
X
= |fi ⟩ ⟨fi | + |gi ⟩ ⟨gi |
i=1 i=1
=P +Q
The importance of the next theorem cannot be understated, and it will be used extensively
throughout the notes to prove various results.
which seems to imply that Pλi = |λi ⟩ ⟨λi |, i.e. the projector onto the i-th eigenspace of M
is |λi ⟩ ⟨λi |. This is a slight notation abuse, and an example will make it clear. Consider
the following matrix:
2 0 0
A = 0 2 0
0 0 5
It is easy to see that the eigenvalues of A are only 2 and 5, however 2 is 2-fold degenerate!
Indeed, by solving
M |v⟩ = 2 |v⟩
we get an eigenspace of dimension 2, and we can choose {|e1 ⟩ , |e2 ⟩} as orthonormal eigen-
basis; similarly, we find that {|e3 ⟩} is an eigenbasis of the second eigenspace of dimension
messages.downloaded_by
lOMoARcPSD|61948123
⊗:V ×W →V ⊗W
such that for every vector space X, and a bilinear map f : V × W → X there exists a
unique linear map f˜ : V ⊗ W → X with
f = f˜ ◦ ⊗
f
V ×W X
⊗
f˜
V ⊗W
messages.downloaded_by
lOMoARcPSD|61948123
This definition is quite rigorous and dense, but a concrete example will make it clear.
First, we recall that a function f is linear if it holds that
• f (x + y) = f (x) + f (y)
• f (αx) = αf (x)
Then, for a function to be bilinear (or multilinear, in general) we require f to be linear
in both of its arguments:
• f (x + x′ , y) = f (x, y) + f (x′ , y)
• f (x, y + y ′ ) = f (x, y) + f (x, y ′ )
• f (αx, y) = αf (x, y) = f (x, αy)
From this definition, we immediately point out that the tensor product ⊗ satisfies
• (v + v ′ ) ⊗ w = v ⊗ w + v ′ ⊗ w
• v ⊗ (w + w′ ) = v ⊗ w + v ⊗ w′
• (αv) ⊗ w = v ⊗ (αw)
We may call the first two as distributive properties. Let’s consider an example we already
presented in the first chapter of the notes.
At the start of our discussion we “defined” the
a c
tensor product between two vectors and as follows
b d
ac
a c ad
⊗ :=
b d bc
bd
⊗ : R2 × R2 → R2 ⊗ R2
Now, we observe that the output space V ⊗ W is a vector space that has
BV ⊗W := {fi ⊗ gj | fi ∈ BV , gj ∈ BW }
messages.downloaded_by
lOMoARcPSD|61948123
indeed V and W can have different dimensions. For instance, a pair of vectors (v, w) ∈
R2 × R3 lies in a 5-dimensional space, since
messages.downloaded_by
lOMoARcPSD|61948123
Consider any two vectors v ∈ V and w ∈ W , and suppose that n := dim V and m :=
dim W . Then, we can describe them in terms of BV and BW , respectively, as follows:
n
X m
X
v= αi fi w= βj gj
i=1 j=1
which indeed is a vector that lies inside V ⊗ W since (fi ⊗ gj ) ∈ BV ⊗W . Then, if the basis
of choice of the output set X is the canonical basis, we observe that
n Xm
!
X
φ(v ⊗ w) = φ αi βj (fi ⊗ gj )
i=1 j=1
n
XX m
= αi βj φ(fi ⊗ gj )
i=1 j=1
Xn X m
= αi βj e(i−1)m+j
i=1 j=1
α1 β1
α1 β2
..
.
= α1 βm
∈ Rn·m
α β
2 1
.
..
αn βm
where the last column vector contains all the pairs (αi , βj ) — note that Rn·m ̸= Rn×m ,
as the latter denotes the space of real-valued matrices of dimension n × m. Again, we
underline that we arbitrarily chose the space Rn·m , but we could have chosen any space
of dimension n · m as output — even Rn×m ! A concrete example will clarify: consider
two
a
spaces V = R2 and W = R2×2 . Then, any element v ∈ R2 has the form v = while
b
messages.downloaded_by
lOMoARcPSD|61948123
c d
any matrix of A ∈ R 2×2
looks like A = . If we want to compute v ⊗ A, we can
e f
project it onto any space that has dimension
dim(R2 ⊗ R2×2 ) = dim R2 · dim R2×2 = 2 · 4 = 8
Here are some examples of the possible outputs of v ⊗ A depending on the choice of the
output space:
ac
ad
ae ac bc
af ac ad ae af ad
bd
∈ R8 ∈ R2×4 ∈ R4×2
bc bc bd be bf ae
be
bd af bf
be
bf
messages.downloaded_by
lOMoARcPSD|61948123
it holds that
ae af be bf
aB bB ag ah bg bh
A⊗B = =
cB dB ce cf de df
cg ch dg dh
We are finally ready to provide the formulation of the tensor product we will adopt for
our purposes.
Given two matrices A ∈ Fm×n and B ∈ Fp×q defined over some field F, the Kronecker
product between A and B defines A ⊗ B as follows
a11 B . . . a1n B
A ⊗ B = ... ..
.
.. ∈ Fmp×nq
.
am1 B . . . amn B
which matches our previous results. From now on, we will assume that the output of
any tensor product is in this form. Most importantly, through the Kronecker product the
following properties hold, which will be used extensively throughout these notes.
Proposition 2.18
For any field F, given two matrices A and B and two vectors v and w such that
A ∈ Fm×n B ∈ Fp×q v ∈ Fn w ∈ Fq
it holds that
(A ⊗ B)(v ⊗ w) = Av ⊗ Bw
messages.downloaded_by
lOMoARcPSD|61948123
2.5. Exercises
Proposition 2.19
For any two matrices A and B defined over a Hilbert space, it holds that
(A ⊗ B)† = A† ⊗ B †
Proposition 2.20
For any four vectors |a⟩ , |c⟩ ∈ H1 and |b⟩ , |d⟩ ∈ H2 of two Hilbert spaces H1 and H2 ,
it holds that
⟨a ⊗ b|c ⊗ d⟩ = ⟨a|c⟩ ⟨b|d⟩
U ⊗n = U ⊗ . . . ⊗ U
| {z }
n times
2.5 Exercises
Problem 2.1
Given n qubits {qi }ni=1 , show that
n
O
qi = 1
i=1
Solution. First, we observe that by Proposition 2.20 it immediately follows that for any
set of vectors {xi }ni=1 and {yi }ni=1 it holds that
n
Y
⟨a|b⟩ = ⟨xi |yi ⟩
i=1
messages.downloaded_by
lOMoARcPSD|61948123
2.5. Exercises
Problem 2.2
Let {fi }ni=1 be an orthonormal basis of a vector space V , and fix a vector u ∈ V ; then,
consider n
X
uV := ⟨fi |u⟩ |fi ⟩
i=1
Prove that the definition of uV does not depend on the choice of {fi }ni=1
Solution. By way of contradiction, suppose that there is an orthonormal basis {gi }ni=1 of
V such that n n
X X
⟨fi |u⟩ |fi ⟩ ̸= ⟨gi |u⟩ |gi ⟩
i=1 i=1
messages.downloaded_by
lOMoARcPSD|61948123
2.5. Exercises
Problem 2.3
Show that if a matrix P is both idempotent and Hermitian, it must be a projector.
P 2 v = P (P v) = P (λv) = λP v = λ(λv) = λ2 v
messages.downloaded_by
lOMoARcPSD|61948123
2.5. Exercises
From this claim, we immediately obtain that each λi is either 0 or 1, which means that
its spectral decomposition can be written as
X
P = Pλ j
j
for some non-zero eigenvalues λj of P . Finally, since Pλj are projectors onto different
eigenspaces they are orthogonal between each other, which means that the statement
follows immediately from Proposition 2.17.
Problem 2.4
Given a unitary matrix U , show that U ⊗n is still unitary.
Solution. The property follows immediately from Proposition 2.18 and Proposition 2.19,
since
n
! n !†
O O
U ⊗n (U ⊗n )† = U U
i=1 i=1
n
! n
!
O O
†
= U U
i=1 i=1
n
O
= UU†
i=1
n
O
= I
i=1
=I
Problem 2.5
Prove the triangular inequality.
Solution. Consider two vectors u and v in some scalar product vector space; we must
show that
||u + v|| ≤ ||u|| + ||v||
First, we observe that
messages.downloaded_by
lOMoARcPSD|61948123
2.5. Exercises
Problem 2.6
Show that if an operator is unitary, it must be linear.
Solution. Let U be a unitary transformation defined over some Hilbert space H; by The-
orem 2.3 we know that
∀x, y ∈ H ⟨U x|U y⟩ = ⟨x|y⟩
Fix three vectors x, y, z ∈ H and two complex values α, β ∈ C; then, by definition of
scalar product we have that
⟨U (αx + βy)|z⟩ = ⟨αx + βy|U † z⟩
= α ⟨x|U † z⟩ + β ⟨y|U † z⟩
= ⟨αU x|z⟩ + ⟨βU y|z⟩
= ⟨αU x + βU y|z⟩
Then, from the previous observation we have
∀x, y, z ∈ H, α, β ∈ C ⟨U (αx + βy)|z⟩ = ⟨αU x + βU y|z⟩
and by Lemma 2.1 we conclude that
U (αx + βy) = αU x + βU y
meaning that U is indeed linear.
messages.downloaded_by
lOMoARcPSD|61948123
2.5. Exercises
Problem 2.7
Prove the Spectral decomposition theorem.
Solution. TODO da
finire
la di-
Now we will prove the converse implication. Let A be an operator that can be written as rect,
decom-
X menta
A= λi Pλi
i
and since projectors onto different eigenspaces are orthogonal between each other we have
that
XX
A† A = λi λj Pλi Pλj
i j
X
= λi λi Pλ2i
i
X
= |λi |2 Pλi
i
Finally, it is easy to see that computing AA† would yield the same result, proving that A
is indeed normal.
Problem 2.8
Show that for any two complex numbers z, w ̸= 0 it holds that
z |z|
=
w |w|
Solution. Let z, w ̸= 0 bet two complex numbers, and consider their polar forms
z = reiθ w = seiφ
where θ, φ ∈ R and r = |z|, s = |w|. Most importantly, we observe that r, s > 0 since
messages.downloaded_by
lOMoARcPSD|61948123
2.5. Exercises
z reiθ
=
w seeφ
r i(θ−φ)
= ·e
s
r
= · ei(θ−φ) (since r, s > 0)
s
|z|
= (∀α ∈ R eiα = 1)
|w|
Problem 2.9
Show that uV and uV ⊥ are orthogonal.
Problem 2.10
TODO
messages.downloaded_by
lOMoARcPSD|61948123
Now that we defined Hilbert spaces and their operators in great detail, we can finally
present we needed this mathematical foundations in order to progress: quantum mechanics
is developed over Hilbert spaces with countable bases, and quantum computing works
with finite-dimensional Hilbert spaces. In particular, these are the four fundamental
postulates of quantum mechanics.
As we saw at the beginning of the previous chapter, |ψ⟩ is always considered to be nor-
malized. We observe that different physical systems of different types live in different
Hilbert spaces.
messages.downloaded_by
lOMoARcPSD|61948123
We observe that the Schrödinger equation is a first-order linear differential equation, and
it is composed by the following elements:
• v(t) which is the state vector at time t (a vector in a Hilbert space)
• H which is the system Hamiltonian, a self-adjoint operator that describes the total
energy of the system
The solution of the Schrödinger equation is
(assuming H does not depend on time). However, we recall that H is a matrix, so we are
raising e to the power of a matrix, an operation that is defined by the power series of the
exponential as follows
∞
X An
eA =
n=0
n!
This definition implies some interesting properties.
Proposition 3.1
For any operator A it holds that
† †
eA = eA
messages.downloaded_by
lOMoARcPSD|61948123
= U −1
which proves that U is unitary! This is a crucial characteristic for quantum mechanics:
since U is unitary, we know that it preserves the scalar product by Theorem 2.3, therefore
it also preserves probabilities and norms. This is why we say that evolution in quantum
systems — or quantum evolution, for short — is unitary. Indeed, the second postulate is
sometimes formulated equivalently as follows.
Pr[A = λ | v] = ⟨v|Pλ v⟩
We can actually explain why we choose that particular scalar product to be the probability.
messages.downloaded_by
lOMoARcPSD|61948123
Since by convention any quantum state is normalize, i.e. ||v|| = 1, it holds that
1 = ||v||2
= ⟨v|v⟩
* m m
+
X X
= Pλ i v P λj v
i=1 j=1
m
XX m
= ⟨Pλi v|Pλj v⟩
i=1 j=1
Now, since each Pλi is a projector, we know that when i ̸= j it holds that Pλi Pλj = 0,
therefore by Hermiticity of projectors we have that
• if i ̸= j then
⟨Pλi v|Pλj v⟩ = ⟨v|Pλi Pλj v⟩ = ⟨v|0v⟩ = 0
• if i = j then
⟨Pλi v|Pλj v⟩ = ⟨Pλi v|Pλi v⟩ = ||Pλi v||2
Hence, we define
Pr[A = λi | v] := ||Pλi v||2
such that m m
X X
Pr[A | v] = Pr[A = λi | v] = ||Pλi v||2 = ||v||2 = 1
i=1 i=1
which also means that our probabilities will add up to 1 automatically. Finally, we can
rewrite this proability as follows (we will drop the index of the eigenvalue):
Pr[A = λ | v] = ⟨Pλ v|Pλ v⟩
= ⟨v|Pλ† Pλ v⟩
= ⟨v|Pλ2 v⟩ (by Hermiticity)
= ⟨v|Pλ Pλ v⟩
= ⟨v|Pλ v⟩
This formulation was refined in 1926 by Max Born [Hal13], when he derived the following
property.
messages.downloaded_by
lOMoARcPSD|61948123
Proof. By the Theorem 2.5 it holds that the set of all the eigenvectors |λ⟩ of any operator
can be expanded to always form an orthonormal basis of the complete Hilbert space.
Hence, the idea is to implicitly construct a self-adjoint operator A whose eigenvalues are
precisely the possible values in which |ψ⟩ might collapse into. In other words, we want
to construct a self-adjoint operator whose Spectral decomposition is exactly defined by
{λ1 , . . . , λn } Hence, if |ψ⟩ is defined as
n
X
|ψ⟩ = αn |λi ⟩
i=1
Thus, the probability that by |ψ⟩ it collapses to some |λ⟩ ∈ {λ1 , . . . , λn } can be rewritten
as follows:
Pr[measure(|ψ⟩ = |λ⟩)] = Pr[Aψ = λ| |ψ⟩]
= ⟨ψ|Pλ ψ⟩ (by the Measurement postulate)
= ⟨ψ|λ⟩ ⟨λ|ψ⟩
= |⟨ψ|λ⟩|2
and we want to know what is the probability that |ψ⟩ collapses to |0⟩ after a measurement,
we simply have that
This formulation of the probability of measurements will be used extensively for our
purposes, and allows us to avoid the description of the matrix Aψ completely.
Before presenting to the next postulate, another very important operator that is frequently
utilized in quantum mechanics is the expected value of a matrix. Given an observable
A, we define the expected value of A as the average eigenvector we may obtain after a
measurement m
X
E[A|v] = λi Pr[A = λi | v]
i=1
messages.downloaded_by
lOMoARcPSD|61948123
We usually denote the expected value of the operator A given that we are in state |ψ⟩
as ⟨A⟩ψ (or ⟨A⟩ if the context is clear enough). Moreover, we have the following prop-
erty.
⟨A⟩ψ = ⟨ψ|Aψ⟩
Corollary 3.1
In other words, the last postulate states that the Hilbert space of a composite system is
the tensor product of the Hilbert spaces of its subsystems. This postulate immediately
tells us something important about entangled quantum systems: if a system C defined
messages.downloaded_by
lOMoARcPSD|61948123
over a Hilbert space HC represents a quantum state, there is no pair of systems A and B
defined over HA and HB such that HC = HA ⊗ HB .
Speaking of tensor products, when operators can be factored out into smaller operators
of smaller systems we obtain linearity of expectations w.r.t. the tensor product.
Proposition 3.3
Given an operator O that can be factored out as O = A ⊗ B, if the current state |ψ⟩
is not entangled it holds that
⟨O⟩ = ⟨A⟩ · ⟨B⟩
where |ψ⟩ = |ψA ⟩ ⊗ |ψB ⟩, which we know exists because we are assuming that |ψ⟩ is not
entangled.
Let the following be the spectral decompositions of A and B, respectively:
m
X m
X
A= λA
i Pλ A
i
, B= λB
j Pλ B
j
i=1 j=1
Then, by computing the tensor product between A and B, we immediately obtain the
spectral decomposition of O:
X
O =A⊗B = λA B
i λj (PλA
i
⊗ PλBj )
i,j∈[m]
i λj for i, j ∈
Hence, the possible values O might be observed into are all the products λA B
messages.downloaded_by
lOMoARcPSD|61948123
m2
X
⟨ψ|Oψ⟩ = λk Pr[O = λk | |ψ⟩]
k=1
m X
X m
= λA B A B
i λj Pr[A ⊗ B = λi λj | |ψA ⟩ ⊗ |ψB ⟩]
i=1 j=1
Xm X m
= λA B
i λj ⟨ψA ⊗ ψB |PλA
i
⊗ PλBj |ψA ⊗ ψB ⟩
i=1 j=1
Xm X m
= λA λ
i j
B
⟨ψA |P A
λi |ψ A ⟩ · ⟨ψ B |P B
λj |ψB ⟩
i=1 j=1
m m
!
X X
= λA
i ⟨ψA |PλA
i
|ψA ⟩ λB
j ⟨ψB |PλB
j
|ψB ⟩
i=1 j=1
m
! m
!
X X
= λA
i ⟨ψA |PλA
i
|ψA ⟩ · λB
j ⟨ψB |PλB
j
|ψB ⟩
i=1 j=1
This result should not come as a surprise, since for any two distributions X and Y we
know that
E[XY ] = E[X] · E[Y ]
only if X and Y are independent. Indeed, by assuming that O and |ψ⟩ can be factorized,
we are assuming that the two underlying subsystems HA and HB — in which |ψA ⟩ and
A, and |ψB ⟩ and B live, respectively — are “independent” in the sense that they are not
entangled !
messages.downloaded_by
lOMoARcPSD|61948123
We observe that the completeness equation expresses the fact that probabilities of the
outcomes sum to one:
X X
†
Pr[M = m | |ψ⟩] = ⟨ψ| Mm Mm |ψ⟩
m m
!
X
†
= ⟨ψ| Mm Mm |ψ⟩
m
= ⟨ψ|I|ψ⟩
= ⟨ψ|ψ⟩
=1
messages.downloaded_by
lOMoARcPSD|61948123
We observe that ρ is a matrix, and this is the reason why it is interchangeably called
density matrix. Nevertheless, this matrix is important because it turns out that all the
postulates of quantum mechanics we presented so far can be reformulated equivalently in
terms of the density operator.
Suppose that we have closed quantum system described by some ensamble {pi , |ψi ⟩}N
i=1
that unitarily evolves following the unitary operator U described earlier
i
U (t2 , t1 ) = e− ℏ H(t2 −t1 )
This means that the system is in state |ψi ⟩ with probability pi , and after the evolution has
occurred the system will be in the state U |ψi ⟩ still with probability pi . More specifically,
we have that
U
|ψi ⟩ −→ U |ψi ⟩
which also directly implies that
U
(|ψi ⟩)† = ⟨ψi | −→ (U |ψi ⟩)† = ⟨ψi | U †
messages.downloaded_by
lOMoARcPSD|61948123
Therefore, after the system has evolved we must update its density operator by applying
U to each |ψi ⟩
N N
U
X X
ρ= pi |ψi ⟩ ⟨ψi | −→ pi U |ψi ⟩ ⟨ψi | U † = U ρU †
i=1 i=1
Not surprisingly, this shows that by linearity we just need to apply U (and U † ) to the
matrix directly in order to consider all the evolutions. The function that maps
ρ 7→ U ρU †
is called superoperator.
Measurements can be also easily described through the density operator. Consider the
General measurement postulate, and suppose we perform a measurement described by
measurement operators Mm . If the initial state was |ψi ⟩, then we have that
†
Pr[M = m| |ψi ⟩] = ⟨ψi |Mm Mm |ψi ⟩
†
= tr(Mm Mm |ψi ⟩ ⟨ψi |) (by Proposition 2.14)
Then, thanks to Proposition 2.13, by computing the total probability we obtain that
N
X
Pr[M = m] = pi Pr[M = m | |ψi ⟩]
i=1
N
X
†
= pi tr(Mm Mm |ψi ⟩ ⟨ψi |)
i=1
XN
†
= tr(pi Mm Mm |ψi ⟩ ⟨ψi |)
i=1
N
!
X
†
= tr pi Mm Mm |ψi ⟩ ⟨ψi |
i=1
N
!
X
†
= tr Mm Mm pi |ψi ⟩ ⟨ψi |
i=1
†
= tr(Mm Mm ρ)
This shows that the basic postulates of quantum mechanics related to unitary evolution
and measurement can be rephrased in terms of density operators. However, we can do
better: we will proivde a characterization of the density operator that does not rely on
the idea of state vectors at all. But first, as usual, we need some definitions. When a
quantum system is an a known exact state |ψ⟩, the system is said to be in a pure state,
and in this case its density matrix operator is simply
ρ = |ψ⟩ ⟨ψ|
Otherwise, if the state is now known and the system is described by an ensamble of states,
we say that ρ is in a mixed state. More specifically, we can distinguish between pure
and mixed states as follows.
messages.downloaded_by
lOMoARcPSD|61948123
Proposition 3.4
Proof. Consider a density matrix describing a pure state ρ = |ψ⟩ ⟨ψ|; by the properties of
the trace it holds thta
tr(ρ2 ) = tr(ρ |ψ⟩ ⟨ψ|)
= ⟨ψ|ρψ⟩
= ⟨ψ|ψ⟩ ⟨ψ|ψ⟩
= |⟨ψ|ψ⟩|2
=1
Differently, consider a density matrix
N
X
ρ= pi |ψi ⟩ ⟨ψi |
i=1
describing a mixed state of some ensamble {pi , |ψi ⟩}Ni=1 . Then, through algebraic manip-
ulation we obtain that
N
! N !!
X X
tr(ρ2 ) = tr pi |ψi ⟩ ⟨ψi | pj |ψj ⟩ ⟨ψj |
i=1 j=1
N X
N
!
X
= tr pi pj |ψi ⟩ ⟨ψi |ψj ⟩ ⟨ψj |
i=1 j=1
N X
X N
= pi pj ⟨ψi |ψj ⟩ tr(|ψi ⟩ ⟨ψj |)
i=1 j=1
N X
X N
= pi pj ⟨ψi |ψj ⟩ ⟨ψj |ψi ⟩ (by Proposition 2.15)
i=1 j=1
N X
X N
= pi pj ⟨ψi |ψj ⟩ ⟨ψi |ψj ⟩
i=1 j=1
N X
X N
= pi pj |⟨ψi |ψj ⟩|2
i=1 j=1
Without loss of generality, we observe that we can assume all the |ψi ⟩’s in the ensamble
that ρ describes are distinct — up to changing the probabilities accordingly. Then, this
means that for any i, j ∈ [N ]
|⟨ψi |ψj ⟩|2 = 1 ⇐⇒ |ψi ⟩ = eiθ |ψj ⟩
for some phase θ. In other words, the norm of the projection of ψj onto ψi is equal to
1 if and only if |ψi ⟩ and |ψj ⟩ are the same state up to a global phase. However, since
messages.downloaded_by
lOMoARcPSD|61948123
qubits cannot be distinguished up to a global phase, we can assume that the ensamble ρ
describes does not contain such pair of states. This implies that
Moreover, since the state is mixed, we can also assume without loss of generality that for
all i ∈ [N ] it holds that pi ̸= 0, 1. From these observations, we conclude that
N X
X N
2
tr(ρ ) = pi pj |⟨ψi |ψj ⟩|2
i=1 j=1
N X
X N
< pi pj
i=1 j=1
N
! N
!
X X
= pi pj
i=1 i=1
N
!2
X
= pi
i=1
=1
Proof. We first prove the first implication. Consider the density operator
N
X
ρ= pi |ψi ⟩ ⟨ψi |
i=1
messages.downloaded_by
lOMoARcPSD|61948123
Now we can proceed to prove the converse implication. Suppose that ρ is any operator that
satisfies the conditions of the statement. In particular, since ρ is positive by Theorem 2.2
we know that ρ is Hermitian, which implies that it admits a spectral decomposition
X
ρ= λj |λj ⟩ ⟨λj |
j
We can write its spectral decomposition in this fashion by repeating the degenerate eigen-
values multiple times as discussed under Theorem 2.7. Let P and D such that ρ is
diagonalizable, i.e.
ρ = P DP −1
and in particular D has the eigenvalues of ρ on its diagonal. Then, we can use the
assumption that tr(ρ) = 1 to conclude that
1 = tr(ρ)
= tr(P DP −1 )
= tr(P −1 P D)
= tr(D)
X
= λj
j
messages.downloaded_by
lOMoARcPSD|61948123
which means that the sum of the eigenvalues of ρ adds up to 1. Finally, by positivity
of ρ we know that λj ≥ 0 for each λj , which means that the eigenvalues behave exactly
as probabilities. This proves that ρ is the density matrix of the system described by the
ensamble
{λj , |λj ⟩ ⟨λj |}j
Proof. The proof follows immediately from the previous theorem. In fact, since each ρi
is a density matrix, by the previous theorem they must be positive, therefore for any
|v⟩ ∈ H it holds that !
XN N
X
⟨v| pi ρi |v⟩ = pi ⟨v|ρi v⟩ ≥ 0
i=1 i=1
Moreover, the previous theorem also states that tr(ρi ) = 1 for each density matrix, which
shows that !
XN Xn N
X
tr pi ρi = pi tr(ρi ) = pi = 1
i=1 i=1 i=1
Therefore, since the weighted sum is positive and its trace is equal to 1, the previous
theorem implies that it is also a density matrix.
Given all we just discussed, we can finally rephrase the postulates through the density
operator.
Associated to any isolated physical system is a Hilbert space known as the state space
of the system, and the system is completely described by its density operator, i.e. any
positive operator ρ with trace one acting on the state space of the system.
messages.downloaded_by
lOMoARcPSD|61948123
The sate space of a composite physical system is the tensor product of the state spaces
of the component physical systems. That is, given n systems such that the i-th system
is in state ρi , the joint state of the total system is
n
O
ρ= ρi
i=1
As a final note, observe that knowing the density matrix of a system tells us nothing
about the ensamble of states of the systems, because different ensambles can generate the
same density matrix. For instance, the matrix
1 1 0
ρ=
2 0 1
but it would be a mistake to make this conclusion because ρ can be also written for
examòle as follows
1 1 1 1 1 −1
ρ= +
4 1 1 4 −1 1
which describes a completely different ensamble!
messages.downloaded_by
lOMoARcPSD|61948123
Given two quantum systems A and B whose composite system is described by ρAB , we
define the reduced density operator of A as follows
ρA := trB (ρAB )
ρAB = τ ⊗ σ
where τ is a density operator for A, and σ is a density operator for B. First, suppose that
τ and σ represent pure states; then, the connection with the reduced density operator is
evident by computing ρA
ρA = trB (ρ)
= trB (τ ⊗ σ)
= τ tr(σ) (since they represent pure states)
=τ (by Theorem 3.2)
messages.downloaded_by
lOMoARcPSD|61948123
ρA = trB (ρ)
= trB (τ ⊗ σ)
N
! N
!!
X X
= trB pi |ϕi ⟩ ⟨ϕi | ⊗ qj |ψj ⟩ ⟨ψj |
i=1 j=1
n X
N
!
X
= trB pi qj (|ϕi ⟩ ⟨ϕi | ⊗ |ψj ⟩ ⟨ψj |)
i=1 j=1
N X
X N
= pi qj trB (|ϕi ⟩ ⟨ϕi | ⊗ |ψj ⟩ ⟨ψj |)
i=1 j=1
N X
X N
= pi qj |ϕi ⟩ ⟨ϕi | tr(|ψj ⟩ ⟨ψj |)
i=1 j=1
N
! N
!
X X
= pi |ϕi ⟩ ⟨ϕi | qj tr(|ψj ⟩ ⟨ψj |)
i=1 j=1
N
! N
!
X X
= pi |ϕi ⟩ ⟨ϕi | tr qj |ψj ⟩ ⟨ψj |
i=1 j=1
= τ tr(σ)
=τ
A more interesing example, however, is an entangled system. For instance, let’s consider
the bell state
|00⟩ + |11⟩
|Φ+ ⟩ := √
2
We can compute the density operator of this system by following the definition
ρ = |Φ+ ⟩ ⟨Φ+ |
|00⟩ + ⟨11| |00⟩ + ⟨11|
= √ √
2 2
|00⟩ ⟨00| + |11⟩ ⟨00| + |00⟩ ⟨11| + |11⟩ ⟨00|
=
2
As we already know, since this system is entangled there is no pair of subsystems A and B
that can produce it as a composite tensor product. Nevertherless, let’s see what happens
messages.downloaded_by
lOMoARcPSD|61948123
3.3. Exercises
ρA = trB (ρ)
|00⟩ ⟨00| + |11⟩ ⟨00| + |00⟩ ⟨11| + |11⟩ ⟨11|
= trB
2
trB (|00⟩ ⟨00|) + trB (|11⟩ ⟨00|) + trB (|00⟩ ⟨11|) + trB (|11⟩ ⟨11|)
=
2
trB (|0⟩ ⟨0| ⊗ |0⟩ ⟨0|) + trB (|1⟩ ⟨0| ⊗ |1⟩ ⟨0|) + trB (|0⟩ ⟨1| ⊗ |0⟩ ⟨1|) + trB (|1⟩ ⟨1| ⊗ |1⟩ ⟨1|)
=
2
|0⟩ ⟨0| ⟨0|0⟩ + |1⟩ ⟨0| ⟨0|1⟩ + |0⟩ ⟨1| ⟨1|0⟩ + |1⟩ ⟨1| ⟨1|1⟩
=
2
|0⟩ ⟨0| + |1⟩ ⟨1|
=
2
I
=
2
Now, we observe that
2 !
I 1
tr = <1
2 2
and by Proposition 3.4 this immediately implies that the system is in a mixed state!
Observe what just happened: the entangled system is in a pure state, because
ρ = |Φ+ ⟩ ⟨Φ+ |
however, ρA (and ρB analogously) is mixed! This means that the state of the joint system
is known exactly, however the state of the first qubit is not maximally known. This strange
property is another hallmark of quantum entanglement.
3.3 Exercises
Problem 3.1
Show that when the observable is a Hermitian operator, Postulate 3.9 reduces to the
Measurement postulate.
Solution. Assuming the General measurement postulate (dens. op.), we can now discuss
the spacial case in which the observable is a Hermitian operator. Let A be a Hermitian
operator, and suppose that we have a system in a state described by some ensamble
i=1 . By the Spectral decomposition we know that
{pi , |ψi ⟩}N
X
A= λPλ
λ∈sp(A)
A = {Pλ }λ∈sp(A)
messages.downloaded_by
lOMoARcPSD|61948123
3.3. Exercises
Problem 3.2
Prove the validity of Principle of deferred measurement for an n-qubit unitary U .
Solution. Similar to the 2-qubits case, suppose that the state of the system is described
as X
|ψ⟩ = αx |x⟩
x∈Bn+1
We observe that x ∈ Bn+1 since the first wire has 1 control qubit, and the second register
contains the n remaining qubits that will be transformed through U . Therefore, the two
diagrams are identical as before:
• •
U U
messages.downloaded_by
lOMoARcPSD|61948123
3.3. Exercises
and the same reasoning applies for the probability that it collapses to |1⟩. Therefore, after
the first measurement we have that the state becomes
( P P 2
y∈Bn |0y⟩ @ y∈Bn |α0y |
|ψ⟩ P P 2
y∈Bn |1y⟩ @ y∈Bn |α1y |
Now, after applying the U gate only if the first qubit has collapsed to |1⟩, the final state
becomes ( P
|α |2
P
n |0y⟩ @
|ψ⟩ P y∈B Py∈Bn 0y 2
y∈Bn |1⟩ ⊗ U |y⟩ @ y∈Bn |α1y |
Differently, in the second case we simply have to distribute the controlled U gate inside
the state |ψ⟩, which indeed yields the same result:
|ψ⟩
X
= αx |x⟩
x∈Bn+1
C−U (|ψ⟩) X
−−−−−→ αx C-U |x⟩
x∈Bn+1
X X
= α0y C-U |0y⟩ + α1y C-U |1y⟩
x∈Bn+1 : x∈Bn+1 :
x=0y x=1y
X X
= α0y |0y⟩ + α1y |1⟩ ⊗ U |y⟩
y∈Bn y∈Bn
( P P 2
measure(|ψ⟩0 )
y∈Bn |0y⟩ @ y∈Bn |α0y |
−−−−−−−−→ P P 2
y∈Bn |1⟩ ⊗ U |y⟩ @ y∈Bn |α1y |
messages.downloaded_by
lOMoARcPSD|61948123
Quantum algorithms
4
Now that we presented all the mathematical tools we need to perform quantum compu-
tations, we are ready to explore some of the most famous and most important quantum
algorithms that have been developed in recent years. But before introducing any algo-
rithm, let’s discuss why we are interested in quantum computing at all — keep in mind
that is just a brief overview of the general ideas and we will delve into the exact details
as soon as we present some quantum algorithms more in depth.
Consider some computable function f (x) and some classical algorithm that is able to
compute it for any valid input x. If we have an input x1 , and we want to compute its
output we need to run the algorithm in order to compute f (x1 ). Analogously, if we have
another input x2 we need to run the algorithm again in order to compute f (x2 ). In
general, if we want to know the outputs f (x1 ), . . . , f (xN ) of N inputs x1 , . . . , xN , with
classical computing we must run the algorithm N distinct times, because there is no way
to compute more than one output at a time. With quantum computers, however, we will
see that not only this is possible, but we can actually compute all the possible outputs
related to all the possible inputs simultaneously. To the best of our knowledge, through
the laws of quantum mechanics we really can compute all the possible outputs f (x) for
each x ∈ Bn — for a fixed input length n.
How does this work in practice? Recall that we seemingly arbitrarily decided to denote
the vectors of the canonical basis with binary strings, such as |000⟩, |001⟩, |010⟩ and so
on (we chose n = 3 for this example). This is no coincidence: since this vectors form a
basis, we can write any quantum state |ψ⟩ as a linear combination of them, and by doing
so we obtain something like X
|ψ⟩ = αx |x⟩
x∈B3
Say that we want to compute f (x) for all x ∈ B3 . In practice, we construct a unitary
operator Uf that implements f reversibly — a property that we will discuss in the
following chapters — for example by acting on an auxiliary register
messages.downloaded_by
lOMoARcPSD|61948123
Now, by linearity of quantum operators when we apply Uf to |ψ⟩ ⊗ |0⟩ we get that
!
X
Uf (|ψ⟩ ⊗ |0⟩) = Uf αx |x⟩ ⊗ |0⟩
x∈B3
X
= αx Uf (|x⟩ ⊗ |0⟩)
x∈B3
X
= αx |x⟩ ⊗ |f (x)⟩
x∈B3
Notice what happened here! By only applying U to |ψ⟩⊗|0⟩ we actually applied Uf — and
therefore f (x) — on all the vectors of the basis simultaneously, hence computing each
possible output. This explains the choice of the labeling of the vectors of the canonical
basis.
So, what’s the catch? Well, we also recall that superpositions of states must be measured
at some point, and this is the problem: when we measure the result of Uf (|ψ⟩ ⊗ |0⟩)
we will inevitably get only one outcome. This makes finding useful quantum algorithms
extremely difficult, because even if we are performing all the computations at once we can
only see 1 possible output, at random. Hence, not only quantum algorithms are hard to
discover because of this inherent limitation of quantum mechanics, but they must also be
more efficient than any classical alternative we currently know, otherwise there is really
no point in using this very complicated computing framework (both in terms of hardware
and software). The algorithms that we will see in this chapter — and also in the next one
— are some of the most important quantum procedures that we know, and sparked a lot
of interest in this area of research in recent years.
messages.downloaded_by
lOMoARcPSD|61948123
which trivially proves that Uf is reversible. Moreover, we can actually prove that when
applied to qubits the corresponding quantum operator
We prove that Uf is indeed unitary in Problem 4.1. In the end, we have that the op-
erator Uf is precisely the quantum gate that allows us to embed f into any quantum
computation.
From now on, we will omit the “⊗” symbol for brevity. Interestingly enough, given our
definition of Uf we notice that
• |y⟩ = |0⟩ =⇒ Uf |x⟩ |0⟩ = |x⟩ |f (x)⟩
• |y⟩ = |1⟩ =⇒ Uf |x⟩ |1⟩ = |x⟩ |¬f (x)⟩
However, until now we only considered already collapsed qubits, but what if we consider
a quantum input that is in a superposition? For instance, let
1
|x⟩ = √ (|0⟩ + |1⟩)
2
and assume that |y⟩ = |0⟩ for simplicity; this implies that
1
Uf |x⟩ |y⟩ = Uf √ (|0⟩ + |1⟩) ⊗ |0⟩
2
1
= Uf √ (|00⟩ + |10⟩)
2
1
= √ (Uf |00⟩ + Uf |10⟩) (by linearity of Uf )
2
1
= √ (|0⟩ |f (0)⟩ + |1⟩ |f (1)⟩)
2
Notice what just happened: both f (0) and f (1) have been computed simultaneously,
in one gate application. This has no classical equivalent, we would have to evaluate f (0)
and f (1) separately. This phenomenon is called quantum parallelism, and it can be
achieved only because:
• qubits are in superpositions
• quantum gates are linear
However, we observe that the result of our calculations is still a superposition. In fact, if
we measure the output of Uf |x⟩ |y⟩ we would still get either |0⟩ |f (0)⟩ or |1⟩ |f (1)⟩, both
messages.downloaded_by
lOMoARcPSD|61948123
with 50% probability. This is a problem: the fact that we can compute f (0) and f (1) at
the same time seems promising, but can we retrieve their actual values?
Unfortunately, this is not possible. Indeed, quantum parallelism cannot help us with local
properties — i.e. when we need all individual outputs — it can only help when we need
global properties. This limit derives from the fact that measurements prevent “seeing”
both outcomes, in fact if we were able to compute f (0) and f (1) simultaneously from this
superposition we would be violating the laws of quantum mechanics themselves.
Then, how do we extract useful global information from the superposition output? In
1985 Deutsch [Deu85] defined a quantum algorithm which is able to compute f (0) ⊕ f (1),
which clearly tells us if f (0) equals f (1) or not.
Given a Boolean function f and 2 qubits, the algorithm returns |0⟩ if f if f (0) = f (1),
|1⟩ otherwise.
1: function Deutsch(f , q0 , q1 )
2: q1 ← X(q1 )
3: q0 , q1 ← (H ⊗ H)(q0 , q1 )
4: q0 , q1 ← Uf (q0 , q1 )
5: q0 ← H(q0 )
6: return measure(q0 )
7: end function
q0 H H
Uf
q1 X H
Figure 4.1: The quantum circuit for Deutsch’s algorithm. The box labeled with Uf
represents a “black-box” for whatever computation Uf represents (which directly depends
on the chioce of f ).
Proving that this quantum circuit is correct, however, will be a little more involved than
what we did for the quantum teleportation. First, we need a lemma that will simplify our
calculations.
messages.downloaded_by
lOMoARcPSD|61948123
Lemma 4.1
For any Boolean function f defined on n bits, and a ∈ {0, 1}n , it holds that
1 1
Uf |a⟩ ⊗ √ (|0⟩ − |1⟩) = (−1)f (a) |a⟩ ⊗ √ (|0⟩ − |1⟩)
2 2
• if f (a) = 1, then
1 1
√ (|a1⟩ − |a0⟩) = (−1)1 |a⟩ ⊗ √ (|0⟩ − |1⟩)
2 2
We are now ready to prove the correctness of Deutsch’s algorithm. To make things less
cluttered, we will use the following standard notation:
1 1
|+⟩ := √ (|0⟩ + |1⟩) |−⟩ := √ (|0⟩ − |1⟩)
2 2
In particular, we observe that
Moreover, we will omit the subscript of the corresponding qubit when the context is clear
enough
messages.downloaded_by
lOMoARcPSD|61948123
q0 ⊗ q 1
= |0⟩ ⊗ |0⟩
X(q1 )
−−−→ |0⟩ ⊗ |1⟩
(H⊗H)(q0 ,q1 )
−−−−−−−−→ |+⟩ ⊗ |−⟩
1 1
= √ |0⟩0 |−⟩1 + √ |1⟩0 |−⟩1
2 2
Uf (q0 ,q1 ) 1 1
−−−−−→ √ (−1)f (0) |0⟩0 |−⟩1 + √ (−1)f (1) |1⟩0 |−⟩1 (by the lemma)
2 2
1
= √ (−1)f (0) |0⟩0 + (−1)f (1) |1⟩0 ⊗ |−⟩1
2
H(q0 ) 1
−−−→ √ (−1)f (0) |+⟩0 + (−1)f (1) |−⟩0 ⊗ |−⟩1
2
1
= (−1)f (0) (|0⟩ + |1⟩) + (−1)f (1) (|0⟩ − |1⟩) ⊗ |−⟩1
2
1
(−1)f (0) + (−1)f (1) |0⟩ + (−1)f (0) − (−1)f (1) |1⟩ ⊗ |−⟩1
=
2
Now, since the final operation of the circuit involves measuring q0 = α |0⟩ + β |1⟩, the only
two things that we care about are its probability amplitudes, namely
1
(−1)f (0) + (−1)f (1)
α=
2
1
(−1)f (0) − (−1)f (1)
β=
2
and we see that
• if f (0) = f (1), then
α = 21 2(−1)f (0) = (−1)f (0)
f (0) f (1)
(−1) = (−1) =⇒
β=0
which implies that
2
Pr[measure(q0 ) = |0⟩] = (−1)f (0) =1
2
Pr[measure(q0 ) = |1⟩] = |0| = 0
In the end, this proves that if f (0) = f (1), q0 will collapse to |0⟩, while if f (0) ̸= f (1)
then q0 will colapse to |1⟩, proving that Deutsch’s algorithm is correct.
messages.downloaded_by
lOMoARcPSD|61948123
The definition of a constant Boolean function has nothing special, and balanced functions
are exactly what the name suggests, i.e. half of the inputs output 0 and the other half
output 1, which can be succintly expressed as follows.
We observe that a Boolean function can be neither constant nor balanced, so this decision
problem is actually a promise problem: given a Boolean function f that is either
constant or balanced — note that it cannot be both — decide if the function is constant
or balanced. Indeed, we see that Deutsch’s algorithm solved the same exact problem for
n = 2: if f (0) = f (1) it means that f is constant, otherwise it is balanced.
Moreover, this problem actually shows the power of quantum parallelism more evidently:
with a classical computation, to solve this decision problem we would need at most
2n−1 + 1 = O(2n )
queries to f , instead our quantum computation still only requires one evaluation of f to
solve the problem.
messages.downloaded_by
lOMoARcPSD|61948123
Given a Boolean function f and n+1 qubits, the algorithm returns |0n ⟩ if f is constant,
|1⟩ otherwise.
1: function DeutschJosza(f , q0 , q1 )
2: q1 ← X(q1 )
3: q0 , q1 ← (H ⊗n ⊗ H)(q0 , q1 )
4: q0 , q1 ← Uf (q0 , q1 )
5: q0 ← H ⊗n (q0 )
6: return measure(q0 )
7: end function
Note that in this algorithm q0 are actually n qubits, thus q0 is initially set to |0⟩⊗n . Before
proving the correctness of this general version of the algorithm, let us first take a look at
the quantum circuit that defines it.
q0⊗n H ⊗n H ⊗n
Uf
q1 X H
Proposition 4.1
For any x ∈ Bn it holds that
1 X
H ⊗n |x⟩ = √ n (−1)x·a |a⟩
2 a∈Bn
and analogously
1 1 X
H |1⟩ = |−⟩ = √ (|0⟩ − |1⟩) = √ (−1)1·b |b⟩
2 2 b∈B
messages.downloaded_by
lOMoARcPSD|61948123
In the rest of the proof we will denote with the · symbol the “canonical” scalar product,
i.e. n
X
n
∀x, y ∈ B x · y := xi y i
i=1
n
O
H ⊗n |x⟩ = H |xi ⟩
i=1
n
!
O 1 X
= √ (−1)xi b |b⟩ (by the claim)
i=1
2 b∈B
n
1 O
=√ n (|0⟩ + (−1)xi |1⟩)
2 i=1
1 X
=√ n (−1)x·a |a⟩
2 a∈Bn
messages.downloaded_by
lOMoARcPSD|61948123
q0 ⊗ q 1
= |0⟩⊗n ⊗ |0⟩
X(q1 )
−−−→ |0⟩⊗n ⊗ |1⟩
H ⊗n (q0 ,q1 )
−−−−−−→H ⊗n |0⟩⊗n ⊗ H |1⟩
1 X n
=√ n (−1)0 ·a |a⟩ ⊗ |−⟩ (by Proposition 4.1)
2 a∈Bn
1 X
=√ n |a⟩ ⊗ |−⟩
2 a∈Bn
1 X
=√ n (|a⟩ ⊗ |−⟩)
2 a∈Bn
Uf (q0 ,q1 ) 1 X
(−1)f (a) |a⟩ ⊗ |−⟩ (by Lemma 4.1)
−−−−−→ √ n
2 a∈Bn
1 X
=√ n (−1)f (a) |a⟩ ⊗ |−⟩
2 a∈Bn
!
H ⊗n (q0 ) 1 X
−−−−−→H ⊗n √ n (−1)f (a) |a⟩ ⊗ |−⟩
2 a∈Bn
1 X
(−1)f (a) H ⊗n |a⟩ ⊗ |−⟩
=√ n
2 a∈Bn
!
1 X 1 X
=√ n (−1)f (a) √ n (−1)a·b |b⟩ ⊗ |−⟩ (by Proposition 4.1)
2 a∈Bn 2 b∈Bn
1 X X
= n (−1)f (a)+a·b |b⟩ ⊗ |−⟩
2 a∈Bn b∈Bn
1 X X
= n (−1)f (a)+a·b |b⟩ ⊗ |−⟩
2 b∈Bn a∈Bn
!
X 1 X
= n
(−1)f (a)+a·b |b⟩0 ⊗ |−⟩1
b∈Bn
2 a∈Bn
Now note that this state describes the superposition of the system, but the next step of
the algorithm will only measure q0 , therefore we can ignore |−⟩1 and just focus on the
amplitudes of q0 . Then, by calling
1 X
∀b ∈ Bn αb := (−1)f (a)+a·b
2n a∈Bn
Finally, since we want to determine the probability that q0 collapses into the state |0n ⟩
messages.downloaded_by
lOMoARcPSD|61948123
4.3. Exercises
specifically, we can easily evaluate the associated amplitude of the latter, i.e.
1 X n 1 X
α0n = n (−1)f (a)+a·0 = n (−1)f (a)
2 a∈Bn 2 a∈Bn
From this, we can easily conclude that:
• if f is constant, then
Pr[measure(q0 ) = |0n ⟩] = |α0n |2
2
1 X
= n (−1)f (a)
2 a∈Bn
2
1
= n · 2n · (−1)b (∀a ∈ Bn f (a) = b ∈ B)
2
2
= (−1)b
=1
therefore q0 is guaranteed to collapse to |0n ⟩
• if f is balanced, then
Pr[measure(q0 ) = |0n ⟩] = |α0n |2
2
1 X
= n (−1)f (a)
2 a∈Bn
2
1 X
f (a)
X
= n
(−1) + (−1)f (a)
2
a∈Bn : a∈Bn :
f (a)=0 f (a)=1
2
1 X X
= n
1 + −1
2
a∈Bn : a∈Bn :
f (a)=0 f (a)=1
2
1 n−1 n−1
= 2 − 2
2n
2
1
= n ·0
2
=0
meaning that it is guaranteed that q0 will not collapse to |0n ⟩.
4.3 Exercises
Problem 4.1
Given a Boolean function f : {0, 1}n → {0, 1}, the operator Uf is unitary.
messages.downloaded_by
lOMoARcPSD|61948123
4.3. Exercises
We will omit the dimensions of the Hilbert spaces for brevity, as they are are not relevant.
What we are really interested in is that |b⟩ can surely be written as tensor product of
some |x⟩ ⊗ |y⟩ for b ∈ Bn+1 , x ∈ Bn and y ∈ B. Therefore, the operator above can be
rewritten as
X
Uf = Uf |b⟩ ⟨b|
b
XX
= Uf |x⟩ |y⟩ ⟨x| ⟨y|
x y
XX
= |x⟩ |y ⊕ f (x)⟩ ⟨x| ⟨y|
x y
From now on, we will extensively utilize Proposition 2.18. First, we prove that Uf is
actually Hermitian.
Claim: The operator Uf is Hermitian.
Now, let y ′ := y ⊕ f (x); then, by the properties of the XOR it follows that
y = y ′ ⊕ f (x)
which means that
XX
Uf = |x⟩ |y⟩ ⟨x| ⟨y ⊕ f (x)|
x y
XX
= |x⟩ |y ′ ⊕ f (x)⟩ ⟨x| ⟨y ′ |
x y′
= Uf
messages.downloaded_by
lOMoARcPSD|61948123
4.3. Exercises
Uf Uf† = Uf Uf = Uf† Uf
Problem 4.2
Compute the final state of the following three-qubit circuit:
|0⟩ H •
|0⟩ H •
|0⟩
Solution. Let q0 , q1 and q2 be the three input qubits; to compute the final state of the
messages.downloaded_by
lOMoARcPSD|61948123
4.3. Exercises
q0 ⊗ q 1 ⊗ q 2
= |0⟩ ⊗ |0⟩ ⊗ |0⟩
H(q0 )
−−−→H |0⟩ ⊗ |0⟩ ⊗ |0⟩
= |+⟩ ⊗ |0⟩ ⊗ |0⟩
1
= √ (|0⟩ + |1⟩) ⊗ |0⟩ ⊗ |0⟩
2
1
= √ (|00⟩ + |10⟩) ⊗ |0⟩
2
CNOT(q0 ,q1 ) 1
−−−−−−−→ √ (CNOT |00⟩ + CNOT |10⟩) ⊗ |0⟩
2
1
= √ (|00⟩ + |11⟩) ⊗ |0⟩
2
1
= √ (|0⟩ ⊗ 0 + |1⟩ ⊗ |1⟩) ⊗ |0⟩
2
H(q1 ) 1
−−−→ √ (|0⟩ ⊗ H |0⟩ + |1⟩ ⊗ H |1⟩) ⊗ |0⟩
2
1
= √ (|0⟩ ⊗ |+⟩ + |1⟩ ⊗ |−⟩) ⊗ |0⟩
2
1 1 1
= √ (|0⟩ ⊗ √ (|0⟩ + |1⟩) + |1⟩ ⊗ √ (|0⟩ − |1⟩)) ⊗ |0⟩
2 2 2
1 1 1
= √ ( √ (|00⟩ + |01⟩) + √ (|10⟩ − |11⟩)) ⊗ |0⟩
2 2 2
1
= (|000⟩ + |010⟩ + |100⟩ − |110⟩)
2
1
= (|0⟩ ⊗ |00⟩ + |0⟩ ⊗ |10⟩ + |1⟩ ⊗ |00⟩ − |1⟩ ⊗ |10⟩)
2
CNOT(q1 ,q2 ) 1
−−−−−−−→ (|0⟩ ⊗ CNOT |00⟩ + |0⟩ ⊗ CNOT |10⟩ + |1⟩ ⊗ CNOT |00⟩ − |1⟩ ⊗ CNOT |10⟩)
2
1
= (|000⟩ + |011⟩ + |100⟩ − |111⟩)
2
messages.downloaded_by
lOMoARcPSD|61948123
approaches for specific problems. These algorithms, while conceptually simpler, help da
understanding the power and subtleties of quantum computation. finire
Building upon that foundation, we now turn our attention to a more sophisticated and
central algorithm: Quantum Phase Estimation (QPE). At its core, QPE allows us
to determine the eigenvalues of a unitary operator with remarkable precision, a capability
that lies at the heart of many quantum algorithms. Unlike the problems addressed by
simpler algorithms, phase estimation tackles inherently more complex tasks and more
broadly applicable, as we will see in the subsequent chapters.
The importance of QPE cannot be overstated. In this chapter, we will focus solely on QPE
and how it works, while in the next chapters we will see how QPE is actually leveraged
in the most widely known quantum algorithm, namely Grover’s algorithm and Shor’s
algorithm.
messages.downloaded_by
lOMoARcPSD|61948123
alent in the frequency domain. We will briefly explore the most important concepts that
define the DFT to have a better understanding in order to the progress with its quantum
counterpart.
First, what is the “time domain”? When we sample a signal, we usually sample such signal
through some finite amount of time, and we discretize such time interval — this is why
we consider the Discrete Fourier transform. What we are interested in is to transform
such signal into the “frequency domain”, which essentially means to understand what
frequencies of sinusoids contribute to our signal and in which percentage. To do this, we
will use some concepts of Linear Algebra. Say that the signal we sampled is discretized
into N parts, thus our sample lives in the RN space — it is nothing but a vector of N
complex values which describe the signal at each timestep. When we say “time domain”,
what we mean is basically this exact vector, i.e. expressed in the canonical orthonormal
basis
1 0 0
0 1 ..
e0 = . e1 = . . . . eN −1 = .
.. .. 0
0 0 1
(we will start counting at 0 for convenience sake). In other words, if our signal is defined
by some vector
t0
t1
x= .
. .
tN −1
it holds that
N
X −1
x= tn en
n=0
Then, what is the “frequency domain”? We need some preliminary observations to describe
it. Our goal is to take into account the frequencies that define our signal, therefore we
need to move into a space in which frequencies are “first-class citizens”. The idea is to use
each possible sinusoid by varying the frequency, add up their contributions, and weight
the latter in the precise way that allows us to reconstruct our original signal. Let us fix
a component n ∈ [0, N − 1], and first consider only cosinusoids, for instance
cos(2π · 0 · n) cos(2π · 1 · n) cos(2π · 2 · n) ... cos(2π · (N − 1) · n)
Basically, we are trying to construct a basis built on each possible frequency f by obtaining
a basis vector cos(2π · f · n). Moreover, we will consider cos(2πmn/N ) for m ∈ [0, N − 1]
since it can be shown that the number of possible frequencies that can be represented on
a N -sized time window is exactly N , and to scale the frequency accordingly we just need
to divide m over N , the size of the sample.
Is this enough to reach our goal? Can we describe any signal in this way? Well, we observe
that m is ranging from 0 to N − 1, but cos(−θ) = cos(θ), which implies that
N
m> =⇒ cos(2πmn/N ) = cos(2π(N − m)n/N )
2
messages.downloaded_by
lOMoARcPSD|61948123
In other words, basically half of our basis vectors add no information at all. Indeed, the
span of the vectors we chose has size
N + 1 N is even
N −1
dim span {cos(2π · m · n/N )}m=1 = 2
N +1
2
N is odd
where the last added 1 comes from the fact that when m = 0 we generate cos(0) = 1 which
is really linearly independent from the others cosines. This suggests that cosinusoids alone
are not enough to describe our space.
Hence, the most natural thing that we can do is add the contributions of sinusoids as well.
A geometric interpretation of the fact that cosinusoids are not enough is that sinusoids
are just phase-shifted cosines, but the shift in phase is not captured by changing the
frequencies of the cosines alone. We need the contributions of some “altered” cosinusoids
— in terms of phases — to get an actual basis and be able to represent any possible
vector. Hence, let’s consider additional N sinusoids
Do we get a base of size more than N then? We observe that sin(θ) = − sin(−θ), therefore
we have that
N
m> =⇒ sin(2πmn/N ) = − sin(2π(N − m)n/N )
2
which again it implies that half of these sinusoids add no useful information. However, in
this case we also have the fact that
which means that these two sinusoid cannot be considered because they are the 0 vector
of this space. Therefore, we get that
N − 1 N is even
N −1
dim span {sin(2π · m · n/N )}m=1 = 2
N −1
2
N is odd
Finally, this means that putting all these cosines and sinusoids together we form a base
for a space that has size
+ 1 + N2 − 1 = N N is even
N
2 =N
N +1
2
+ N2−1 = N N is odd
Hence, we can fully describe RN , namely for any vector x ∈ RN we have that
N
X −1 N
X −1
∀n ∈ [0, N − 1] x(n) = αm cos(2πmn/N ) + βm sin(2πmn/N )
m=0 m=0
messages.downloaded_by
lOMoARcPSD|61948123
to immediately some the contributions of cosinusoids and sinusoids into a single value
e2πimn/N . In other words, for any vector x ∈ CN it holds that
N
X −1
∀n ∈ [0, N − 1] x(n) = γm e2πimn/N
m=0
We observe that this basis is orthogonal as well, but it’s not orthonormal in fact Hence, prove
it, bor-
because the norm of each vector is ing too
v
q uN −1
uX
⟨e2πimn/N |e2πimn/N ⟩ = t e2πimn/N · e2πimn/N
n=0
v
uN −1
uX 2
=t |e2πimn/N |
n=0
v
uN −1
uX
=t 1
n=0
√
= N
N −1
1 X
∀n ∈ [0, N − 1] x(n) = √ δm e2πimn/N
N m=0
Indeed, we can compute the DFT by simply applying the matrix that performs the change
of basis, but we will see the details of this idea in the next section.
messages.downloaded_by
lOMoARcPSD|61948123
For instance, −i is a 4-th root of unity, in fact (−i)4 = 1. We observe that, since
multiplication in the complex plane is a rotation, the n−-th roots of 1 evenly divide the
unit circle as shown below:
TODO drawing
Now, among all possible n-th roots of unity we are going to provide a more specific
definition. Let the order of an n-th root of unity ω be the smallest power d such that
ω d = 1. For instance, (−1)4 = 1 indeed −1 is a 4-th root of unity, however its order is 2
since (−1)2 = 1 and 2 < 4.
Given an n-th root of unity ω, we say that ω = eiθ is principal if and only if
• ω ̸= 1
• ω is n
• θ is minimal
In other words, the principal n-th root of unity is the “first” n-th root (after 1) that we
encounter on the unit circle. Indeed, thanks to Euler’s formula we usually define the
principal n-th root of unity as
ω := e2πi/n
since 2π
n
is the n-th slice of the unit circle. Furthermore, the second condition of the defini-
tion is usually not provided in terms of order of the root, and it’s written as follows
n−1
X
∀p ∈ [n − 1] ω jp = 0
j=0
Aside from the geometric interpretation of this sum, this is a finite complex geometric
series with common ratio ω p , which implies that
• if ω p = 1, then every term is (ω p )j = 1j = 1 for any j, meaning that the sum is
equal to
n−1
X n−1
X
jp
ω = 1=n
j=0 j=0
messages.downloaded_by
lOMoARcPSD|61948123
1 − (ω p )n = 0 ⇐⇒ ω pn = 1
Therefore, we have that this sum is equal to 0 if and only if ω p ̸= 1 and ω pn = 1. Indeed,
when ω p = 1 since p ∈ [n − 1] this would imply that the order of ω is less than n, meaning
that ω was not a principal root.
Now that we presented roots of unity we can finally present how the DFT matrix is usually
defined.
···
1 1 1 1
−1
1
ω ω −2 · · · ω −(N −1)
DFT :=
1 ω −2 ω −4 · · · ω −2(N −1)
. .. .. ... ..
.. . . .
−(N −1) −2(N −1) 2
1 ω ω · · · ω −(N −1)
2πi
Moreover, we usually define the DFT matrix by setting ω = e n , thus getting
Indeed, having presented the intuition behing the DFT beforehand, it’s now fairly obvious
the reason why the DFT matrix looks like this: its just the matrix that performs the
change of basis, and since the basis of the DFT space can be defined in terms of n-th
roots of unity, this is the matrix we get.
Furthermore, not surprisingly the DFT matrix is invertible, in fact we have that
1 jk 1
∀j, k ∈ [0, N − 1] IDFTjk = DFT−1
jk = ω = e+2πijk/N
N N
and this matrix takes the name of Inverse Discrete Fourier Transform (IDFT).
messages.downloaded_by
lOMoARcPSD|61948123
Then, can’t we just use the DFT matrix in quantum computations whenever we need it
and be done? The problem is that the DFT matrix is clearly not unitary: if we look closely,
we see that the columns of the DFT matrix are only orthogonal and not orthonormal.
Thus, to solve this problem, we need to normalize the column vectors.
Given a Hilbert space H of size N , the Quantum Fourier Transform (QFT) matrix
in H is defined as follows:
1
∀j, k ∈ [0, N − 1] QFTjk = √ ω jk
N
where ω is the principal N -th root of unity.
We observe that the QFT matrix has positive exponents, which is just a convention
employed in quantum computing. Therefore, we get the following matrix:
···
1 1 1 1
1
ω ω2 · · · ω N −1
QFT := 1
ω2 ω4 · · · ω 2(N −1)
. .. .. .. ..
.. . . . .
(N −1)2
1 ω N −1 ω 2(N −1) ··· ω
In particular, for any |x⟩ basis state, the quantum Fourier transform can also be expressed
as follows:
N −1
1 X +2πixk/N
QFT |x⟩ = √ e |k⟩
N k=0
which directly implies that we can rewrite the QFT matrix as follows
−1 N −1
N
!
X 1 X 2πijk/N
QFT = √ e |k⟩ ⟨j|
j=0
N k=0
Proposition 5.1
The QFT operator is a unitary, and in particular
−1 −1
N N
!
X 1 X
QFT† = |j⟩ √ e−2πijk/N ⟨k|
j=0
N k=0
messages.downloaded_by
lOMoARcPSD|61948123
Now, we observe that the inner sum is a geometric series of ratio e2πi(k−j)/N , and we can
use its known result to simplify the calculations. However, we observe that this is true
only if the ratio of the series is not equal to 1, but due to the way we split the sums we
already took care of all the possible terms that could be equal to 1 so we do not need to
make additional assumptions. Thus, we have that
−1 −1
N N
!
1 X X r
QFT† QFT = I + e2πi(k−j)/N
|j⟩ ⟨k|
N j,k=0: r=0
j̸=k
N −1 N !
1 X 1 − e2πi(k−j)/N
=I+ |j⟩ ⟨k|
N j,k=0:
1 − e2πi(k−j)/N
j̸=k
N −1
1 − e2πi(k−j)
1 X
=I+ |j⟩ ⟨k|
N j,k=0: 1 − e2πi(k−j)/N
j̸=k
Lastly, since k − j is an integer for any j, k ∈ [0, N − 1], therefore, the numerator is always
messages.downloaded_by
lOMoARcPSD|61948123
The problem arises because we are using fractional exponents, however x ∈ Bn . To solve
this issue, we need to take a closer look at the exponent. Since x ∈ Bn , there exist some
bits x1 , . . . , xn ∈ B such that x can be written as
x = x1 · 2n−1 + . . . + xn · 20
Since k ∈ [0, N − 1], we can also define such k1 , . . . , kn ∈ B, and we can see what happens
when we evaluate xk/N :
(k1 · 2n−1 + . . . + kn · 20 ) · (x1 2n−1 + . . . + xn 20 )
kx/N =
2n
2n−1 20
n−1 0
= k1 · 2 + . . . + kn · 2 · x1 · n + . . . + xn · n
2 2
n−1 0
= k1 · 2 + . . . + kn · 2 · 0.x1 . . . xn
= k1 · 2n−1 · 0.x1 . . . xn + . . . + kn · 20 · 0.x1 . . . xn
This is true because we recall that
and since we are computing x/N and N = 2n what we get is just a “displacement of the
decimal point”, but in binary. Now, we observe that
since again, we are just moving the decimal point n − ℓ times to the right. Therefore, we
get that
kx/N = k1 · x1 . . . xn−1 .xn + . . . + kn 0.x1 . . . xn
n−1
X
= kn · 0.x1 . . . xn + kh · x1 . . . xn−h .xn−h+1 . . . xn
h=1
messages.downloaded_by
lOMoARcPSD|61948123
we observe that we need to put 0.x1 . . . xn just because we cannot include it in the same
sum. Now, let’s see what happens when we put this term at the exponent:
e2πikx/N
= exp(2πikx/N )
n−1
!!
X
= exp 2πi kn 0.x1 . . . xn + kh · x1 . . . xn−h .xn−h+1 . . . xn
h=1
n−1
!
X
= exp(2πikn 0.x1 . . . xn ) · exp 2πi kh · x1 . . . xn−h .xn−h+1 . . . xn
h=1
n−1 n−1
!
X X
= exp(2πikn 0.x1 . . . xn ) · exp 2πi kh · (x1 . . . xn−h ) + 2πi kh · [Link]−h+1 . . . xn
h=1 h=1
n−1
! n−1
!
X X
= exp(2πikn 0.x1 . . . xn ) · exp 2πi kh · (x1 . . . xn−h ) · exp 2πi kh · [Link]−h+1 . . . xn
h=1 h=1
n−1
!
X
= exp(2πikn 0.x1 . . . xn ) · 1 · exp 2πi kh · [Link]−h+1 . . . xn
h=1
The last semplitifcation derives immediately from the fact that e2πiθ = 1 when θ is an
integer, as we mentioned in the previous section, so that is what we are left with — since
x1 . . . xn−h is definitely an integer. We can proceed as follows:
QFT |x⟩
N −1 n−1
!!
1 X X
=√ exp(2πikn 0.x1 . . . xn ) · exp 2πi kh · [Link]−h+1 . . . xn |k⟩
N k=0 h=1
N −1 n
!!
1 X X
=√ exp(2πikn 0.x1 . . . xn ) · exp 2πi kn−m+1 · [Link] . . . xn |k⟩
N k=0 m=2
N −1 n
!
1 X X
=√ exp 2πi kn−m+1 · [Link] . . . xn |k⟩
N k=0 m=1
N −1 n
1 XY
=√ exp (2πikn−m+1 · [Link] . . . xn ) |k⟩
N k=0 m=1
messages.downloaded_by
lOMoARcPSD|61948123
In other words the bits of k are indexing which exponentials to use in the k-th coefficient
of the sum. This means that we can rewrite the last step as follows:
n
1 O
QFT |x⟩ = √ |0⟩ + e2π[Link] ...xn |1⟩
N m=1
It can be easily proven that it is unitary, so we can use it as a quantum gate. Hence, we
construct the following quantum circuit:
|xn ⟩ • • ... • H
TODO explain
what is
ts, non
manca
lo swap
5.3 Quantum Phase Estimation alla fine
tipo?
The application of the QFT we are going to present in this section was introduced by
Kitaev [Kit95] in 1995, and it is the most important quantum algorithm to date. As we
will see, it will be used for multiple algorithms in the next chapters.
By Theorem 2.4 we know that the eigenvalues of a unitary operator are complex values
of modulus 1. This means that any eigenvalue of a unitary operator can be ewritten as
e2πiφ for some real value φ ∈ [0, 1] — φ being the phase of the complex value, i.e. the
angle w.r.t. the unitary circumference.
messages.downloaded_by
lOMoARcPSD|61948123
Now, let U 2 be the quantum gate that applies the U operator 2k times repeatedly, and
k
This operator is the controlled version of U 2 , and it can easily be showed by plugging
k
|0⟩ and |1⟩ as first argument — alongside with some other quantum state |ψ⟩
k k
C-U 2 (|0⟩ ⊗ |ψ⟩) = (|0⟩ ⟨0| ⊗ I + |1⟩ ⟨1| ⊗ U 2 )(|0⟩ ⊗ |ψ⟩)
k
= (|0⟩ ⟨0| ⊗ I) |0⟩ ⊗ |ψ⟩ + (|1⟩ ⟨1| ⊗ U 2 ) |0⟩ ⊗ |ψ⟩
= |0⟩ ⊗ |ψ⟩
Hence, if the first input is |0⟩ the state |ψ⟩ is unchanged, otherwise if the former is |1⟩ we
get that we actually apply U 2 to |ψ⟩:
k
k k
C-U 2 (|1⟩ ⊗ |ψ⟩) = (|0⟩ ⟨0| ⊗ I + |1⟩ ⟨1| ⊗ U 2 )(|1⟩ ⊗ |ψ⟩)
k
= (|0⟩ ⟨0| ⊗ I) |1⟩ ⊗ |ψ⟩ + (|1⟩ ⟨1| ⊗ U 2 ) |0⟩ ⊗ |ψ⟩
k
= |1⟩ ⊗ U 2 |ψ⟩
Indeed, in general if we have an operator V , its controlled version can be easily built in
this manner:
C-V = |0⟩ ⟨0| ⊗ I + |1⟩ ⟨1| ⊗ V
However, this controlled gate can also be “abused”: what happens if the control bit is a
superposition of states? In particular, what happens when the control is set to
1
|+⟩ = √ (|0⟩ + |1⟩)
2
meaning that |0⟩ and |1⟩ are equally probable?
k 1 k
C-U 2 (|+⟩ ⊗ |ψ⟩) = √ C-U 2 (|0⟩ ⊗ |ψ⟩ + |1⟩ ⊗ |ψ⟩)
2
1 k k
= √ (C-U 2 (|0⟩ ⊗ |ψ⟩) + C-U 2 (|1⟩ ⊗ |ψ⟩))
2
1 k
= √ ((|0⟩ ⊗ |ψ⟩) + (|1⟩ ⊗ U 2 |ψ⟩))
2
As we would expect, what happens is that the two outcomes we previously described
are now equally likely, but this gets interesting if we carefully choose the target qubit.
Instead of any possible |ψ⟩, let’s pick |u⟩, the eigenvector presented at the beginning of
the discussion. First, we observe that
k 2k kφ
U |u⟩ = e2πiφ |u⟩ =⇒ U 2 |u⟩ = e2πiφ |u⟩ = e2πi2 |u⟩
messages.downloaded_by
lOMoARcPSD|61948123
Indeed, intuitively we are just performing the rotation that U performs on |u⟩ exactly 2k
times. This means that
k 1 k
C-U 2 (|+⟩ ⊗ |u⟩) = √ ((|0⟩ ⊗ |u⟩) + (|1⟩ ⊗ U 2 |u⟩))
2
1 k
= √ ((|0⟩ ⊗ |u⟩) + (|1⟩ ⊗ e2πi2 φ |u⟩))
2
1 k
= √ (|0⟩ + e2πi2 φ |1⟩) ⊗ |u⟩
2
Notice what happened here: |0⟩ and |1⟩ are parts of the first input, and |u⟩ is the second
input. In other words, by putting |u⟩ as target input of the controlled gate, the target
is unchanged, and the effect is seen on the control. We observe that this could not
have been done with any other state |ψ⟩ because the trick works precisely because U
becomes a scalar e2πiφ when applied to |u⟩, so it can be grouped as shown. The following
quantum circuit computes the Quantum Phase Estimation (QPE) algorithm, and it
uses precisely this trick.
Given a unitary operator U , and an eigenvector |u⟩ of U , the algorithm returns the
phase φ to which |u⟩ is associated to.
messages.downloaded_by
lOMoARcPSD|61948123
Furthermore, we obseve that φ ∈ [0, 1), because as we already metioned there is no need
messages.downloaded_by
lOMoARcPSD|61948123
to consider the integral part of the phases. Thus, suppose that φ can be written through
t bits φ1 , . . . , φt ∈ B such that
φ = 0.φ1 . . . φt
This implies that
2m−1 · φ = 2m−1 · 0.φ1 . . . φt
= φ1 . . . φm−1 .φm . . . φt
Very elegantly, this is exactly QFTt |φ⟩ we computed in the previous section (only applied
in a t-dimensional space). Finally, if we place the inverse QFT — namely QFT†t — at
the end of the circuit we retrieve |x⟩ itself, which is also the entire state of the system at
this point (without considering |u⟩). This means that if we measure each register at the
end of the circuit we retrieve the bits of φi ∈ Bt — i.e. the bits that describe φ — with
probability 1. In the end, we recovered the phase φ of the eigenvalue associated to |u⟩
with probability 1.
As a final note, what if φ cannot be expressed in exactly t bits? It can be shown
that φ 1can
be estimated with n bits of precision through a QPE circuit composed of n+ log(2 + 2ε )
qubits with a success probability at least 1 − ε, for some ε > 0.
messages.downloaded_by
lOMoARcPSD|61948123
hardware — with classical optimization techniques that adjust those parameters. This
hybrid quantum-classical strategy resembles machine-learning approaches like neural
networks and helps manage NISQ constraints while avoiding the deep circuits required
by fully fault-tolerant quantum algorithms.
VQAs have been explored for a wide range of quantum computing applications and may
offer the best chance for near-term quantum advantage. Due to the inherent versatility of
VQAs, there is a wide variety of different algorithmics structures with different levels of
complexity. Nevertheless, most of VQAs share the same basic elements. A VQA begins
with a clearly defined task and, if needed, relevant training data. The first step is to
design a cost function C that captures what it means to solve the problem.
Next, it must be choosen an ansatz, a German term that can be translated to approach or
attempt. In the context of physics and mathematics, an ansatz is kind of an initial estimate
to the solution of the problem considered. For instance, given a set of experimental
data that looks to be clustered about a line, a linear ansatz could be made to find the
parameters of the line by a least squares curve fit. In other words, if experimental data
looks linear, we might choose a linear model
y = mx + b
because we believe that the solution lives somewhere in the “space of all straight lines”.
Thus, in the quantum context specifically, the ansatz is the family of quantum states
we allow the VQA to explore
|ψ(θ)⟩ = U (θ) |ψ0 ⟩
for some initial state |ψ0 ⟩, and a set of parameters θ of the model — θ is not an angle here!
This means that choosing the structure of the circuit is the ansatz itself. In fact, this is
the reason why choosing an appropriate ansatz is one of the most important steps of the
whole process, and there are a wide range of ansatze that are currently being studied in
order to model different type of problems. Cerezo, Arrasmith, Babbush, et al. [CAB+20]
compiled a detailed list of the best known ansatze depending on the application of the
VQA.
The algorithm then trains these parameters through a hybrid quantum-classical optimiza-
tion loop, seeking the values
θ∗ = arg min C(θ)
θ
that minimize the cost function chosen. The quantum computer then evaluates the cost,
and a classical optimizer updates the parameters according to a preffered optimization
strategy — classical Stochastic Gradient Descent (SGD) is usually employed but
newer alternatives are being developed in recent years that are “gradient-free”.
VQAs are highly flexible because they support task-oriented programming, making them
suitable for nearly every major application envisioned for quantum computers. In fact,
they are powerful enough to enable universal quantum computation. A quantum
model is said to be universal if it can approximate any unitary operation on any number
of qubits to arbitrary accuracy, only using some kind of restricted architecture. In some
sense, it is the quantum analog of what being a universal gate means with classical
gates.
messages.downloaded_by
lOMoARcPSD|61948123
H |ψ⟩ = E |ψ⟩
which is used when looking at stationary states — states whose probability distributions
don’t change over time. In this formula, we have that
• H is the Hamiltonian
• E is an eigenvalue of H, which is the energy of |ψ⟩
• |ψ⟩ is an eigenvector associated to E, which is the stationary state we are considering
Each eigenvalue E of H tells us an allowed energy level of the system, and we are interested
in the lowest one, which is called ground-state energy, often denoted as EG . While
higher eigenvalues describe excited states that govern how mulecules absorb and emit
light, EG describes a molecule’s stability, preferred structure and how it participates in
chemical reactions. This is the eigenvalue we are interested in, and it will be the main
focus of our discussion. Determining the ground-state energy is essential for understanding
spectroscopy, photochemistry, and materials used in solar cells or sensors. Moreover,
beyond chemistry many problems in physics, materials science, and engineering reduce
to eigenvalue calculations as well, such as the behavior of electrons in solids and the
vibrations of mechanical structures.
What is the problem in finding the eigenvalues of H then? We observe that when we
have a system of n particles we require a Hilbert space of dimension 2n , which means
that the size of the Hamiltonian is 2n × 2n . This exponential growth makes the search for
eigenvalues classically intractable. Traditional approximate methods help but cannot
achieve efficient, exact solutions for large systems. Luckily, quantum computing offers a
promising path forward.
Actually, we already know a quantum algorithm that is able to yield the eigenvalue of a
unitary operator: it’s the QPE. Indeed, this algorithm does provide exponential speedups
w.r.t. classical approaches, however it requires long coherent evolution and extremely deep
circuits, making it impractical for near-term devices. Today, in the NISQ era, QPE is still
not practical. However, in 2014 Peruzzo, McClean, Shadbolt, et al. [PMS+14] published a
landmark paper, which proposed a VQA that avoids the long coherent runtimes required
by QPE.
messages.downloaded_by
lOMoARcPSD|61948123
From a theoretical point of view, the idea is fairly straightforward: we want to find the
state |ψ ∗ ⟩ that minimizes the eigenvalue, in order to find EG . But first, let’s consider a
more general scenario: let A be any observable (i.e. a self-adjoint operator), and consider
its expected value ⟨A⟩. In Proposition 3.2 we already proved that if the current state is
|ψ⟩ it holds that
⟨A⟩ = ⟨ψ|Aψ⟩
We are interested in finding the state |ψ ∗ ⟩ that will yield the lowest possible eigenvalue
of A after measuring the latter. We observe that
⟨ψ|Aψ⟩ = ⟨A⟩
= E[A | |ψ⟩]
Xm
= λi Pr[A = λi | |ψ⟩]
i=1
≥ min λi
i∈[m]
= λmin
with the equality holding if |ψ⟩ = |ψ ∗ ⟩. This means that by searching for
we can immediately find λmin . It is easy to see that this idea is clearly applicable for
finding EG since H is self-adjoint, thus
C(θ) = ⟨ψ(θ)|Hψ(θ)⟩
where in this case |ψ(θ)⟩ is the “trial” state that has to be defined as
where U (θ) represents the ansatz of choice. Therefore, we are interested in finding the
best parameters such that
θ∗ = arg min ⟨ψ(θ)|Hψ(θ)⟩
θ
We observe that there is no universal ansatz for the VQE, as there are multiple variants
that have been developed depending on the specific Hamiltonian of interest — different
Hamiltonians may have different structures, entanglement patterns and symmetries. In
conclusion, from a theoretical standpoint of view the VQE aims at minimizing C(θ)
by computing the cost with a NISQ machine, and by optimizing θ through a classical
computer.
In particular, we observe that the evaluation of the cost depends on the value of ⟨H⟩, and
the best way we have to evaluate this quantity is by repeatedly measuring H. However,
messages.downloaded_by
lOMoARcPSD|61948123
due to the size of H and the noise of the machines this step is often implemented with
a better alternative. In fact, there is a very useful property of Hamiltonians that we can
leverage: any Hamiltonian can be written as linear combination of tensor products of
Pauli matrices n
X O
H= hj σαk ,jk
j k=1
which means that in order to compute the cost C(θ) we can instead evaluate the follow-
ing * n +
X O
′
C(θ) = ⟨H⟩ = ⟨ψ(θ)|Hψ(θ)⟩ = hj σαk ,jk
j=1 k=1
This is much more feasible on current NISQ hardware, since the tensor producto of Pauli
matrices can be treated as n different qubits
* n +
O
σαk ,jk = ⟨σα1 ,j1 ⊗ . . . ⊗ σαn ,jn ⟩
k=1
therefore measuring this expected value requires shallower circuits than computing the
whole ⟨H⟩ which has size exponential size. We observe that this is an oversemplification
and we are glossing over a lot of details, both from a theoretical and physical point of
view, but such specifics are definitely outside the scope of this discussion as they would
require an entire chapter on their own.
The last thing that we are going to mention about the VQE is its versatility. We showed
how with this technique we are able to determine the ground-state energy of a Hamiltonian
H, which is useful to know in various scientific research areas. However, in reality we
observe that the method we outlined does not depend on the meaning of H. In fact, H
really can be any self-adjoint operator that can be written as sum of “easier” operators
to measure. Consider any cost function S(x) that we seek to minimize; what we need
is a matrix HS whose eigenvalues are exactly the possible values that S(x) can assume.
Hence, by using the same trick that we used in the Born rule it suffices to consider a
matrix whose Spectral decomposition is exacly
X
HS = S(y) |y⟩ ⟨y|
y∈Y
messages.downloaded_by
lOMoARcPSD|61948123
Therefore, by executing the VQE on HS we are actually finding the lowest value of
S(y):
⟨ψ|HS ψ⟩ = ⟨HS ⟩
= E[HS | |ψ⟩]
X
= S(y) Pr[HS = S(y) | |ψ⟩]
y∈Y
≥ min S(y)
y∈Y
to get an approximation of the minimum value for our original cost function. This strategy
is used to approximate various classically intractable computational problems outside
chemistry and physics, such as
• max-cut problems, in which HS encodes the cut costs
• combinatorial optimization problems, in which HS encodes the constraints
The following procedure is a high-level overview of the implementation of this idea.
1: function VQEOptimization(S, N )
2: θ ← θ0
3: while true do
4: Generate circuit Qθ from ansatz based on θ
5: cθ ← []
6: for i ∈ [N ] do
7: |ψ(θ)⟩ ← Qθ |0n ⟩
8: ci ← HC measured on |ψ(θ)⟩
9: cθ .append(ci )
10: end for
11: ĉθ ← avg (cθ )
12: if classical machine determines that ĉθ is ok then
13: return θ
14: end if
15: θ ← θ′ ▷ θ′ computed classically
16: end while
17: end function
messages.downloaded_by
lOMoARcPSD|61948123
6
Shor’s algorithm
TODO introduction
impor-
tance
TODO alg +
connec-
tion w
qpe
This is the usual division with remainder, which defines modular arithmetic, for in-
stance
31 = 4 · 7 + 3
Indeed, with equivalence classes we would write that
31 ≡ 3 mod 7
messages.downloaded_by
lOMoARcPSD|61948123
We will not replace Ux inside the first sum for now in order to prove that Ux is unitary.
But first, we need to present a result in number theory.
Theorem 6.1
If x and N are coprime, it holds that
messages.downloaded_by
lOMoARcPSD|61948123
Proposition 6.2
The operator Ux is unitary, and in particular
X X
Ux† = |y⟩ (Ux |y⟩)† + |y⟩ ⟨y|
y<N y≥N
Proof. It is easy to prove the correctness of Ux† , so we are going to prove that Ux is unitary
directly. this
proof
! ! is to be
rewrit-
ten
X X X X
Ux† Ux = |y⟩ (Ux |y⟩)† + |y⟩ ⟨y| Ux |z⟩ ⟨z| + |z⟩ ⟨z|
y<N y≥N z<N z≥N
! !
X X X X
= |y⟩ ⟨Ux y| + |y⟩ ⟨y| |Ux z⟩ ⟨z| + |z⟩ ⟨z|
y<N y≥N z<N z≥N
X X X X
= |y⟩ ⟨Ux y|Ux z⟩ ⟨z| + |y⟩ ⟨Ux y|z⟩ ⟨z| + |y⟩ ⟨y|Ux z⟩ ⟨z| + |y⟩ ⟨y|z⟩ ⟨z|
y,z<N y<N y≥N y,z≥N
z≥N z<N
Now note that if z ≥ N and y < N , by definition of Ux we have that Ux |y⟩ = |xy mod N ⟩,
hence it will be a basis state among |0⟩ , . . . , |N − 1⟩. Therefore, if z > N we are guar-
anteed that |z⟩ and |Ux y⟩ are orthogonal, i.e. ⟨Ux y|z⟩ = 0 — we recall that N is not the
size of the space in this context, is just a composite number, indeed the size of the space
we are considering is 2k . Therefore, we have that
X X
|y⟩ ⟨Ux y|z⟩ ⟨z| = |y⟩ ⟨y|Ux z⟩ ⟨z| = 0
y<N y≥N
z≥N z<N
so we conclude that
X X X X
Ux† Ux = |y⟩ ⟨Ux y|Ux z⟩ ⟨z| + |y⟩ ⟨Ux y|z⟩ ⟨z| + |y⟩ ⟨y|Ux z⟩ ⟨z| + |y⟩ ⟨y|z⟩ ⟨z|
y,z<N y<N y≥N y,z≥N
z≥N z<N
X X
= |y⟩ ⟨Ux y|Ux z⟩ ⟨z| + |y⟩ ⟨y|z⟩ ⟨z|
y,z<N y,z≥N
X X X
= |y⟩ ⟨Ux y|Ux z⟩ ⟨z| + |y⟩ ⟨Ux y|Ux z⟩ ⟨z| + |y⟩ ⟨y|z⟩ ⟨z|
y,z<N : y,z<N : y,z≥N
y≡z mod N y̸≡z mod N
xy ≡ xz mod N ⇐⇒ y ≡ z mod N
messages.downloaded_by
lOMoARcPSD|61948123
thus getting
X X X
Ux† Ux = |y⟩ ⟨Ux y|Ux z⟩ ⟨z| + |y⟩ ⟨Ux y|Ux z⟩ ⟨z| + |y⟩ ⟨y|z⟩ ⟨z|
y,z<N : y,z<N : y,z≥N
y≡z mod N y̸≡z mod N
X X
= |y⟩ ⟨z| + |y⟩ ⟨y|z⟩ ⟨z|
y,z<N : y,z≥N
y≡z mod N
X X
= |y⟩ ⟨z| + |y⟩ δyz ⟨z|
y,z<N : y,z≥N
y=z
X X
= |y⟩ ⟨y| + |y⟩ ⟨y|
y<N y≥N
X
= |y⟩ ⟨y|
y
=I
We did not provide any reason to why we defined the operator Ux as such, but before
giving a geometrical intuition consider the following proposition.
Theorem 6.2
Given N ∈ N, and x ∈ [0, N − 1], if r is the order of x modulo N , it holds that
r−1
1 X −2πisk/r k
∀s ∈ [0, r − 1] |us ⟩ = √ e |x mod N ⟩
r k=0
is an eigenvector of Ux .
Proof. Fix s ∈ [0, r − 1]; to prove that |us ⟩ is an eigenvector of Ux we need to show that
there exists some phase φs such that
messages.downloaded_by
lOMoARcPSD|61948123
TODO intuizione
geomet-
rica
What happenns if the input of Ux is |x0 ⟩? By definition of our problem x < N , there-
fore
Ux |x0 ⟩ = |x · x0 mod N ⟩ = |x1 mod N ⟩
Indeed in general it’s easy to see that
Ux |xk ⟩ = |xk+1 mod N ⟩
In other words Ux is cycling through x’s powers, which also implies that when k = r − 1
we get that
Ux |xr−1 ⟩ = |xr mod N ⟩ = |1 mod N ⟩
messages.downloaded_by
lOMoARcPSD|61948123
since r is the order of x modulo N . Moreover, as we already know these are basis states
so they are both normalized and orthogonal to each other, thus the powers x form an
orthonormal base of the following space
which is a restriction of the whole Hilbert space that has exactly r dimensions. Now look
again at how the eigenvectors of Ux are defined:
r−1
1 X −2πisk/r k
∀s ∈ [0, r − 1] |us ⟩ = √ e |x mod N ⟩
r k=0
Indeed, it holds that |us ⟩ is basically QFT |s⟩ but taken inside Hr — the only difference
being the sign of the exponent, ndeed it technically holds that
but as we said the sign of the exponent is just a convention either sign is found in literature,
we only need to be consistent with the calculations. non ho
capito
che
The most interesting part is that, as proved in the last theorem, for any fixed s ∈ [0, N −1] c’entra
però
its associated phase φs is exactly s/r, thus if we knew how to prepare the last register
of the QPE as |us ⟩ we could recover its phase, and maybe get closer to know r itself.
However, we have two probems with this idea:
• there is really no easy or practical way to prepare the second register to some
arbitrary state
• |us ⟩ actually depends on r itself, which actually is a very big problem on its own
Thankfully, the following property will solve both of these issues at the same time.
Proposition 6.3
messages.downloaded_by
lOMoARcPSD|61948123
As we did for the proof of Proposition 5.1, because of how we split the sums we know
that k ̸= 0 hence e−2πik/r ̸= 1 because k/r is not an integer (since k ∈ [1, r − 1]), therefore
we get that
r−1 r−1
1 X 1X k 1 − (e−2πik/r )r
√ |us ⟩ = |1⟩ + |x mod N ⟩
r s=0 r k=1 1 − e−2πik/r
r−1
1X k 1 − e−2πik
= |1⟩ + |x mod N ⟩
r k=1 1 − e−2πik/r
r−1
1X k 1−1
= |1⟩ + |x mod N ⟩
r k=1 1 − e−2πik/r
= |1⟩
Indeed, this property is incredibly useful because we can provide |1⟩ to the lower register of
the QPE circuit instead of a single eigenvector, in order to compute the same algorithm but
to all the eigenvectors simultaneously. We observe that |1⟩ is essentially a superposition
of all the eigenvectors of Ux , which means that when fed to C-Ux2 as target qubit we don’t
k
messages.downloaded_by
lOMoARcPSD|61948123
QPE — and we are still preserving the superposition of eigenvectors |us ⟩. This is exactly
what we need, however it also means that the result at the end of the circuit is not
very straightforward: in standard QPE the resulting state is just the tensor product of
the single control qubits because they are independent from each other, but here we are
entangling all the control and the target qubits together at each application of C-Ux2 .
k
T ODO
r−1 t
1 X 1 O m−1
=√ √ |0⟩ + e2πi2 s/r |1⟩ ⊗ |us ⟩
r s=0 2t m=1
r−1 t
1 X 1 O
|0⟩ + e2πi0.φsm ...φst |1⟩ ⊗ |us ⟩
=√ √
r s=0 2t m=1
r−1
1 X
=√ QFTt |φs ⟩q0 ···qt−1 ⊗ |us ⟩
r s=0
r−1
QFT† (|q0 ···qt−1 ⟩) 1 X
−−−−t−−−−−−→ √ |φs ⟩ ⊗ |us ⟩
r s=0
assuming that φs = s/r can be written through t bits. This entangled quantum state
is exactly what we want, because now by measuring the first t registers we get that for
each s ∈ [0, r − 1] they will collapse into |φs ⟩ with probability 1r , and the last register will
collapse into |us ⟩ which is exactly the eigenvector associated to e2πiφs . This proves that
we truly computed the phases of all the possible eigenvectors simultaneously.
We are almost done. We now know that we can retrieve φs = s/r for each s ∈ [0, r − 1]
without even knowing a single eigenvector of Ux , but there is a problem. Say that we
messages.downloaded_by
lOMoARcPSD|61948123
want to find the order of x = 3 modulo N = 11, which is r = 5, and suppose that the
true phase that the algorithm should output is
s 2
φs = =⇒ φ2 = = 0.4
r 5
The QPE algorithm, however, cannot output this exact value, because 0.4 cannot be
written precisely in binary — in particular, the reason is that 5 does not divide 2t for
any t. This means that our algorithm will return an approximation of φ2 . Say that we
are working with 6 registers of precision and fix t = 6; then QPE will output the closest
approximation of 0.4 with 6 bits:
13
φ̃2 = 0.40625 =
32
Now, it would be a mistake to assume that r = 32! How do we proceed?
x = [a0 ; a1 , a2 , . . . , an ]
[a0 ]
[a0 ; a1 ]
[a0 ; a1 , a2 ]
...
[a0 ; a1 , a1 , . . . , an ]
338
= [2; 1, 3, 1, 5, 4]
121
messages.downloaded_by
lOMoARcPSD|61948123
We will use continued fractions to recover r from φ̃s . Suppose that QPE outputs φ̃2 = 1332
as in the previous example. Without going into the details, there is a classical algorithm
which is able to recover its continued fraction in O(L3 ) time — where L = ⌈log N ⌉. Thus,
we get that
1
φ̃2 = 0 + = [0; 2, 2, 6]
1
2+
1
2+
6
Now, to recover 5 we just need to compute the convergents:
2
[0] = 0
1
[0; 2] =
2
2
[0; 2, 2] =
5
13
[0; 2, 2, 6] =
32
Finally, since we know that r is the order of x modulo N , we just need to pick the
convergent with the smallest denominator r such that xr ≡ 1 mod N . In our example we
had x = 3 and N = 11, thus
32 ≡ 9 ̸≡ 1 mod 11
35 ≡ 243 ≡ 1 mod 11
This is how we can recover r = 5 — to be precise, there are theoretical results which
guarantee that 52 shows among the convergents of 32
13
but this is ouside the scope of our
discussion.
N = pα1 1 · . . . · pαmm
messages.downloaded_by
lOMoARcPSD|61948123
Theorem 6.4
Given any L-bit long composite natural number N ∈ N, let x ∈ [2, N ] different from
N − 1 be a solution to the equation
x2 ≡ 1 mod N
Theorem 6.5
Given any N ∈ N odd composite positive integer with m prime factors, let x ∈R
[1, N − 1] such that gcd(1, N − 1) = 1. Then, if r is the order of x modulo N , it holds
that
1
Pr[r is even and xr/2 ̸≡ 1 mod N ] ≥ 1 − m
2
TODO write
the alg
and
TODO TODO explain
stuff?
TODO size of
QPE
write
QPE
alg
size
of Ux
gates
messages.downloaded_by
lOMoARcPSD|61948123
Grover’s algorithm
7
The algorithm that we are going to present in this chapter is, together with Shor’s algo-
rithm, one of the most famous quantum algorithms we currently know. In 1996, Grover
[Gro97] published a landmark paper called “Quantum Mechanics Helps in Searching for a
Needle in a Haystack”, which contains the algorithm that we will present in this chapter.
In the same year, Grover famously noted:
It might be possible to combine the search scheme of this paper with Shor
[Sho] and other quantum mechanical algorithms to design faster algorithms
This statement led many to speculate that Grover may have drawn inspiration from Shor’s
algorithm, although the exact influence remains unclear. Nevertheless, we will see at the
end of the chapter that it is indeed possible to apply the QPE technique to Grover’s
algorithm.
where A is our array, and S is the set of solution elements, the problem asks to return an
x such that f (x) = 1, i.e. such that A[x] is a solution.
With a classical computation, it is easy to see that we need O M N
accesses to A to solve
our problem, however we will see that the algorithm Grover developed is able to return
messages.downloaded_by
lOMoARcPSD|61948123
q
a “solution index” in O M
N
with high probability, i.e. Grover’s algorithm provides
a quadratic speedup compared to any classical algorithm — however, it is probabilis-
tic.
Before explaining the details of the algorithm, we need to define some new operators that
will be used in Grover’s algorithm, and introduce some general notation:
• given an arbitrary qubit |ψ⟩, we will write its superposition of states as follows
X
|ψ⟩ = αb |b⟩
b∈Bn
where
P
b∈Bn |αb | = 1
• we define an operator Of (where f is the indicator function of the array defined
before) that computes as follows:
∀x ∈ Bn Of |x⟩ := (−1)f (x) |x⟩
• finally, we will define an operator G that will simply compose the last two operators
we described
G = W · Of
1: function Grover(f , q0 )
2: q0 ← H h⊗n (q0 )q i
3: for i ∈ 1, O N
M
do ▷ where N = 2n
4: q0 ← G(q0 )
5: end for
6: return measure(q0 )
7: end function
First of all, we see that this algorithm takes only n qubits as input, however the actual
implementation of the algorithm is slightly different, as shown in the following quantum
circuit below.
messages.downloaded_by
lOMoARcPSD|61948123
q0⊗n H ⊗n
G ··· G
q1
Indeed, we can see that the real quantum circuit takes n + 1 inputs, and the additional
register is called “ancilla” becuase its only purpose is to actually implement the Of op-
erator, which is designed exactly as if it was the Uf black-box we discussed in previous
algorithms. This can be done thanks to Lemma 4.1, which guarantees that if we give |−⟩
as the second input to Uf we get
which implies that the ancilla register will sill be |−⟩, therefore we can just ignore the
second register completely throughout the whole computation, and we are sure that Of
computes correctly.
Furthermore, before proceeding, let us prove that G is actually a unitary operator, i.e.
that this is a valid quantum computation.
Proposition 7.1
The Of , W and G operators are unitary.
Proof. By Proposition 2.11, it suffices to prove that both Of and W are unitary operators.
Claim: The Of operator is unitary
Proof of the Claim. First, we notice that the Of operator computes as follows:
Of = Of · I
X
= Of |x⟩ ⟨x|
x
(7.1)
X
= Of |x⟩ ⟨x|
x
X
= (−1)f (x) |x⟩ ⟨x|
x
messages.downloaded_by
lOMoARcPSD|61948123
Now that we know this operator is unitary, we can delve into the details of the algorithm.
To see what happens at each iteration, we will describe the complete state of the system
in a rather unusual way. Let |a⟩ and |b⟩ be the following superpositions:
1 X 1 X
|a⟩ := √ |x⟩ |b⟩ := √ |x⟩
N −M M x∈S
x∈S
In other words, |a⟩ is the uniform superposition of non-solution indices, and |b⟩ is the
superposition of solution [Link], it’s easy to see that |a⟩ and |b⟩ are orthogonal,
so they form an orthonormal basis for a 2D space.
Furthermore, because of how we defined |a⟩ and |b⟩, we can rewrite the uniform superpo-
sition
1 X
|s⟩ = √ |x⟩
N x∈B
messages.downloaded_by
lOMoARcPSD|61948123
as shown below r r
N −M M
|s⟩ = |a⟩ + |b⟩
N N
This is quite interesting, because it means that we can describe |s⟩ in terms of |a⟩ and
|b⟩. Let us do exactly this, and plot the resulting graph on a 2D space that has |a⟩ and
|b⟩ as axis.
We observe that:
• both |s⟩, |a⟩ and |b⟩ are normalized, and all the vectors that we are going to consider
are quantum states, so they will be normalized too, therefore we can restrict our
focus on a 2D circumference of radius 1 — this plane is usually called Grover plane
q q
• since we expect that M ≪ N , we have that M N
≪ N −M
N
, which basically means
that the vector |s⟩ is almost parallel to |a⟩ (the bigger is the numer of solution
indices, the bigger the angle between |s⟩ and |a⟩)
Consider any state |ψ⟩ = x∈Bn αx |x⟩; we observe that
P
X
Of |ψ⟩ = Of αx |x⟩
x∈Bn
X
= αx Of |x⟩
x∈Bn
X
= αx (−1)f (x) |x⟩
x∈Bn
which basically means that each time we apply the Of operator we are flipping the sign
of the amplitudes of the compoents of |ψ⟩ that represent solution indices. In other words,
the Of operator flips its input w.r.t. |a⟩.
messages.downloaded_by
lOMoARcPSD|61948123
where α |s⟩ is the projection of |ψ⟩ along |s⟩’s space — thus α = ⟨s|ψ⟩ — and |s⊥ ⟩ is the
projection of |ψ⟩ along the space that is orthogonal to |s⟩’s. Therefore, we have that
which means that what W actually performs is leaving the component along |s⟩’s space
unchanged, and it flips the sign of the component of the orthogonal space. In other words,
what W computes is the reflection of |ψ⟩ w.r.t. |s⟩.
We can finally describe Grover’s algorithm in detail. First, we see that
q0
= |0⟩⊗n
H ⊗n (q0 ) 1 X n
−−−−−→ √ (−1)0 ·x |x⟩
2n x∈Bn
1 X
=√ |x⟩
N x∈Bn
= |s⟩
Indeed, the only purpose of the first Hadamard operator is to “move” the initial state
slightly away from |a⟩ — and also making each component initially equally likelly. Now,
let’s see what happens at each application of the G = W · Of operator:
• as previously shown, the operator Of reflects its input w.r.t. the |a⟩ axis — below
we show what happens when we first apply Of q0 = Of |s⟩:
messages.downloaded_by
lOMoARcPSD|61948123
• additionally, as previously explained the operator W reflects its input w.r.t. the
axis described by the |s⟩ vector, thus when we compute W · Of q0 we will end up
with the following vector:
• this suggests that each time we apply the operator G we are making q0 closer and
closer to |b⟩, as depicted below:
messages.downloaded_by
lOMoARcPSD|61948123
This is the core idea of Grover’s algorithm: if we rewrite q0 in terms of |a⟩ and |b⟩
q0 = β0 |a⟩ + β1 |b⟩
we get that through Grover’s algorithm we transformed q0 such that it is now very close to
|b⟩, meaning that β0 ≪ β1 . This direcly implies that when we will measure q0 at the end
of Grover’s procedure the likelihood that it will collapse into some |x⟩ that is a component
of |b⟩ — i.e. a solution index — is very high. In other words, what happens with Grover’s
algorithm is that we gradually increase the amplitudes of the solution indices, in order to
maximize the probability that our qubit will collapse in one them when it will be measured
at the end of the procedure.
Now
qthat we know how Grover’s algorithm works, the only thing left to discuss is the
O N
M
factor. Why is it guaranteed that after this amount of applications of the G
operator we are done with the algorithm? Well, we actually have the opposite problem:
in reality, we have to stop early enough. Consider again how Grover’s algorithm operates
in the Grover plane; clearly, if we apply G too many times, what happens is that q0 will
end up past |b⟩ itself: drawing
Let the angle between |a⟩ and |s⟩ be θ; since Of flips q0 w.r.t. |a⟩, and W flips Of q0
w.r.t. |s⟩, G will cumulatively rotate q0 by 2θ: More formally, we can actually show that drawing
messages.downloaded_by
lOMoARcPSD|61948123
Proposition 7.2
The Grover operator G can be rewritten in the basis {|a⟩ , |b⟩} as follows:
cos 2θ − sin 2θ
G=
sin 2θ cos 2θ
We already saw how the Of operator flips its input w.r.t. the |a⟩ axis, indeed its action
on |v⟩ would be the following:
messages.downloaded_by
lOMoARcPSD|61948123
Thus, starting from the definition of G, by the two previous claims we have that
G |v⟩ = W · Of |v⟩
= W · (α |a⟩ − β |b⟩)
= (2 |s⟩ ⟨s| − I)(α |a⟩ − β |b⟩)
= 2 |s⟩ ⟨s| (α |a⟩ − β |b⟩) − (α |a⟩ − β |b⟩)
= 2 |s⟩ (cos θ |a⟩ + sin θ |b⟩)† (α |a⟩ − β |b⟩) − (α |a⟩ − β |b⟩)
= 2 |s⟩ (cos θ ⟨a| + sin θ ⟨b|)(α |a⟩ − β |b⟩) − (α |a⟩ − β |b⟩)
= 2 |s⟩ (α cos θ − β sin θ) − (α |a⟩ − β |b⟩)
= 2(cos θ |a⟩ + sin θ |b⟩)(α cos θ − β sin θ) − (α |a⟩ − β |b⟩)
= 2α cos2 θ |a⟩ − 2β cos θ sin θ |a⟩ + 2α sin θ cos θ |b⟩ − 2β sin2 θ |b⟩ − α |a⟩ + β |b⟩
= α 2 cos2 θ − 1 − 2β cos θ sin θ |a⟩ + β 1 − 2 sin2 θ + 2α sin θ cos θ |b⟩
Indeed, with each application of G we are rotating q0 by 2θ, which means that at the k-th
application it holds that
for any k ∈ N, where the additional 1 comes from the fact that q0 = |s⟩ through the
Hadamard transformation at the start of the process. Thus, to evaluate the optimal
number of iterations we need to find the optimal k, i.e. the one that maximizes the
probability of measuring a solution index, which is equal to the squared amplitude of |b⟩,
namely
Pr[measure(q0 ) = |b⟩] = sin2 [(2k + 1)θ]
Hence, we have that sin2 [(2k + 1)θ] = 1 when (2k + 1)θ = π2 , and solving for k we get
that
π 1
k= −
4θ 2
Lastly, since θ is the angle between |a⟩ and |s⟩, we can rewrite |s⟩ as
messages.downloaded_by
lOMoARcPSD|61948123
and therefore
π 1
k= −
4θ 2
π 1
= r −
M 2
4 arcsin
N
π
≤ r
M
4 arcsin
N
π
≤ r
M
4
N
r
π N
=
4 M !
r
N
=O
M
which finally explains the quadratic speedup of Grover’s algorithm w.r.t. the classical
version of the problem.
As a final note, we observe that Grover’s algorithm assumes that θ ≤ π4 , otherwise we
overshoot |b⟩ with a single iteration of the G operator — since θ > π4 would mean that
|s⟩ is placed on the “upper half” of the Grover plane. However, to ensure this constraint
on θ we only need that M ≤ N2 , i.e. at most half of the elements in our array are solution
elements. Indeed, we see that
r r r
N M 1 1 π
M≤ =⇒ sin θ = ≤ =⇒ θ ≤ arcsin =
2 N 2 2 4
What can we do if the number of solutions is more than half the size of the array? We
simply invert the problem and find the non-solutions!
messages.downloaded_by
lOMoARcPSD|61948123
1 X X
=√ αx ⟨y|x⟩
N y∈Bn x∈Bn
1 X
=√ αx
N x∈Bn
√
= N αψ
where αψ is the average amplitude of |ψ⟩. This implies that
W |ψ⟩ = (2 |s⟩ ⟨s| − I) |ψ⟩
X
= 2 |s⟩ ⟨s|ψ⟩ − αx |x⟩
x∈Bn
√ X
= 2 |s⟩ N αψ − αx |x⟩ (for the previous observation)
x∈Bn
!
1 X √ X
=2 √ |y⟩ N αψ − αx |x⟩
N y∈Bn x∈Bn
X
= (2αψ − αx ) |x⟩
x∈Bn
In other words, when we apply W to a superposition of states, what happens is that each
amplitude of the basis states is trasformed as follows:
W : αx → 2αψ − αx
To understand why this is important, let’s look at what happens in Grover’s algorithm
after the first Hadamard application. TODO da
finire
messages.downloaded_by
lOMoARcPSD|61948123
the probability of finding a solution, without oscillating back down |a⟩. This algorithm is
called Fixed-Point Quantum Search, becuase the solutions actually become a “stable
fixed point” of the transformation — i.e. once you reach a good solution, further iterations
leave it basically unchanged. Indeed, with Grover’s search each iteration is a constant-
angle rotation, while in fixed-point search we will see that the phase angles in each rotation
changes such that the rotation angle decreases over time.
First, we need to define two new operators:
where |s⟩ is the starting state and |t⟩ is the target state (in Grover’s algorithm this was
|b⟩) — this is the original notation that Grover used in his paper, and actually explains
why we used |s⟩ in the previous version of the algorithm, it’s just the “start”. These two
operators are called phase shift operators, and it can be easily showed that they are
both unitary operators — we will omit the calculations here.
What are these two operators in the first place? When we presented the W operator,
we also noticed how it actually performes a reflection of its input w.r.t. the space of |s⟩.
Well, through a very similar argument it can be shown that
W ⊥ := I − 2 |s⟩ ⟨s|
performs a reflection of its input w.r.t. the space orthogonal to |s⟩ — indeed, we end up
with
W ⊥ |ψ⟩ = β |s⊥ ⟩ − α |s⟩
If we now look at the Rs operator, we can see that when we actually compute the reflection
it performs we end up with
Rs |ψ⟩ = β |s⊥ ⟩ + eiθ α |s⟩
This suggests that what Rs actually computes is a “soft reflection” w.r.t. the space
perpendicular to |s⟩. Through an analogous argument, we can see that
meaning that Rt computes a “soft reflection” w.r.t. the space perpendicular to |t⟩ —
however, we observe that the latter is literally the space of |a⟩, indeed O in Grover’s
algorithm could have been defined as
O = I − 2 |b⟩ ⟨b|
|⟨t|U s⟩|2 = 1 − ε
We observe that
messages.downloaded_by
lOMoARcPSD|61948123
Lemma 7.1
It holds that
h 2 i
G |s⟩ = U |s⟩ eiθ + |Uts |2 eiθ − 1 + |t⟩ Uts eiθ − 1
messages.downloaded_by
lOMoARcPSD|61948123
Most importantly, this equality can be used in the following proposition, which shows that
we can actually find an angle θ for which the distance from |t⟩ decreases significantly.
Proposition 7.3
There exists an angle θ such that
messages.downloaded_by
lOMoARcPSD|61948123
π 2
= (1 − ε) · (1 + ε)ei 3 − 1
√ ! 2
1 4
= (1 − ε) · (1 + ε) +i −1 (by Euler’s formula)
2 2
√ √ 2
1 3 ε 3
= (1 − ε) · + i + +i ε−1
2 2 2 2
√ 2
ε 1 3
= (1 − ε) · − + i (1 + ε)
2 2 2
√
!2
2
ε 1 3
|z|2 = ℜ2 (z) + ℑ2 (z)
= (1 − ε) · − + (1 + ε)
2 2 2
= (1 − ε) · (1 + ε + ε2 )
= 1 + ε + ε2 − ε − ε2 − ε3
= 1 − ε3
This shows that by applying G the probability of measuring |t⟩ has increased from 1 − ε
to 1 − ε3 .
Indeed, it can be shown that by defining the following recursive sequence of operators
(
U0 := U m=0
†
Um = Um−1 Rs Um−1 Rt Um−1 m ≥ 1
we get that
Pr[measure(Um |s⟩) = |t⟩] = |⟨t|Um s⟩|2 = 1 − ε2qm +1
where qm is the number of queries of f (x).
TODO drawing
of the
vector
Unfortunately, there already exists a classical probabilistic algorithm that the failure that
grows
probability drops as εq+1 after q queries to f . Thus, the quantum advantage with this mono-
toni-
method is lost. cally
So, what do we do now? In 2014 Yoder, Low, and Chuang [YLC14] proposed a fixed-
point quantum serach algorithm that monotonically converges to the target state while
still retaining the quadratic advantage of the original Grover’s algorithm over classical
algorithms. The algorithm involves phase-shift operators that are parametrized with
angles different from θ = π3 , and again involes building a sequence of operators using
messages.downloaded_by
lOMoARcPSD|61948123
said phase shifts. However, the details of this result are way beyond the scope of our
discussion, so we won’t describe the details of their findings.
Proposition 7.4
This means that we can use the QPE algorithm with the matrix G in order to obtain an
estimate of θ! In particular, with this information we can actually solve two problems at
once:
messages.downloaded_by
lOMoARcPSD|61948123
7.4. Exercises
It can be proven that the quantum counting circuit estimates ±2θ — to be precise, it
actually estimates 2θ or 2π − 2θ since QPE does not return negative angles — to a degree
of accuracy up to a desired 2− m with probability at least 1−ε. Moreover, it can be shown
that
√
N
M̃ − M < 2 M N + m+1 2−m
2
where M̃ is the estimated value of M through
n the QPE algorithm. For instance, choosing
m = 2 + 1 and ε = 6 , we get that t = 2 + 3 and an estimation of M with an error
n 1
of about
√
r
M 1
M̃ − M < + = O( M )
2 4
√
with only O(2 ) = O( N ) iterations of the Grover operator, i.e. array accesses. Classi-
t
cally, to know the value of M with the same error in the estimate we would necessarily
need O(N ) accesses.
Lastly, another problem that quantum counting solves is knowing if M is 0 or not. Indeed,
Grover’s algorithm relies on the assumpion that M ̸= 0, i.e. there are solution elements,
otherwise the procedure actually does nothing.
7.4 Exercises
Problem 7.1
Starting from the fact that W is the operator that computes the inversion about the
mean of the coefficients of its inputs, show that
W = 2 |s⟩ ⟨s| − I
where |s⟩ = √1
P
N x |x⟩.
messages.downloaded_by
lOMoARcPSD|61948123
7.4. Exercises
for some coefficients αx , and assume that W computes the inversion about the mean of
each αx . This means that
W : αx → 2αψ − αx
where αψ is the average of the coefficients of |ψ⟩. Therefore, we have that
X
W |ψ⟩ = (2αψ − αx ) |x⟩
x
X X
= 2αψ |x⟩ − αx |x⟩
x x
! !
1 X X
=2 αy |x⟩ − |ψ⟩
N y x
! !
1 X 1 X
=2 √ αy √ |x⟩ − |ψ⟩
N y N x
!
1 X
=2 √ αy |s⟩ − |ψ⟩
N y
! !
1 X X
=2 √ ⟨z| αw |w⟩ |s⟩ − |ψ⟩
N z w
= 2 ⟨s|ψ⟩ |s⟩ − |ψ⟩
= (2 |s⟩ ⟨s| − I) |ψ⟩
Problem 7.2
Given an array of size N = 4 which contains only one “solution” element at index
3, prove that Grover’s algorithm finds the solution in only 1 application of the G
operator.
since the only solution element of the array is in the last position. Let’s see what happens
after running Grover’s algorithm with only 1 application of the G operator (we will omit
messages.downloaded_by
lOMoARcPSD|61948123
7.4. Exercises
q0
= |0⟩⊗2
H ⊗2 (q0 )
−−−−−→(H ⊗ H)(|0⟩ ⊗ |0⟩)
=H |0⟩ ⊗ H |0⟩
= |+⟩ ⊗ |+⟩
1 1
= √ (|0⟩ + |1⟩) ⊗ √ (|0⟩ + |1⟩)
2 2
1
= (|00⟩ + |01⟩ + |10⟩ + |11⟩)
2
Of (q0 ) 1
−−−−→ (Of |00⟩ + Of |01⟩ + Of |10⟩ + Of |11⟩)
2
1
= (|00⟩ + |01⟩ + |10⟩ − |11⟩)
2
The last part of the calculations involves applying the W operator on the state, but since
the calculations are quite dense we will see what happens with only one of the products
and other ones can be proved to be analogous.
Claim: W |00⟩ = 12 (− |00⟩ + |01⟩ + |10⟩ + |11⟩)
1 P
Proof of the Claim. Recall that |s⟩ = √ x∈Bn |x⟩ therefore, in our case, we have
N
that
1
|s⟩ = (|00⟩ + |01⟩ + |10⟩ + |11⟩)
2
and ⟨s| is defined accordingly. Hence, we have that
W |00⟩
=(2 |s⟩ ⟨s| − I) |00⟩
=2 |s⟩ ⟨s|00⟩ − |00⟩
1
=2 |s⟩ (⟨00| + ⟨01| + ⟨10| + ⟨11|) |00⟩ − |00⟩
2
= |s⟩ (⟨0|0⟩ ⟨00⟩ + ⟨0|0⟩ ⟨1|0⟩ + ⟨1|0⟩ ⟨00⟩ + ⟨1|0⟩ ⟨1|0⟩) − |00⟩
= |s⟩ |⟨0|0⟩|2 − |00⟩
= |s⟩ − |00⟩
1
= (|00⟩ + |01⟩ + |10⟩ + |11⟩) − |00⟩
2
1
= (− |00⟩ + |01⟩ + |10⟩ + |11⟩)
2
messages.downloaded_by
lOMoARcPSD|61948123
7.4. Exercises
In other words, the input now lies precisely over |b⟩, meaning that Grover’s algorithm
correctly found the solution element with 1 application of the G operator.
messages.downloaded_by
lOMoARcPSD|61948123
8
Quantum circuits
So far, we have treated quantum gates primarily as “abstract” unitary operators acting
on quantum states. While this perspective is sufficient to define quantum algorithms and
reason about their correctness, it leaves an important question unanswered: how are these
gates actually constructed? In other words, given a desired unitary transformation, how
can it be realized using a finite set of elementary operations that a quantum computer
can physically implement? The central result of this chapter shows that any controlled
single-qubit unitary can be constructed using only a restricted set of single-qubit gates,
and a small number of CNOT gate.
Proposition 8.1
It holds that S = T 2 .
In this chapter, we will see any arbitrary quantum computation can be reduced to a
combination of
• the Hadamard H, S and T gates
• the CNOT gate
messages.downloaded_by
lOMoARcPSD|61948123
The importance of this result stems from the fact that these gates can be physically
realized, and can therefore be treated as the building blocks of any other unitary trans-
formation. We will discuss we this set of gates is both necessary and sufficient to achieve
quantum approximate universality to arbitrary accuracy — unfortunately, it is not
known if we can achieve exact universality avoiding an exponential number of gates in
the general case.
In the first section of this chapter we will discuss the necessity of Pauli matrices. But
first, we need to present a new type of matrices, the rotation operators which apply
rotations on the x, y and z axes.
The rotation operators Ri (θ) that apply a rotation of an angle θ on the i-th axis
(for i ∈ {x, y, z}) are defined as follows:
cos 2θ −i sin 2θ
Rx (θ) := ≡ e−iθX/2
−i sin 2θ cos 2θ
cos 2θ − sin 2θ
Ry (θ) := ≡ e−iθY /2
sin 2θ cos 2θ
−iθ/2
e 0
Rz (θ) := ≡ e−iθZ/2
0 eiθ/2
Lemma 8.1
For any real nubmer x ∈ R and matrix A such that A2 = I, it holds that
Proof. From the Taylor expansions of ex , sin x and cos x we get the following
messages.downloaded_by
lOMoARcPSD|61948123
+∞
iAx
X (iAx)n
e =
n=0
n!
+∞ +∞
X (iAx)n X (iAx)n
= +
neven
n! n odd
n!
+∞ +∞
X (iAx)2k X (iAx)2k+1
= +
k=0
(2k)! k=0
(2k + 1)!
+∞ 2k +∞
X i A2k 2k X i2k+1 A2k+1 2k+1
= x + x
k=0
(2k)! k=0
(2k + 1)!
+∞ +∞
X (i2 )k (A2 )k 2k X i · (i2 )k · A · (A2 )k 2k+1
= x + x
k=0
(2k)! k=0
(2k + 1)!
+∞ +∞
X (−1)k 2k X (−1)k 2k+1
=I x + iA x (A2 = I = I k )
k=0
(2k)! k=0
(2k + 1)!
= I cos(x) + iA sin(x)
Corollary 8.1
The rotation operators can be rewritten through the Pauli gates as follows:
θ θ
Rx (θ) = cos I − i sin X
2 2
θ θ
Ry (θ) = cos I − i sin Y
2 2
θ θ
Rz (θ) = cos I − i sin Z
2 2
Most importantly, the corollary above already implies that any type of rotation can be
expressed in terms of only linear combinations of Pauli matrices. However, there is
a catch: the rotation matrices written in these form are not constructible in practice. In
the first part of this chapter we will not address this issue, and we will assume that we
can construct rotation matrices of arbitrary angles. Then, in the second part of of our
discussion we will discuss physical realizability of the ideas we will present.
Nevertheless, the above result together with the next theorem allow us to express any
arbitrary single-qubit operation in terms of rotation matrices only.
messages.downloaded_by
lOMoARcPSD|61948123
Proof sketch. Since U is unitary, by Proposition 2.10 we know that its rows and columns
must be orthonormal. This property implies the existence of real numbers α, β, γ, δ ∈ R
such that HOW????
cos γ2 −ei(α−β/2+δ/2) sin γ2
i(α−β/2−δ/2)
e
U=
ei(α+β/2−δ/2) sin γ2 ei(α+β/2+δ/2) cos γ2
Lastly, this formulation can be rewritten as the statement describes.
This theorem already shows how much we can achieve through rotation matrices alone.
However, as we already encountered multiple times throughout our discussion, we know
that this is not general enough. Indeed, what we are still missing is controlled opera-
tions. For instance, consider the controlled NOT, the CNOT operator; even if the CNOT
is a unitary transformation, it acts on 2 qubits, which means that we cannot apply the
theorem above. We observe that this problem already hints at reason why we included
the CNOT in the discussion at the beginning of this chapter — akeen eye might have also
noticed that without the CNOT we don’t know how to create EPR pairs! We will see
how to solve these problems in the next section.
However, we cannot turn this controlled operator directly into a quantum gate. This
formulation tells us how C-U looks like in a matrix form, but what does the actual gate
look like?
Before we progress, we must first prove a corollary of the Z-Y single-qubit decomposi-
tion.
Corollary 8.2
If U is a unitary operation on a single-qubit, there exist unitary operators A, B and C
on a single-qubit such that ABC = I and
U = eiα AXBXC
Proof. Consider the real values α, β, γ and δ obtained from the previous theorem, and
define the following operators
• A := Rz (β)Ry γ2
• B := Ry − γ2 Rz − δ+β
2
messages.downloaded_by
lOMoARcPSD|61948123
• C := Rz δ−β
2
Now, given any unitary transformation U , our next goal is to understand how to imple-
ment C-U using only single-qubit operations and the CNOT gate, leveraging the result
above. Consider two qubits q0 and q1 , and construct the operators A, B and C as de-
scribed by the corollary. Suppose that q0 is the control qubit; then, the controlled-U
operator should then work as follows:
• if q0 is not set, q1 must be left unchanged
• if q0 is set, we must apply U to q1
In the first case, we can leverage the fact that A, B and C satisfy
ABC = I
by the corollary, indeed the following circuit is already enough to construct C-U :
messages.downloaded_by
lOMoARcPSD|61948123
q0 • • •
iα
e 0
q1 C B A
0 eiα
q1 C B A
messages.downloaded_by
lOMoARcPSD|61948123
q0 •
q1 •
q2 U
Even if we will not prove the following result, we can use this powerful property to
construct a circuit as shown that computes C 2 (U ).
Proposition 8.2
Every untary operator has a unitary square root.
q0 • • •
q1 • •
q2 V V† V
messages.downloaded_by
lOMoARcPSD|61948123
This seeminly uninteresting quantum circuit is actually very important. What happens
when U = X? It can be proven that
(1 − i)(I + iX)
V =
2
is such that V 2 = X = U . This quantum gate depicted below
q0 •
q1 •
q2
is called quantum Toffoli gate, and as the name suggests there is also a classical Toffoli
gate that computes exactly as we would expect:
We see that this binary function flips c only if both a and b are set to 1, since
¬c = c ⊕ 1
First, we shall show how the quantum Toffoli can be constructed using only the gates we
allowed ourselves at the beginning of the chapter:
q0 • • • • T
q1 • • T† T† S
q2 H T† T T† T H
Figure 8.4: The quantum Toffoli gate written with only H, S, T and CNOT gates.
not the Toffoli gate! We will leave the correctness of this quantum circuit as an exercise
for the reader.
Surprisingly, we can utilize the quantum Toffoli gate to construct C n (U ). The idea is to
simply chain multiple quantum Toffoli gates in order to enforce that all the control qubits
messages.downloaded_by
lOMoARcPSD|61948123
8.3. Universality
are set. To achieve this, we need an overhead of n − 1 work qubits set to |0⟩, as shown
below.
|c1 ⟩ • •
|c2 ⟩ • •
|c3 ⟩ • •
|c4 ⟩ • •
|c5 ⟩ • •
|0⟩ • •
|0⟩ • •
|0⟩ • •
|0⟩ •
q0 U
This circuit can be fully constructed with our restrictions, since it only uses quantum
Toffoli gates and a single-control single-qubit U gate.
As a final note, it can be proven that this idea can be extended such that any unitary
operator U acting on an arbitrary number of qubits can be is this
even
true?
8.3 Universality
Now that we have introduced the Toffoli gate in the quantum context, it’s a good opportu-
nity to look at what the Toffoli gate can do in classical computing, and why it’s actually
special even in the classical context.
We already mentioned how quantum computation is reversible, since each operator is
unitary. However, we also metioned that classical computaion admits reversible compu-
tation as well. It turns out that the Toffoli gate allows such goal. Indeed, we observe that
by associativity of the XOR it holds that
(c ⊕ (a ∧ b)) ⊕ (a ∧ b) = c ⊕ (a ∧ b) ⊕ (a ∧ b) = c
messages.downloaded_by
lOMoARcPSD|61948123
8.3. Universality
Proof. Since it is well known that the NAND gate is univesal, we just need to simulate
the NOT and the AND operators with the Toffoli gate. Then, if we denote with T3 (a, b, c)
the third output of the Toffoli gate, we get that
• the NOT gate can be simulated as follows:
∀x ∈ B T3 (1, 1, x) = x ⊕ (1 ∧ 1) = x ⊕ 1 = ¬x
This means that the Toffoli gate alone is enough to perform any classical and fully re-
versible computation.
But we do we need 3 inputs? It is easy to see that a 1-bit gate is definitely not enough
to achieve classical reversibility. Our intuition would suggest that adding an ancilla wire
that keeps track of the original input should be able to solve this issue. However, the
following holds.
This result concludes that the Toffoli gate cannot be improved any further. Therefore,
from a classical viewpoint the construction presented in Section 8.2.2 is remarkable: in
quantum computing we can construct the Toffoli gate from one and two qubit gates, and
since reversibility is an intrinsic property of quantum operators, the following holds.
messages.downloaded_by
lOMoARcPSD|61948123
8.3. Universality
• X = HRz (π)H
• Y = SHRz (π)HS †
• Z = Rz (π)
• S = Rz (π/2)
• T = Rz (π/4)
• Rx (θ) = HRz (θ)
• Ry (θ) = SHRz (θ)HS †
We see that with rotation matrices of arbitrary angles we only need the H gate and the
CNOT gate to achieve universality!
This means that we cannot actually achieve exact quantum universality with the
strategies we proposed. Unfortunately, while they are useful and can be utilized in practice
for a wide range of unitrary transformations that have “nice” angle values, the ideas we
laid down don’t guarantee realizable exact quantum universality.
Each time we have discussed quantum universality, we have been careful to state that it
was exact. Let’s see how we can achieve it, and which issues arise. First, consider the
following definition.
eiα 0 0
U := 0 1 0
0 0 1
eiα 0 0
iα
x1 x1 e
U x = 0 1 0 x2 = x2
0 0 1 x3 x3
messages.downloaded_by
lOMoARcPSD|61948123
8.3. Universality
U = V1 . . . Vk
We will not present the construction that allows such decomposition, but this theorem
has an important consequence. Indeed, if we have a unitary operator U acting on an n
qubit system, we have that d = 2n , therefore the bound on k becomes
This bound is definitely not practical, and it already shows how difficult it is to construct
arbitrary unitrary transformation exactly! However, we can go a step further.
Theorem 8.4
Any two-level unitary operator acting on the state space of n qubits can be constructed
through O(n2 ) single-qubit and CNOT gates.
This result together with the previous theorem, provide the following corollary which
states that single-qubit unitaries, together with CNOT gates, achieve exact quantum
universality. However, there is a catch.
This construction does not provide very efficient quantum circuits! However, it can be ac-
tually proven that this result is close to optimal if we demand exact quantum universality.
write
thm
section
In the end, to find reasonably fast quantum algorithms we will clearly need a totally 4.5.4?
different approach.
messages.downloaded_by
lOMoARcPSD|61948123
8.3. Universality
This measure of error has the interpretation that if E(U, V ) is small„ then anymeasure-
ment performed on the state V |ψ⟩ will give approximately the same measurement statis-
tics as a measurement of U |ψ⟩, for any initial state |ψ⟩. Amazingly, the following results
shows that with multiple unitaries the errors add at most linearly.
Consider the following set of quantum gates, called the standard set
{H, S, T, CNOT}
Our final goal for this chapter will be to show that this set can achieve approximate
quantum universality.
Lemma 8.2
Given any angle α, it holds that
ε
∀ε > 0 ∃k E(Rn̂ (α), Rn̂ (θ)k ) <
3
where →
−
n = (cos(π/8), sin(π/8), cos(π/8)) and θ is such that cos(θ/2) = cos2 (π/8).
messages.downloaded_by
lOMoARcPSD|61948123
8.3. Universality
In particular, this lemma implies that H and T gates can be used to approximate any
single-qubit unitary operation to arbitrary accuracy.
Theorem 8.5
Any single-qubit unitary operator U , there exists a unitary tranformation V composed
of only H and T gates such that
Since H and T gates allow us to approximate, any single qubit unitary operator, we can
leverage known constructions in order to approximate any m gate quantum circuit.
Corollary 8.4
Any m gate quantum circuit can be approximated to an accuracy ε with Θ(m2 /ε) gates
of the standard set.
Even if this is a quadratic increase of the original size, it is already good enough for
many applications. Rather remarkably, however, the following result is much more effi-
cient.
From this well-known result, it follows a polylogarithmic increase over the size of the
original circuit, instead of the previous quadratic.
Corollary 8.5
Any m gate quantum circuit can be approximated to an accuracy ε using O(m logc (m/ε))
gates of the standard set.
messages.downloaded_by
lOMoARcPSD|61948123
messages.downloaded_by
lOMoARcPSD|61948123
9.1. Background
9.1 Background
9.1.1 The No-cloning theorem
As stated in the introduction, before introducing any QKD protocol we need to discuss a
theorme that we only introduced in Section 1.3.2, namely the No-cloning theorem. In
particular, we stated that there is no quantum transformation that copies any quantum
state. Now that we have the mathematical tools to prove the theorem, we can actually
show its real formulation. But first, let’s try to understand what it means to “clone” a
qubit. Say that we have a qubit set to some unknown superposition of states |χ⟩ that we
would like to clone; in other words, we need an ancilla qubit |γ⟩ and some operator U
(which must be unitary) such that
Essentially, the ancilla qubit is used to store the clone of |χ⟩. We observe that the initial
state of the ancilla can be considered to be some fixed superposition, since the qubit |χ⟩ is
unknown and we want U to work on any possible state. However, the No-cloning theorem
states that such a transformation U cannot exist if the choice of the possible state for |χ⟩
isn’t restricted enough.
U :H⊗H→H⊗H
Proof. By way of contradiction, suppose that there exists a unitary transformation U for
which there exists a fixed |γ⟩ ∈ H that can be universally used as ancilla qubit to copy
any |χ⟩ ∈ S. Moreover, let |ψ⟩ , |ϕ⟩ ∈ S two distinct vectors such that ⟨ψ|ϕ⟩ ̸= 0 meaning
that they are non-orthogonal. Because U is unitary, by Theorem 2.3 we know that it
must preserve the scalar product, meaning that
messages.downloaded_by
lOMoARcPSD|61948123
9.1. Background
where the last implication comes from the fact that S was chosen to contain only normal-
ized vectors of H. This means that |ψ⟩ and |ϕ⟩ are actually the same vector, contradicting
the fact that we chose them distinct in S .
Corollary 9.1
There is no quantum transformation that copies an unknown quantum state.
This is just the particular case in which S, contains any possible normalized vector of H,
which obviously contains non-orthogonal pairs of distinct quantum states.
As we wil see in the subsequent sections, the hypothesis of the No-cloning theorem re-
garding the choice of S is used strategically by the BB84 protocol in order to ensure
quantum-safety. But before explaining the details of the protocol, we still need some
preliminary concepts.
messages.downloaded_by
lOMoARcPSD|61948123
9.1. Background
9.1.2 Measurements
Each time we discussed “measuring” we never actually mentioned that when we are physi-
cally performing a measurement what we are really doing is applying a “polarizing lens” to
the final state. For instance, this operation can be implemented through Faraday rotators,
which leverage the Faraday effect:
This is important because it means that when we talk about measurement we need to
define the “angle” at which we perform it. Mathematically speaking, this is equivalent
to defining the basis of choice for the measurement — we always consider orthonormal
bases only, so all the possible bases of a space are identical up to a rotation. Let’s see
how different bases behaave
• If we have a qubit in the state |ϕ⟩ = |+⟩, we know that the probability of getting
either |0⟩ or |1⟩ when measured in the Z basis is precisely 50% for both outcomes
because
1
Pr[measure(|ϕ⟩) = |0⟩] = |⟨+|0⟩|2 =
2
• Now, consider the orthonormal basis formed by the vector |+⟩ and |−⟩ — which is
usually called X basis; we observe that this space is just a rotation of 45° clockwise
of the Z basis. This space is interesting: when we measure a qubit |ϕ⟩ set to the
state |0⟩ in the Z basis we get |0⟩ with 100% certainty, however in the X basis we
have that
1
Pr[measure(|ϕ⟩) = |0⟩] = |⟨0|+⟩|2 =
2
Indeed, as we would expect |0⟩ and |1⟩ in the X basis behave exactly as |+⟩ and |−⟩
do in the Z one.
We will see how the BB84 protocol takes advantage of this fact later in our discussion.
The last detail that we want to mention about measurements in “unusual” bases is that
we can actually define unitary operators that allow us to perform measurements in the Z
basis no matter the basis of choice, by first applying some particular unitary operator that
messages.downloaded_by
lOMoARcPSD|61948123
creates a “map” between the two bases. For instance, say that we have some vector
|v⟩ = α |+⟩ + β |−⟩
defined in the X basis, and we want to measure this vector in the Z basis. This can be
done by first applying the following operator:
U = |0⟩ ⟨+| + |1⟩ ⟨−|
In fact, it holds that
U |v⟩ = (|0⟩ ⟨+| + |1⟩ ⟨−|)(α |+⟩ + β |−⟩)
= |0⟩ ⟨+| (α |+⟩ + β |−⟩) + |1⟩ ⟨−| (α |+⟩ + β |−⟩)
= α |0⟩ + β |1⟩
We can actually generalize this idea: if we have two bases {fi }ni=1 and {gi }ni=1 an operator
that maps each fi to gi for all i ∈ [n] is exactly
n
X
Uf g = |gi ⟩ ⟨fi |
i=1
We show that any change of basis matrix is unitary in Problem 9.2. Interestingly enough,
we already know an operator that acts as a map between the X and the Z bases:
U = |0⟩ ⟨+| + |1⟩ ⟨−|
† †
1 1 0 1
= · √ (|0⟩ + |1⟩) + · √ (|0⟩ − |1⟩)
0 2 1 2
1 1 1 0
=√ 1 1 +√ 1 −1
2 0 2 1
1 1 1 1 0 0
=√ +√
2 0 0 2 1 −1
1 1 1
=√
2 1 −1
=H
This should not come as a suprise, since we already knew that
H |0⟩ = |+⟩ H |1⟩ = |−⟩
messages.downloaded_by
lOMoARcPSD|61948123
ai bi Chosen state
0 0 |0⟩
1 0 |1⟩
0 1 |+⟩
1 1 |−⟩
For example, if her two random strings are
a = 01101
b = 00110
then she will construct the following superposition
Now, we will assume that Alice and Bob share two communication channels:
• one quantum channel, which can be eavesdropped by a third party Eve that wants
to know their shared key
• one public classical authenticated channel — in particular Alice and Bob must be
sure about the identity of the other
Now that Alice has constructed her superposition |ψ⟩, she will send it to Bob which will
receive E(|ψ⟩), where E describes the quantum operation due to the combined effect of
the channel’s noise and Eve’s actions — we will describe what Eve can do later in our
discussion.
Bob will then proceed to generate a random string of (4 + δ)n bits as well, which we will
call b′ , and based on this very string he will measure the received quantum superposition
— in particular, if b′i = 0 he will use the Z base, and if b′i = 1 he will use the X one. In
our example, assuming that Bob generated the random string
b′ = 10111
We observe that the first and the last states randomly collapsed to |−⟩ and |+⟩ respectively
because they were measured in the wrong basis — indeed, the original string was b = 00110
and b ⊕ b′ = 10001. Bob then tries to reconstruct the original string a based on its b′ ,
thus getting the string
a′ = 11100
When this process is complete, Bob publicly announces that he measured the superposi-
tion he received in the authenticated channel to Alice.
After Alice has heard that Bob has measured the state, she can proceed to send b itself as
it is over the authenticated public channel to Bob — we will see why she is sure that she
can perform this operation safely. Through b Bob can then discard all the bits of a′ that
messages.downloaded_by
lOMoARcPSD|61948123
were generated through wrong bits of b′ — we observe that their remaining bits satisfy
ai = a′i for all kept indices i. This step is usually called basis reconciliation, and the
expected number of bits kept by Bob after this step is
(4+δ)n (4+δ)n
X X 1 1 δ
E[kept bits] = 1 · Pr[bi = b′i ] = = · (4 + δ)n = 2 + n
i=1 i=1
2 2 2
At this point, Alice and Bob will agree on 2n bits to keep from the reconciled string (which
can be done again through the public medium) — δ can be chosen sufficiently large so
that there are at least 2n bits to choose with exponentially high probability.
At this point, the protocol is basically finished, and the last step involves error checking
and error correction which has to take into account both the possible noise of the
quantum medium, and the potential actions of Eve. Thus, as final step Alice and Bob
agree on a split of their 2n bits into 2 sets of n bits (choosen UAR), such that half of them
will be used as the shared key, and the other half are used as check bits. In particular,
Alice and Bob publicly share the check bits, such that
• if more than t bits disagree, they abort and re-try the protocol from the start
• if less that t bits disagree, the error rate is estimated and used to apply error
correction algorithms to the key bits — we will not cover the details of the error
correction procedures since they are not part of the key distribution protocol itself.
and half of the possible pairs are actually non-orthogonal. However, what she could
theoretically do is intercept |ψ⟩, measure it herself, and send the qubit back to Bob acting
as a man-in-the-middle — and Bob would have no way to know this actually happened.
Nevertheless, nor Bob neither Eve know the sequence of bases Alice chose originally, so
the best thing Eve can do is try randomly (exactly as Bob does in the protocol anyway).
Hence, fix a state |ψi ⟩ of the states that constitute |ψ⟩; the following can happen:
• Eve chooses the correct basis for |ψi ⟩: this means that she does not introduce any
disturbance to the state Bob will receive, and Bob still has 50% chance of recovering
Alice’s original qubit
• Eve chooses the wrong basis for |ψi ⟩: this means that she introduces some distur-
bance to the state Bob will receive, in the sense that now Bob has only 25% chance
of recovering Alice’s original qubit
messages.downloaded_by
lOMoARcPSD|61948123
For instance, suppose that Alice sends |+⟩; if Eve guesses the correct basis it holds
that
Pr[Bob measures |+⟩ | Eve chooses X] = Pr[Bob measures |+⟩ | Bob chooses X, Eve sends |+⟩]
· Pr[Bob chooses X]
· Pr[Eve sends |+⟩ | Eve chooses X]
1
=1· ·1
2
1
=
2
(obviously, all the probabilities are conditioned under the fact that Alice sent |+⟩). Dif-
ferently, if Eve guesses the wrong basis we have that
X
Pr[Bob measures |+⟩ | Eve chooses Z] = (Pr[Bob measures |+⟩ | Bob chooses X, Eve sends |b⟩]
b∈B
· Pr[Bob chooses X]
· Pr[Eve sends |b⟩ | Eve chooses Z])
1 1 1 1 1 1
= · · + · ·
2 2 2 2 2 2
1
=
4
Note that 25% is not the chances that Bob has to recover |+⟩ in general, because that is
given by
X
Pr[Bob measures |+⟩] = (Pr[Bob measures |+⟩ | Eve chooses B] · Pr[Eve chooses B])
B∈{X,Z}
1 1 1 1
= · + ·
2 2 4 2
3
=
8
which is still less than 12 .
We observe that, on average, with big enough bit strings the chance that Eve correctly
chooses each basis can be made exponentially low. Moreover, Eve’s actions are exactly
the reason why in the last step of the algorithm we perform a thresholded check on the
error rate: if the error rate is too high (some noise has to be expected) on average it
probably means that someone eavesdropped on the channel.
Is this everything Eve can do? The attack we presented has a very high chance of in-
troducing too much disturbance and being detected by the error rate check step, so for
Eve to have some chance of not being detected she needs to avoid introducing distur-
bance completely. How can she achieve this? The idea is based on the fact that she
actually does not need to apply the full No-cloning theorem: suppose that there exists
some unitary operator U that on input |ψ⟩ ⊗ |x⟩ — for some state |x⟩ — it behaves as
follows:
U (|ψ⟩ ⊗ |x⟩) = |ψ⟩ ⊗ |y⟩
messages.downloaded_by
lOMoARcPSD|61948123
In other words, U leaves |ψ⟩ unchanged and turns |x⟩ into |y⟩. For now, consider |ψ⟩ as 1
single qubit. If such an operator exists, Eve could use it in order to try to measure |y⟩ in
a later moment and gain some information about |ψ⟩, without ever measuring the latter
directly.
This idea seems compelling, however for Eve’s attack to be effective U must compute as
follows:
U (|ψ⟩ ⊗ |x⟩) = |ψ⟩ ⊗ |y⟩
U (|ϕ⟩ ⊗ |x⟩) = |ϕ⟩ ⊗ |y ′ ⟩
where |y⟩ and |y ′ ⟩ must be different. In this way
• U leaves |ψ⟩ unchanged, and the latter can be sent to Bob without anyone noticing
• U behaves differently depending on the input superposition, i.e. |y⟩ ̸= |y ′ ⟩, otherwise
she cannot distinguish between |ψ⟩ and |ϕ⟩ upon measurement — to be clear, this
has nothing to do with entanglement, in fact for Eve it is sufficient to look at the
second qubit and infer what the first must have been based on the fact that |y⟩ and
|y ′ ⟩ are distinguishable
Indeed, if such U exists she can recover what the original qubit Alice sent only looking
at |y⟩ and using the possible values of the ancilla qubit as “lookup table”. Let’s see if she
can employ this strategy.
Suppose that Alice sends some qubit which can be either |ψ⟩ or |ϕ⟩, where
Since U must be unitary, by Theorem 2.3 we know that U preserves the scalar product,
meaning that
⟨U (|ψ⟩ ⊗ |x⟩)|U (|ϕ⟩ ⊗ |x⟩)⟩ = ⟨ψ ⊗ x|ϕ ⊗ x⟩
⇐⇒ ⟨ψ ⊗ y|ϕ ⊗ y ′ ⟩ = ⟨ψ ⊗ x|ϕ ⊗ x⟩
⇐⇒ ⟨ψ|ϕ⟩ ⟨y|y ′ ⟩ = ⟨ψ|ϕ⟩ ⟨x|x⟩
⇐⇒ ⟨ψ|ϕ⟩ ⟨y|y ′ ⟩ = ⟨ψ|ϕ⟩
We observe that between all the possible choices of pairs of |ψ⟩ and |ϕ⟩, half of them are
such that ⟨ψ|ϕ⟩ ̸= 0, i.e. |ψ⟩ and |ϕ⟩ are non-orthogonal. This means that for appropriate
choices of |ψ⟩ and |ϕ⟩ we can simplify the last equality even more, obtaining that
Once again, through an argument fairly similar to the one we used for the No-cloning
theorem, this proves that such an operator U cannot exist that works for all the possible
values of |ψ⟩ and |ϕ⟩, which means that there is no way for Eve to gain any information
at all without introducing disturbance.
To be precise, there are more subtle attacks that do employ quantum entagnlement, such
as optimal intercept–resend tradeoffs, where Eve applies a unitary operator that
messages.downloaded_by
lOMoARcPSD|61948123
partially entangles the signal with a probe to trade a small amount of information for a
small disturbance. It can be proven that the BB84 protocol is also resistant against these
type of attacks, however this is beyond the scope of our discussion.
Lastly, we observe that BB84 requires Alice to wait before hearing back from Bob that he
actually measured |ψ⟩. This is to prevent that Alice sends b too early, so that Eve could
use the latter to decode |ψ⟩ into the original string a without any issue. Therefore, we
require Alice to wait for Bob’s measurement so that there is no way for Eve to recover
a after looking at b becasuse the original superposition is definitively destroyed — unless
she can go back in time!
Proof. Let q and r be two outcomes of the random variables Q and R, respectively. Since
q, r, ∈ {+1, −1}, either q = r or q = −r, therefore either q − r = 0 or q + r = 0. Define
p(q, r, s, t) := Pr[Q = q, R = r, S = s, T = t]
messages.downloaded_by
lOMoARcPSD|61948123
=2
This result is also known as the CHSH inequality, named after the initials of its four
discoverers. Nevertheless, it is generally referred to as the Bell inequality since it is part
of a larger set of inequalities known as Bell inequalities, named after the work of Bell
[Bel64] published in 1964.
By repeating the experiment multiple times, Alice and Bob can determine each term on
the LHS of the Bell inequality — for example, after a set of experiments they get a sample
of values for Q and S, and by multiplying the results they get multiple estimates of QS
which can subsequently be averaged out to get E[QS]. We must underline that in the
experiment we described there is no quantum mechanics involved : the only thing we did
was evaluating expected values and doing calculations with random variables by following
a seemingly logical reasoning.
Now, we are going to introduce quantum mechanics in the picture and see what happens
with our experiment. Suppose that Charlie prepares a quantum system of two entangled
qubits in the Bell state
1
|Ψ− ⟩ = √ (|01⟩ − |10⟩)
2
and gives the two qubits to Alice and Bob. To obtain the same exact numbers of the
experiment we outlined, we need to consider some properties that Alice and Bob can
measure which ultimately yield ±1 as possible outcomes. Fortunately, we do know such
observables and they are the Pauli matrices. In fact, by Postulate 3.4 we know that an
observable is a self-adjoint operator, and we already know that all Pauli matrices are
self-adjoint. Let’s first consider the Z Pauli matrix:
• it’s easy to prove that its eigenvalues are exactly +1 and −1
• it can also be easily calculated that |0⟩ is an eigenvector of Z associated to +1, and
|1⟩ is an eigenvector of Z associated to −1
This matrix seems to have everything we need for our purposes, so let’s set the random
variable Q equal to Z. Now, we need to find another observable (i.e. another self-adjoint
messages.downloaded_by
lOMoARcPSD|61948123
operator) to assign to Alice, which also has +1 and −1 as eigenvalues and that does not
commute with Q, meaning that
QR ̸= RQ
This is a crucial detail because we want to express the fact that the order of measurements
matters, otherwise the outcomes could be modeled by a single classical random variable.
This is easy enough by again turning our attention to the Pauli matrices, in particular we
just need to set R = X, in fact
• the eigenvalues of X are +1 and −1
• |+⟩ is an eigenvector of X associated to +1, and |−⟩ is an eigenvector of X associated
to −1
• it can be easily shown that
ZX = −XZ
The only thing left to define are S and T . We will set them as follows
−Z − X Z −X
S= √ T = √
2 2
and we will justify this choice later in our discussion. Most importantly, not only their
eigenvalues can be proven to be still ±1, but the following property allows us to rewrite
them nicely.
Proposition 9.2
It holds that
−Z − X Z −X
S= √ = −H T = √ = −iHY
2 2
messages.downloaded_by
lOMoARcPSD|61948123
Our next goal is to evaluate the same quantity calculated in the Bell inequality, and check
what value quantum mechanics predicts. The Bell inequality tells us that its LHS cannot
exceed 2, and our reasoning seemed to be pretty sound. Hence, it would be very strange
if quantum mechanics predicted otherwise. However, observe the following result.
Proposition 9.3
It holds that
√
E[Q ⊗ S | |Ψ− ⟩] + E[R ⊗ S | |Ψ− ⟩] + E[R ⊗ T | |Ψ− ⟩] − E[Q ⊗ T | |Ψ− ⟩] = 2 2
Proof. We will show this result by evaluating each expected value separately. We will use
the Proposition 2.20 extensively.
Claim 1: E[Q ⊗ S | |Ψ− ⟩] = √1 .
2
messages.downloaded_by
lOMoARcPSD|61948123
In the following claims we will skip some obvious steps for brevity.
Claim 2: E[R ⊗ S | |Ψ− ⟩] = √1 .
2
messages.downloaded_by
lOMoARcPSD|61948123
What? The Bell inequality told us that the LHS√could not ever exceed 2, however quantum
mechanics predicts that this sum is equal to 2 2! What is going on?
Short answer: we are not sure. Over the years, multiple experiments have been done
to check the prediction of quantum mechanics versus the Bell inequality, and the results
messages.downloaded_by
lOMoARcPSD|61948123
are resoundingly in favor of the quantum mechanical outcome. Most notably, in 2022
the Nobel Prize in Physics was awarded to Aspect, Clauser and Zeilinger for having
established experimentally the violation of Bell inequalities. In simpler terms, the Bell
inequality it not obeyed by Nature.
What does this mean? It means that at least one of the assumptions that went into
the derivation of the Bell inequality must be incorrect. However, we notice that in the
experiment we described we relied upon very few assumptions. Among all the various
hypotheses on which assumptions are wrong that have been made over the years, two
arguments mainly stand out.
1. Assumption of realism: this assumes that the physical properties PQ , PR , PS and
PT have definite values Q, R, S and T which exist independent of observation. In
fact, our intuition would suggest that every measurement outcome has a definite
value before it is measured: when we say that
Q, R, S, T ∈ {+1, −1}
we are also presupposing that the properties to be measured exist before we even
perform the measurements. Classically, through measurement we are only looking
at definite values that were “already there”.
2. Assumption of weak locality: this assumes that measurement performed by Alice
does not influence the result of Bob’s measurement. In other words, this assumes
that Alice’s choice of measurement cannot change Bob’s values, and vice versa. We
want to underline that with this assumption we are not talking about the outcomes,
only about the choice of which measurement apparatus one party selects.
Together, these two assumptions are known as the assumptions of local realism. Clearly
they seem to be plausible assumptions that match our everyday experience, yet the Bell
inequalities show that at least one of the two is incorrect. Most physicists believe that
the assumption to be dropped is realism, indeed current quantum mechanics believes
that there are no values of Q, R, S and T inside the particles and we can only talk
about possible measurement outcomes along with their probabilities, but such outcomes
do not exist before our measurement. Indeed, this is exactly what we have been assuming
from the start: we consider superpositions of states that collapse only after we have
performed our measurement.
To be precise, there is a third possible assumption to consider that we might deem false,
which is called measurement independence, through which we assume that there exists
the possibility of free choice between the measurements that Alice and Bob can perform.
However, if this presumption if false, it implies that free will does not exist and there
are some kind of “hidden variables” that know what settings Alice and Bob will choose
in advance. Nevertheless, to this day almost no physicist believes this assumption to be
false, so we will only focus on the first two.
As a final note, the choice of S and T was lead by the following bound proved by Tsirelson
[Tsi80] in 1980.
messages.downloaded_by
lOMoARcPSD|61948123
∀i, j ∈ {0, 1} Ai Bj = Bj Ai
it holds that √
⟨A0 B0 ⟩ + ⟨A0 B1 ⟩ + ⟨A1 B0 ⟩ − ⟨A1 B1 ⟩ ≤ 2 2
The choices for S and T are just the matrices that maximize this bound, given the choices
for Q and R.
To this day, it is not known if the world follows either one of them with certainty, but
this discrepancy between the classical and the quantum model must imply that the world
is not locally realistic. Modern quantum mechanics believes in weak locality but not in
realism, and interestingly enough such assumption can actually be leveraged in order to
design a more quantum-secure key distribution protocol!
Consider again the experiment performed by Alice and Bob, and let A be the quan-
tity
A := ⟨Q ⊗ S⟩ + ⟨R ⊗ S⟩ + ⟨R ⊗ T ⟩ − ⟨Q ⊗ T ⟩
Can an eavesdropper Eve disturb this experiment without any of the two parties involved
notice? Recall that the choice of measurements performed by Alice and Bob are executed
randomly, which means that Eve has no way to know in advance which setting Alice and
Bob will pick — not even Alice and Bob do! Therefore, if Eve wants to cheat successfully
she must find a way to arrange the context such that she knows all the possible outcomes
in advance regardless of the choices of the measurement apparatus performed by the two
parties. In other words, Eve must be able to set things up in such a way that she can
predict all possible outcomes ahead of time. However, because we are assuming that
Nature is weakly local, Eve cannot influence nor Alice’s neither Bob’s outcomes after
they chose which property to measure. This must imply that the only chance she has to
cheat is to have some way of “assigning” an outcome to every possible setting in advance.
This is exactly realism, and by the Bell inequality any system that is locally realistic
must yield a value of A ≤ 2.
This is the core idea of the E91 protocol, published by Ekert [Eke91] in 1991: suppose
that Alice and Bob take a random portion of their qubits and use it to compute the
quantity A. Then, if we set Q, R, S and T as we outlined previously we are guaranteed
that, without any external disturbance in the setting, the value of A will be
√
A≈2 2
This means that if Alice and Bob measure a value A ≤ 2, then their correlations could
have come from a locally realistic (and therefore predetermined ) model. And if their
correlations could come from such a model, then Eve could have predicted all outcomes
in advance, so their exchange would not be quantum-safe anymore and should be aborted.
Hence, by chekcing the value of A Alice and Bob can choose to proceed with the exchange
of the key or abort their attempt and try again.
messages.downloaded_by
lOMoARcPSD|61948123
Problem 9.1
Write the single qubit X gate as a sum of projectors.
First, we show that the eigenvalues of X are ±1, as outlined in this chapter.
Claim: sp(X) = {−1, +1}.
Then, we need to find the projectors P1 and P−1 . First, let λ = 1; we observe that
−1 1 v1
Xv = λv = v ⇐⇒ (X − I)v = 0 ⇐⇒ =0
1 −1 v2
and solving for v1 and v2 we obtain that
v2 − v1 = 0 v1 1
=⇒ v1 = v2 =⇒ v = = v1
v1 − v2 = 0 v1 1
so
the eigenspace associated to λ = 1 is the set of vectors that are scalar multiples of
1
, and in particular the normalized vector is obtained for
1
1 1 1 1 0 1
√ =√ + = √ (|0⟩ + |1⟩) = |+⟩
1+1 1 2 0 1 2
This means that we can use |+⟩ as basis for the P1 eigenspace. We will skip the details
of the calculations for λ = −1 since they are analogous, but we would end up with |−⟩
instead of |+⟩. In the end, this means that
X = 1 · P1 − 1 · P−1 = |+⟩ ⟨+| − |−⟩ ⟨−|
messages.downloaded_by
lOMoARcPSD|61948123
9.4. Exercises
9.4 Exercises
Problem 9.2
Prove that the trace independent of the chosen basis.
Solution. Let {fi }ni=1 and {gi }ni=1 be two orthonormal bases of the same Hilbert space,
and consider the following basis-change martix:
n
X
Uf g = |gi ⟩ ⟨fi |
i=1
Claim: Uf g is unitary.
since Uf g maps vectors of {fi }ni=1 into vectors of {gi }ni=1 . Then, let {fi }ni=1 = {ei }ni=1 , i.e.
let the first be the canonical basis, and consider the following change of basis matrix
n
X
Ueg = |gi ⟩ ⟨ei |
i=1
Let A by any matrix defined over the same Hilbert space. In the first chapters we saw
how we could write the trace of A as follows
n
X
tr(A) = ⟨ei |A|ei ⟩
i=1
messages.downloaded_by
lOMoARcPSD|61948123
9.4. Exercises
Howver, since
†
Ueg |ei ⟩ = |gi ⟩ ⟨ei | Ueg = ⟨gi |
we can also rewrite the trace as
†
tr(A) = tr(Ueg Ueg A)
†
= tr(Ueg AUeg )
Xn
†
= ⟨ei |Ueg AUeg |ei ⟩
i=1
Xn
= ⟨gi |A|gi ⟩
i=1
which means that we can define the trace of A both in terms of {ei }ni=1 and in terms
of {gi }ni=1 , proving that tr(A) is independent of the basis of choice — provided that the
chosen basis is orthonormal.
messages.downloaded_by
lOMoARcPSD|61948123
b = b0 = b1
Her idea is to make Bob able to recover the original b by looking at both b0 and b1 .
However, there is an issue with this idea: since both b0 and b1 could flip during the
transmission, its easy to see that if b0 ̸= b1 Bob has no way to determine what b was.
This suggests that what Alice needs to provide is more information!
Suppose that Alice now sends b0 , b1 and b2 such that
b = b0 = b1 = b2
and for now, let’s assume that b0 flipped during the transmission. Then, Bob will see
that
b0 ̸= b1 = b2
messages.downloaded_by
lOMoARcPSD|61948123
which ultimately helps him determine that the value Alice wanted to send is contained in
the bits b1 and b2 , and b0 flipped because of the noise. For a more practical example, if
Alice wants to send 0 to Bob she transmits 000 through the noisy medium, but whenever
Bob receive 100 he will infer that what Alice actually sent was 000, therefore the bit he
was meant to receive was 0.
This idea is called majority voting, as Bob decides how to recover the bit by looking at
the value of the bits that appears more often, however its easy too see a very big flaw of
this approach: with 2 or more bit flips the majority voting fails! If Bob receives 110, by
majority he will infer that we was meant to receive 1 from Alice, however he cannot be
sure that what really happened is that both b0 and b1 flipped through the transmission
and what Alice originally sent was 0. In general, we have that
messages.downloaded_by
lOMoARcPSD|61948123
at their value”, otherwise he would destroy all the information making the recovery
impossible
Fortunately, we can circumvent all of these problems with some clever ideas. First, con-
sider the following quantum circuit:
|ψ⟩ • •
|0⟩
|0⟩
This is exactly what we needed: we started with a state |ψ⟩ = α |0⟩ + β |1⟩ and we ended
up with
|ψ̂⟩ = α |000⟩ + β |111⟩
which yields the redundancy we need in order to utilize the repetition strategy.
Now, suppose that Alice sends each of the three qubits through the noisy quantum channel,
and each qubit will experience the effect of the noise, independently, with probability p.
But what is this effect in practice? So far, we did not mention the word flip, because we
actually need to define what a flip even is in this context. Well, if a “classical bit flip” is
an application of a NOT operator on some bit bi , it makes sense to define a “quantum bit
flip” as the application of the X operator of some qi sent, analogously.
However, this immediately shows that there is a continuous spectrum of possible errors
that can occur to the qubits — namely every possible linear transformation — and apart
from the X gate itself none of them have a classical analogue! For now, let’s just focus on
the X operator, and suppose that at most one bit flip occurred on the qubits Alice sent
to Bob. How can Bob recover the original message? Consider the following table:
messages.downloaded_by
lOMoARcPSD|61948123
This means that Bob is sure that the second bit flipped, hence the original message can
be recovered flawlessly by flipping the second qubit received. Again, this error-correction
procedure works perfectly, provided that bit flips occur on at most one qubit per message,
so reliability still requires that p < 1/2.
TODO add
slide 14
and 15
As previously mentioned, this scenario has no classical analogue, but it is still easy to
handle. In fact, we already know a key fact: the Z operator acts like a standard bit flip
in the Z basis, i.e.
Z |+⟩ = |−⟩ Z |−⟩ = |+⟩
This suggests that we can still employ the same redundancy strategy of the previous
section, provided that we perform a change of basis. Luckily, we already know a matrix
that performs the change from the X to the Z bases, as discussed in Section 9.1.2, namely
the Hadamard operator! Therefore, all Alice has to do is send the following:
messages.downloaded_by
lOMoARcPSD|61948123
|ψ⟩ • • H
|0⟩ H
|0⟩ H
Then, Bob can discover if a qubit phase flip occured through the following table:
Projector Error occured
P0 = |+ + +⟩ ⟨+ + +| + |− − −⟩ ⟨− − −| No error occurred
P1 = |− + +⟩ ⟨− + +| + |+ − −⟩ ⟨+ − −| First phase flipped
P2 = |+ − +⟩ ⟨+ − +| + |− + −⟩ ⟨− + −| Second phase flipped
P3 = |+ + −⟩ ⟨+ + −| + |− − +⟩ ⟨− − +| Third phase flipped
Once Bob learns which qubit phase flipped (if any) he can apply a Z operator to the
corresponding qubit. We say that the channel that applies the X matrix and the one
that applies the Z martix are unitarily equivalent, since there is a unitary operator —
the Hadamard gate, in this case — such that the action of one channel is the same as
the other, provided that the first channel is preceded by U and followed by U † in every
operation performed — we will leave the proof of this fact as an exercise.
TODO slide 19
messages.downloaded_by
lOMoARcPSD|61948123
Theorem 10.1
Any quantum error-correcting code that corrects at most k Pauli errors on at most k
qubits will also correct an arbitrary quantum operation on thos qubits.
messages.downloaded_by
lOMoARcPSD|61948123
It’s easy to see that a “good” code is required to have R as close to 1 as possible, in order to
reduce the number of redundancy symbols. However, any repetition-based error-correcting
code has a rate significantly smaller than 1, in fact as the number of repetitions required
to correct more errors increases, the rate approaches 0! In this section we present a more
rubust type of error-correcting codes, called linear codes.
Enc : Zk×1
2 → Zn×1
2 : x 7→ Gx
messages.downloaded_by
lOMoARcPSD|61948123
Proposition 10.1
A great advantage of linear codes over more general error-correcting codes is their compact
specification: a general code encoding k information bits into n bits requires 2k codewords,
each of length n, for a total of n2k bits needed to provide a description of the entire code.
With a linear code instead, we only need to specify the nk bits of the generator matrix,
and that’s it. This is an exponential saving in the amount of memory required!
Now that we know what linear codes are, we can proceed to describe how to perform
error-correction with them. In fact, in the repetition codes we just had to use a majority
rule and that was enough to retrieve the origianl message, however in this case the error-
correction procedure is not as intuitive. But first, we need to provide a different definition
of linear codes.
C = ker H
(n−k)×n
where H ∈ Z2 is the parity check matrix of C.
messages.downloaded_by
lOMoARcPSD|61948123
Proof of the Claim. First, we show that C ⊆ ker H. Fix any c ∈ C, and consider
the input x ∈ Zk2 such that c = Gx. We observe that
Hc = H(Gx) = (HG)x
and by construction each row yiT is orthogonal to all columns of G, which implies that
Now note that H has n − k linearly independent rows by construction, which implies that
rk(H) = n − k. Therefore, by the rank-nullity theorem
dim(ker H) = n − rk(H) = n − (n − k) = k
Then, since C ⊆ ker H, and C has dimension k, this must imply that C = ker H.
Now we need to do the opposite in order to prove that the two definitions are actually
equivalent. Let H be the parity check matrix of H; pick k linearly independent vectors
y1 , . . . , yk spanning the kernel of H. Then, construct the generator matrix G of C as
follows:
G := y1 . . . yk
Proof of the Claim. Fix any c ∈ {Gx | x ∈ Zk2 } generated by some x ∈ Zk2 . Then,
it holds that c = Gx meaning that
c = x1 y1 + . . . + xk yk
Hc = x1 Hy1 + . . . xk Hyk = 0
messages.downloaded_by
lOMoARcPSD|61948123
span{y1 , . . . , yk } = ker H = C
by construction of G. Therefore, for any fixed c ∈ C = ker H it must hold that c can be
written as a linear combination of y1 , . . . , yk , i.e.
∃x1 , . . . , xk ∈ Z2 c = x1 y1 + . . . + xk yk
which concludes that c = Gx where x is the vector composed of the coefficients of the
linear combination.
This shows that the two definitions are equivalent.
As an example of parity check matrix, consider the [3, 1] repetition code described by the
generator matrix we saw earlier
1
G = 1
1
To construct H, we pick 3 − 1 = 2 linearly independent vectors orthogonal to the columns
of G, say
1 0
y1 = 1 y2 = 1
0 1
and define the parity check matrix as
1 1 0
H :=
0 1 1
Ok, how do we use this matrix now? Suppose that we have a linear code C generated by
a matrix G, and we encode a message x as y = Gx, but an error e due to noise corrupts
y giving the corrupted codeword
y′ = y + e
Because the parity check matrix H is such that C = ker H, it holds that
Hy = 0 =⇒ Hy ′ = H(y + e) = Hy + He = He
We call Hy ′ = He the error syndrome of y ′ , and it is the key component that enables
error-correction in linear codes.
To see how to perform error-correction, suppose that at most 1 error occurred. Then, the
error syndrome Hy ′ is equal to 0 in the no error case, and it is equal to Hej when an error
occurs on the j-th bit (where ej is the j-th vector of the canonical basis). Then, under the
assumption that errors occur on at most one bit, it is possible to perform error-correction
by computing the error syndrome Hy ′ and comparing it to the different possible values
of Hej , to dermine which (if any) bit need to be corrected. This looks like an interesting
strategy, but we would like to be even more general.
messages.downloaded_by
lOMoARcPSD|61948123
In simpler terms, the Hamming distance between two bit strings is the number of places
at which they differ, for instance
d 1 1 0 0 , 0 1 0 1 =2
w(x) := d(x, 0)
The weight of a word is the number of places at which x is non-zero. It is easy to show
that the following proposition holds.
Proposition 10.2
Given two words x and y each of n bits, it holds that
d(x, y) = w(x + y)
These two definitions are crucial because global properties of a linear code can be under-
stood using the Hamming distance.
Note that for any codewords x, y ∈ C it holds that x + y ∈ C by linearity of the code C,
therefore by the previous proposition we obtain that
which means that the minimum distance is actually also equal to the minimum weight.
messages.downloaded_by
lOMoARcPSD|61948123
Theorem 10.3
A linear code C of type [n, k, d] can correct t = errors, and can detect d − 1
d−1
2
errors.
TODO
how
does
this
work
10.2.1 The Hamming code
Let r ≥ 2 be an integer, and consider the matrix H whose columns are all the 2r − 1
bit strings of length r different from the 0 bit string. This is a parity check matrix of
dimensions (2r − 1) × (2r − r − 1) and it defines a linear code known as the Hamming
code, named after Turing Prize winner Richard Hamming. A very famous special example
of the Hamming code is obtained with r = 3, which defines the following parity check
matrix
0 0 0 1 1 1 1
H = 0 1 1 0 0 1 1
1 0 1 0 1 0 1
which describes a linear code of type [7, 4, 3]. By Theorem 10.3, we know that this code
is able to correct
3−1
t= =1
2
Let’s give an example of error-correction through the r = 3 case of the Hamming code in
action: suppose that the received codeword is
1
0
1
y ′ = 1
1
1
0
messages.downloaded_by
lOMoARcPSD|61948123
Then, since this is not the 0 vector some error must have occurred, and because we know
that Hy ′ = Hej where ej has 1 only in the j-th position we have that
0
0
1 0
Hej = 0 =⇒ ej = 0 =⇒ j = 5
1 1
0
0
which means that the error occured in the 5-th position of y ′ . This means that the original
y was
1
0
1
y = 1
0
1
0
Now, to retrieve the original message x we need to construct a matrix that we did not
discuss yet. First, we need the generator matrix G, and we can costruct it by following the
construction in Theorem 10.3. For this example we will employ the most common gener-
ator matrix usually defined for the Hamming code [7, 4, 3], which is the following
0 0 1 1
0 1 0 1
0 1 1 1
G := 1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1
This matrix is not invertible because it is not a square matrix, however we can simply
choose k linearly indepentend rows from G and construct the following matrix
0 0 1 1
0 1 0 1
Ĝ :=
0 1 1 1
1 0 0 1
messages.downloaded_by
lOMoARcPSD|61948123
Proving that Ĝ−1 Ĝ = I mod 2 is left as exercise. Finally, to obtain the message x that
generated y we must first truncate y to the first 4 bits — because of how we constructed
Ĝ — thus obtaining
1
0
ŷ =
1
1
which ultimately allows us to retrieve the original message
1 1 1 1 1 1
1 0 1 0 0 0
Ĝ−1 ŷ = = = x
0 1 1 0 1 1
1 1 1 0 1 0
We will not go into the details of this very dense definition, however what we really
matter is a special case of if, usually referred to as Steane code — named after its
inventor Andrew Steane. It is derived by using the [7, 4, 3] Hamming code we saw earlier,
and it is capable of correcting errors on t qubits. We can construct it as follows: let H be
this exact Hamming space, and set
messages.downloaded_by
lOMoARcPSD|61948123
• C1 = H
• C2 = H ⊥
Then, since H ⊥ ⊂ H, and H ⊥ = 2dim(H ) = 23 = 8 we have that
⊥
1 X
x = |0000000⟩ =⇒ |0L ⟩ := |x + H ⊥ ⟩ = √ |y⟩
8 y∈H ⊥
1 X
x = |1111111⟩ =⇒ |1L ⟩ := |x + H ⊥ ⟩ = √ |1111111 + y⟩
8 y∈H ⊥
where |0L ⟩ and |1L ⟩ indicate the “logical” 0 and 1, respectively. Then, if we need to tranfer
a qubit
|ψ⟩ = α |0⟩ + β |1⟩
we just need to encode it as
α X β X
|ψL ⟩ = α |0L ⟩ + β |1L ⟩ = √ |y⟩ + √ |1111111 + y⟩
8 y∈H ⊥ 8 y∈H ⊥
b4 ⊕ b 5 ⊕ b 6 ⊕ b 7
Hb = b2 ⊕ b3 ⊕ b6 ⊕ b7
b1 ⊕ b 3 ⊕ b 5 ⊕ b 7
In particular, this formulation is useful because it can be translated into the following
quantum circuit: TODO After computing the syndrome, we can proceed as before with slide 13
messages.downloaded_by
lOMoARcPSD|61948123
Bibliography
[BB14] Charles H. Bennett and Gilles Brassard. “Quantum cryptography: Public key
distribution and coin tossing”. In: Theoretical Computer Science 560 (Dec.
2014), 7–11. issn: 0304-3975. doi: 10 . 1016 / j . tcs . 2014 . 05 . 025. url:
[Link]
[Bel64] J. S. Bell. “On the Einstein Podolsky Rosen paradox”. In: 1.3 (Nov. 1964),
195–200. issn: 0554-128X. doi: 10.1103/physicsphysiquefizika.1.195.
url: [Link]
[CAB+20] M. Cerezo, Andrew Arrasmith, Ryan Babbush, et al. “Variational Quantum
Algorithms”. In: (2020). doi: 10.48550/ARXIV.2012.09265. url: https:
//[Link]/abs/2012.09265.
[Deu85] David Deutsch. “Quantum theory, the Church–Turing principle and the uni-
versal quantum computer”. In: Proceedings of the Royal Society of London.
A. Mathematical and Physical Sciences 400.1818 (1985), pp. 97–117.
[Deu92] Josza Deutsch. In: Proceedings of the Royal Society of London. Series A:
Mathematical and Physical Sciences 439.1907 (Dec. 1992), 553–558. issn:
2053-9177. doi: 10.1098/rspa.1992.0167. url: [Link]
1098/rspa.1992.0167.
[Eke91] Artur K Ekert. “Quantum cryptography based on Bell’s theorem”. In: Phys-
ical review letters 67.6 (1991), p. 661.
[EPR35] A. Einstein, B. Podolsky, and N. Rosen. “Can Quantum-Mechanical Descrip-
tion of Physical Reality Be Considered Complete?” In: Physical Review 47.10
(May 1935), 777–780. issn: 0031-899X. doi: 10.1103/physrev.47.777. url:
[Link]
[Gro05] Lov K. Grover. “Fixed-Point Quantum Search”. In: Physical Review Letters
95.15 (Oct. 2005). issn: 1079-7114. doi: 10.1103/physrevlett.95.150501.
url: [Link]
[Gro97] Lov K. Grover. “Quantum Mechanics Helps in Searching for a Needle in a
Haystack”. In: Physical Review Letters 79.2 (July 1997), 325–328. issn: 1079-
7114. doi: 10.1103/physrevlett.79.325. url: [Link]
1103/physrevlett.79.325.
[Hal13] Brian C. Hall. Quantum Theory for Mathematicians. Springer New York,
2013. isbn: 9781461471165. doi: 10 . 1007 / 978 - 1 - 4614 - 7116 - 5. url:
[Link]
[Kit95] A. Yu. Kitaev. Quantum measurements and the Abelian Stabilizer Problem.
1995. doi: 10.48550/[Link]- PH/9511026. url: [Link]
org/abs/quant-ph/9511026.
Bibliography 190
messages.downloaded_by
lOMoARcPSD|61948123
Bibliography
[PMS+14] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, et al. “A variational eigen-
value solver on a photonic quantum processor”. In: Nature Communications
5.1 (July 2014). issn: 2041-1723. doi: 10.1038/ncomms5213. url: http:
//[Link]/10.1038/ncomms5213.
[Sho] P.W. Shor. “Algorithms for quantum computation: discrete logarithms and
factoring”. In: Proceedings 35th Annual Symposium on Foundations of Com-
puter Science. SFCS-94. IEEE Comput. Soc. Press, 124–134. doi: 10.1109/
sfcs . 1994 . 365700. url: http : / / dx . doi . org / 10 . 1109 / SFCS . 1994 .
365700.
[Tsi80] B. S. Tsirelson. “Quantum generalizations of Bell’s inequality”. In: Letters
in Mathematical Physics 4.2 (Mar. 1980), 93–100. issn: 1573-0530. doi: 10.
1007/bf00417500. url: [Link]
[WZ82] W. K. Wootters and W. H. Zurek. “A single quantum cannot be cloned”.
In: Nature 299.5886 (Oct. 1982), 802–803. issn: 1476-4687. doi: 10.1038/
299802a0. url: [Link]
[YLC14] Theodore J. Yoder, Guang Hao Low, and Isaac L. Chuang. “Fixed-Point
Quantum Search with an Optimal Number of Queries”. In: Physical Review
Letters 113.21 (Nov. 2014). issn: 1079-7114. doi: 10.1103/physrevlett.
113 . 210501. url: http : / / dx . doi . org / 10 . 1103 / PhysRevLett . 113 .
210501.
Bibliography 191
messages.downloaded_by