PIQC Lecture 6

A Practical Introduction to Quantum
Computing: From Qubits to Quantum

Machine Learning and Beyond
Elı́as F. Combarro
[email protected]
CERN openlab (Geneva, Switzerland) - University of Oviedo (Oviedo, Spain)
CERN - November/December 2020

Part I
Introduction: quantum computing...

the end of the world as we know it?
2 / 211
I, for one, welcome our new quantum overlords
Image credits: sciencenews.org

3 / 211
Philosophy of the course
Image credits: Modified from an Instagram image by Bob MacGuffie
4 / 211
Tools and resources
• Jupyter Notebooks
• Web application to create and execute notebooks that
include code, images, text and formulas
• They can be used locally (Anaconda) or in the cloud
(mybinder.org, Google Colab...)
• IBM Quantum Experience
• Free online access to quantum simulators (up to 32 qubits)
and actual quantum computers (1, 5 and 15 qubits) with
different topologies
• Programmable with a visual interface and via different
languages (python, qasm, Jupyter Notebooks)
• Launched in May 2016
• https://quantum-computing.ibm.com/
Image credits: IBM 5 / 211

Tools and resources (2)
• Quirk
• Online simulator (up to 16 qubits)
• Lots of different gates and visualization options
• http://algassert.com/quirk
• D-Wave Leap
• Access to D-Wave quantum computers
• Ocean: python library for quantum annealing
• Problem specific (QUBO, Ising model...)
• https://www.dwavesys.com/take-leap
6 / 211
The shape of things to come
Image credits: Created with wordclouds.com
7 / 211
What is quantum computing?
Quantum computing
Quantum computing is a computing paradigm that exploits
quantum mechanical properties (superposition, entanglement,
interference...) of matter in order to do calculations
Image credits: Erik Lucero
8 / 211
Models of quantum computing
• There are several models of quantum computing (they’re
all equivalent)
• Quantum Turing machines
• Quantum circuits
• Measurement based quantum computing (MBQC)
• Adiabatic quantum computing
• Topological quantum computing
• Regarding their computational capabilities, they are
equivalent to classical models (Turing machines)
Image credits: Getty Images

9 / 211
Quantum and classical computational complexity
Image credits: wikipedia.org
10 / 211
What technologies are used to build quantum
computers?
Image credits: Graphic by C. Bickle/Science data by Gabriel Popkin
11 / 211
What is a quantum computer like?
Image credits: IBM
The Sounds of IBM: IBM Q

12 / 211
Programming a quantum computer
• Different frameworks and programming languages:
• qasm
• Qiskit (IBM)
• Cirq (Google)
• Forest/pyqil (Rigetti)
• Q# (Microsoft)
• Ocean (D-Wave)
• ...
• Most of them for quantum circuit specification
Image credits: IBM
13 / 211
What are the elements of a quantum circuit?
• Every computation has three elements: data, operations

and results
• In quantum circuits:
• Data = qubits
• Operations = quantum gates (unitary transformations)
• Results = measurements
Image credits: Adobe Stock
14 / 211
Part II
One-qubit systems: one qubit to

rule them all
15 / 211
What is a qubit?
• A classical bit can take two different values (0 or 1). It is
discrete.
• A qubit can “take” infinitely many different values. It is
continuous.
• Qubits live in a Hilbert vector space with a basis of two
elements that we denote |0i y |1i.
• A generic qubit is in a superposition
|ψi = α |0i + β |1i
where α and β are complex numbers such that
|α|2 + |β|2 = 1
Image credits: https://prateekvjoshi.com/ 16 / 211

Measuring a qubit
• The way to know the value of a qubit is to perform a
measurement. However
• The result of the measurement is random
• When we measure, we only obtain one (classical) bit of
information
• If we measure the state |ψi = α |0i + β |1i we get 0 with
probability |α|2 and 1 with probability |β|2 .
• Moreover, the new state after the measurement will be |0i
or |1i depending of the result we have obtained
(wavefunction colapse)
• We cannot perform several independent measurements of
|ψi because we cannot copy the state (no-cloning
theorem)
17 / 211
What are quantum gates?
• Quantum mechanics tells us that the evolution of an

isolated state is given by the Schrödinger equation
• In the case of quantum circuits, this implies that the

operations that can be carried out are given by unitary
matrices. That is, matrices U of complex numbers verifying
UU † = U † U = I
where U † is the conjugate transpose of U.

• Each such matrix is a possible quantum gate in a quantum
circuit
18 / 211
Reversible computation
• As a consequence, all the operations have an inverse:
reversible computing
• Every gate has the same number of inputs and outputs
• We cannot directly implement some classical gates such
as or , and, nand, xor ...
• But we can simulate any classical computation with small
overhead
• Theoretically, we could compute without wasting energy
(Landauer’s principle, 1961)
Image credits: wikipedia.org 19 / 211

One-qubit gates
• When we have just one qubit |ψi = α |0i + β |1i, we usually

α
represent it as a column vector
β
• Then, a one-qubit gate can be identified with a matrix

a b
U= that satisfies
c d

a b a c 1 0
=
c d b d 0 1
where a, b, c, d are the conjugates of complex numbers

a, b, c, d.
20 / 211
Action of a one-qubit gate
• A state |ψi = α |0i + β |1i is transformed into

a b α aα + bβ
=
c d β cα + dβ
that is, into the state |ψi = (aα + bβ) |0i + (cα + dβ) |1i
• Since U is unitary, it holds that
|(aα + bβ)|2 + |(cα + dβ)|2 = 1
21 / 211
The X or NOT gate
• The X gate is defined by the (unitary) matrix

0 1
1 0
• Its action (in quantum circuit notation) is
|0i X |1i
|1i X |0i
that is, it acts like the classical NOT gate
• On a general qubit its action is
α |0i + β |1i X β |0i + α |1i
22 / 211
The Z gate
• The Z gate is defined by the (unitary) matrix

1 0
0 −1
• Its action is
|0i Z |0i
|1i Z − |1i
23 / 211
The H or Hadamard gate
• The H or Hadamard gate is defined by the (unitary) matrix

1 1 1
√
2 1 −1
• Its action is
|0i+|1i
|0i H √
2
|0i−|1i
|1i H √
2
• We usually denote
|0i + |1i
|+i := √
2
and
|0i − |1i
|−i := √
2
24 / 211
Other important gates
• Y gate

0 −i
i 0
• S gate

1 0
π
0 ei 2
• T gate

1 0
π
0 ei 4
• The gates X , Y and Z are also called, together with the
identity, the Pauli gates. An alternative notation is σX , σY ,
σZ .
25 / 211
The Bloch sphere
• A common way of representing the state of a qubit is by

means of a point in the surface of the Bloch sphere
• If |ψi = α |0i + β |1i with |α|2 + |β|2 = 1 we can find angles
γ, δ, θ such that
θ
α = eiγ cos
2
θ
β = eiδ sin
2
• Since an overall phase is physically irrelevant, we can
rewrite
θ θ
|ψi = cos |0i + eiϕ sin |1i
2 2
with 0 ≤ θ ≤ π and 0 ≤ ϕ < 2π.
26 / 211
The Bloch sphere (2)
• From |ψi = cos 2θ |0i + eiϕ sin 2θ |1i we can obtain spherical
coordinates for a point in R3
(sin θ cos ϕ, sin θ sin ϕ, cos θ)

27 / 211
Rotation gates
• We can define the following rotation gates
cos 2θ −i sin 2θ

−i θ2 X θ θ
RX (θ) = e = cos I − i sin X =
2 2 −i sin 2θ cos 2θ
cos 2θ − sin 2θ

θ θ θ
RY (θ) = e−i 2 Y = cos I − i sin Y =
2 2 sin 2θ cos 2θ
θ
!
e−i 2

−i θ2 Z θ θ 0 1 0
RZ (θ) = e = cos I−i sin Z = ≡
2 2 0
θ
ei 2 0 eiθ
• Notice that RX (π) ≡ X , RY (π) ≡ Y , RZ (π) ≡ Z ,

RZ ( π2 ) ≡ S, RZ ( π4 ) ≡ T
28 / 211
Using rotation gates to generate one-qubit gates
• For any one-qubit gate U there exist a unit vector

r = (rx , ry , rz ) and an angle θ such that
θ θ θ
U ≡ e−i 2 r ·σ = cos I − i sin (rx X + ry Y + rz Z )
2 2
• For instance, choosing θ = π and r = ( √1 , 0, √1 ) we can
2 2
see that
θ 1
H ≡ e−i 2 r ·σ = −i √ (X + Z )
2
• Additionally, it can also be proved that there exist angles α,
β and γ such that
U ≡ RZ (α)RY (β)RZ (γ)
29 / 211
Inner product, Dirac’s notation and Bloch sphere
• The inner product of two states |ψ1 i = α1 |0i + β1 |1i and

|ψ2 i = α2 |0i + β2 |1i is given by

α2
hψ1 |ψ2 i = α1 β1 = α1 α2 + β 1 β 2
β2
• Notice that h0|0i = h1|1i = 1 and h0|1i = h1|0i = 0

• This allows us to compute

hψ1 |ψ2 i = α1 h0| + β1 h1| (α2 |0i + β2 |1i)
= α1 α2 h0|0i + α1 β2 h0|1i + β1 α2 h1|0i + β1 β2 h1|1i
= α1 α2 + β1 β2
• Orthogonal states are antipodal on the Bloch sphere
30 / 211
Hello, quantum world!
• Our very first quantum circuit!
|0i H
• After applying the H gate the qubit state is
|0i + |1i
√
2
• When we measure, we obtain 0 or 1, each with 50%
probability: we have a circuit that generates perfectly
uniform random bits!
31 / 211
Part III
The BB84 protocol: Alice and Bob’s

hotline
32 / 211
One-time pad: a Catch-22 situation
• Alice wants to send Bob a message m without Eve being
able to learn anything about its content
• This can be achieved if Alice and Bob share in advance a
string k of random bits:
• Alice computes x = m ⊕ k and sends x to Bob
• Eve cannot learn anything from x
(Pr (M = m|X = x) = Pr (M = m))
• But Bob can recover m by computing x ⊕ k
• The main problem is that k has to be as long as m and
cannot be reused so... how to agree on k?
Image credits: nullprogram.com
33 / 211
The problem of key distribution
• Alice and Bob may share several keys for later use when
they are together
• But... what if they cannot meet each other?
• There exist key distribution methods like the Diffie-Hellman
protocol but...
• They are not unconditionally secure (they usually rely on
hardness assumptions)
• In fact, DH can be broken with quantum computers!
34 / 211
BB84: Alice’s part
• In 1984, Charles Bennett and Gilles Brassard proposed

the first protocol for quantum key distribution (QKD)
• Alice generates a (private) string of random bits
• She could even do this with a quantum computer (H gate +
measure)
• Then, for each bit she randomly chooses if she encodes it
in the {|0i , |1i} basis or in the {|+i , |−i} basis (remember
that |+i = √1 (|0i + |1i) and |−i = √1 (|0i − |1i))
2 2
• She can easily do this by using H and X gates (recall that
H |0i = |+i , H |1i = |−i , X |0i = |1i , X |1i = |0i)
• Alice sends the resulting qubits to Bob (through a quantum
but not necessarily secure channel)
35 / 211
BB84: Bob’s part
• Each time Bob receives a qubit, he randomly decides

whether he will measure it in the {|0i , |1i} basis or in the
{|+i , |−i} basis
• He does this by applying (or not) the H gate before
measuring
• He writes down the results and the basis he used:
• If he used {|0i , |1i} he writes down 0 if he gets |0i and 1 if
he gets |1i
• If he used {|+i , |−i} he writes down 0 if he gets |+i and 1
if he gets |−i
36 / 211
BB84: Alice and Bob on the phone
• After this process, Alice and Bob talk on a classical

channel (authenticated but not necessarily secure)
• Bob announces the bases he has used for the
measurements and Alice announces the bases she used
to code the bits
• Bob does NOT announce the results of his measurements
• For those bits in which Bob measured with the same basis
that Alice used for coding, he has got the bit that Alice
intended to send
• The rest are discarded (they will keep about half of the bits)
37 / 211
BB84: The protocol in an image
Image credits: A. Carrasco-Casado, V. Fernández, N. Denisenko
38 / 211
Eve tries to intercept and resend...
• Imagine Eve has access to the qubits that Alice sends to

Bob
• Eve could try to measure and resend the qubit to Bob
• It is imposible for Eve to distinguish the four possibilities
{|0i , |1i , |+i , |−i} because she does not know the basis
that Alice has chosen
• If Eve chooses a basis at random, she will make an error
half of the time and Alice and Bob may detect it (by sharing
some of the bits of the key to check that they are equal)
• Eve cannot copy the qubits and wait to check the basis that
Alice and Bob have used (no cloning theorem)
• Other more complex attacks are possible, but can be
shown to fail
39 / 211
Information reconciliation and privacy amplification
• Because of imperfections in the channel and devices or
because of eavesdropping, some of the bits that Alice and
Bob have may be different
• They can conduct a process of information reconciliation
(for instance, with the cascade protocol)
• After this phase (or even before), some information may
have leaked to Eve
• Alice and Bob can perform privacy amplification (for
instance, with randomness extractors)
Image credits: hikingandcoding.wordpress.com

40 / 211
QKD at CERN
Image credits: https://arxiv.org/pdf/1203.4940.pdf
41 / 211
Kak’s three-stage protocol
• Proposed by Kak in 2006
• It needs an authenticated quantum channel
• Suppose Alice wants to send |xi ∈ {|0i , |1i} to Bob:
• Alice chooses θA at random and sends RY (θA ) |xi to Bob
• Bob choose θB at random and sends RY (θB )RY (θA ) |xi
back to Alice
• Alice applies RY (−θA ) and sends
RY (−θA )RY (θB )RY (θA ) |xi = RY (θB ) |xi
to Bob
• Bob can now recover |xi by applying RY (−θB )
42 / 211
The quantum one-time pad
• The analagous of the one-time pad with quantum

operations would be to choose a ∈ {0, 1} at random and
encode |xi ∈ {|0i , |1i} as
X a |xi = |x ⊕ ai
• This cannot be extended to general qubits |ψi because

X |+i = |+i and X |−i ≡ |−i
• We need to choose two bits a and b at random and encode
|ψi as
Z b X a |ψi
• Bob can now recover |ψi by applying X a Z b
• It can be proved that this is unconditionally secure
• The QOTP is the basis of some blind quantum computing
protocols
43 / 211
Other protocols that use independent qubits
• The use of independent qubits does not fully exploit the
possibilities of quantum information, but there are some
additional interesting applications
• For instance:
• Other QKD protocols: B92, SARG04, Six-state protocol...
• The concept of quantum money (Wiesner)
• The Elitzur-Vaidman bomb tester
• Quantum position verification
• One-qubit classifier
Image credits: The American Association for the Advancement of Science

44 / 211
Part IV
Two-qubit systems: more than the

sum of their parts
45 / 211
Working with two qubits
• Each of the qubits can be in state |0i or in state |1i
• So for two qubits we have four possibilities:
|0i ⊗ |0i , |0i ⊗ |1i , |1i ⊗ |0i , |1i ⊗ |1i
that we also denote
|0i |0i , |0i |1i , |1i |0i , |1i |1i
or
|00i , |01i , |10i , |11i
• Of course, we can have superpositions so a generic state
is
|ψi = α00 |00i + α01 |01i + α10 |10i + α11 |11i
where αxy are complex numbers such that
1
X
|αxy |2 = 1
x,y=0
46 / 211
Measuring a two-qubit system
• Suppose we have a state
|ψi = α00 |00i + α01 |01i + α10 |10i + α11 |11i

• If we measure both qubits, we will obtain:
• 00 with probability |α00 |2 and the new state will be |00i
• It is an analogous situation to what we had with one qubit,
but now with four possibilities
47 / 211
Measuring just one qubit in a two-qubit system
• If we have a state
|ψi = α00 |00i + α01 |01i + α10 |10i + α11 |11i
we can also measure just one qubit

• If we measure the first qubit (for the second one is
analogous):
• We will get 0 with probability |α00 |2 + |α01 |2
• In that case, the new state of |ψi will be
α00 |00i + α01 |01i

p
|α00 |2 + |α01 |2
• We will get 1 with probability |α10 |2 + |α11 |2

• In that case, the new state of |ψi will be
α10 |10i + α11 |11i

p
|α10 |2 + |α11 |2
48 / 211
Two-qubit states and vector representation
• A general two-qubit quantum state is
|ψi = α00 |00i + α01 |01i + α10 |10i + α11 |11i
• We can represent with the column vector

 
α00
α01 
 
α10 
α11
• We can compute inner products by noticing that
h00|00i = h01|01i = h10|10i = h11|11i = 1
h00|01i = h00|10i = h00|11i = · · · = h11|00i = 0

• A two-qubit quantum gate is a unitary matrix U of size 4 × 4
49 / 211
Tensor product of one-qubit gates
• The simplest way of obtaining a two-qubit gate is by having
a pair of one-qubit gates A and B acting on each of the
qubits
• In this case, the matrix for the two-qubit gate is the tensor
product A ⊗ B
• It holds that
(A ⊗ B)(|ψ1 i ⊗ |ψ2 i) = (A |ψ1 i) ⊗ (B |ψ2 i)
• Of course, either A or B may be the identity
• This does NOT exhaust all posible two-qubit gates
50 / 211
The CNOT gate
• The CNOT (or controlled-NOT or cX ) gate is given by the

(unitary) matrix  
1 0 0 0
0 1 0 0
 
0 0 0 1
0 0 1 0
• If the first qubit is |0i, nothing changes. If it is |1i, we flip
the second bit (and the first stays the same)
• That is:
|00i → |00i |01i → |01i
|10i → |11i |11i → |10i
51 / 211
Action of the CNOT gate
• Its action on x, y ∈ {0, 1} is, then:
|xi • |xi
|y i |y ⊕ xi
• This is an extremely important gate for it allows to:
• Create entanglement (more on this soon)
• Copy classical information, because:
|00i → |00i
|10i → |11i
• Construct other controlled gates
52 / 211
Equivalences with CNOT gates
• Sometimes, CNOT gates are not implemented between all

pairs of qubits in a quantum computer
• We can use H gates to change the control and target of a
CNOT gate
H • H
H H
• We can swap states using three CNOT gates
• •
•
53 / 211
Constructing controlled gates by using the CNOT gate
• Any one-qubit gate U can be decomposed in the form
eiθ AXBXC
with ABC = I
• Then, the circuit
• • RZ (θ)
C B A
implements a U gate on the lower qubit controlled by the

upper qubit
54 / 211
The no-cloning theorem
• There is no quantum gate that makes copies of an
arbitrary (unknown) qubit
• The proof is easy: suppose we have a gate U such that
U |ψi |0i = |ψi |ψi
• Then U |00i = |00i and U |10i = |11i and by linearity
1 1 1
U √ (|00i+|10i) = √ (U |00i+U |10i) = √ (|00i+|11i)
2 2 2
• But
|00i + |10i |0i + |1i
√ = √ |0i
2 2
so we should have
|00i + |10i (|0i + |1i) (|0i + |1i) 1
U √ = √ √ 6= √ (|00i + |11i)
2 2 2 2
55 / 211
Quantum entanglement: the spooky action at a
distance
• We say that a state |ψi is a product state if it can be written

in the form
|ψi = |ψ1 i |ψ2 i
where |ψ1 i and |ψ2 i are two states (of at least one qubit)
• An entangled state is a state that is not a product state
• Example of entangled states (Bell states):
|00i + |11i |00i − |11i

√ √
2 2
|01i + |10i |01i − |10i
√ √
2 2
56 / 211
Hello, entangled world!
• We can construct (and measure) Bell states with simple

circuits
|0i H •
|0i
• Initially, the state of the system is |00i
• After we apply the H gate, the state is
|00i + |10i
√
2
• When we apply the CNOT gate, the state changes to
|00i + |11i
√
2
57 / 211
Hello, entangled world!
|0i H •
|0i
• Before we measure the first qubit, we have the state

|00i+|11i
√
2
• We will get 0 or 1, each with probability 21
• Suppose we obtain 0. Then, the new state will be |00i
• Then, when we measure the second qubit we will obtain 0
with probability 1!
• Also, if we obtain 1 in the first qubit, in the second we will
also obtain 1!
58 / 211
Part V
The CHSH game: Nature isn’t

classical, dammit
59 / 211
The CHSH game
• Based in an inequality proposed in 1969 by Clauser,
Horne, Shimony and Holt based on previous work by John
Bell
• Alice and Bob receive bits x and y from a referee
• They have to respond with bits a and b
• They win if
a⊕b =x ·y
• They can decide on a joint strategy beforehand, but they
cannot communicate during the game
Image credits: quantumcomputing.stackexchange.com
60 / 211
Classical strategies for the CHSH game
• Alice and Bob can win 75% of the time if they always
answer ‘0’
• No other deterministic strategy can do better
• And probabilistic strategies are convex combinations of
classical strategies so they cannot improve the 75%
success rate
Image credits: Ryan O’Donnell
61 / 211
Quantum strategy for the CHSH game
• Alice and Bob share a Bell pair |00i+|11i

√ before the start of
2
the game
• If Alice receives 0, she measures her qubit and ouputs the
result
• If she receives 1, she applies RY ( π2 ) to her qubit and then
she measures it
• If Bob receives 0, he applies RY ( π4 ). Else, he applies
RY (− π4 ).
• Then, he measures his qubit
• The probability of winning is now cos2 ( π8 ) ≈ 0.85 > 0.75
|0i H • RY ( π2 )
|0i RY ( π4 )
62 / 211
Some comments on the CHSH game
• It can be proved that cos2 ( π8 ) is the highest possible
success rate for a quantum strategy (Tsirelson’s bound)
• The CHSH game can be used to rule out local realism
• Several experiments have been conducted, including:
• Aspect et al. (1981-82)
• Hensen et al. (2005) - Eliminate the locality and detection
loopholes
• All of them agree with the predictions of quantum theory
Image credits: George Stamatiou based on png file of C.Thompson
63 / 211
The GHZ game
• Introduced by Greenberger, Horne and Zeilinger
• A referee selects rst from {000, 011, 101, 110} and sends r
to Alice, s to Bob and t to Charlie
• They produce a, b and c and win if
a⊕b⊕c =r ∨s∨t
• Classically, they can only win with 75% probability
• Quantumly, they can win every single time
• They share the state
1
(|000i − |011i − |101i − |110i)
2
• They apply H to their qubit if the receive 1
• They measure and return the answer
• This is sometimes called “quantum pseudo-telepathy”
(Brassard, Cleve, Tapp)
• Both the CHSH and the GHZ game can be used for
randomness certification (and expansion)
64 / 211
Part VI
Quantum teleportation and

superdense coding: entangled up in
blue
65 / 211
Quantum teleportation: Quantum me up, Scotty!
• Can Alice sent a qubit |ψi to Bob it there is no quantum
channel available?
• We are interested in the most general case, even if Alice
does not know which state she has
• The problem can be solved if Alice and Bob share an
entangled state √1 (|00i + |11i)
2
Image credits: www.geeksaresexy.net
66 / 211
Quantum teleportation: Alice’s part
• Alice and Bob share an entangled state √1 (|00i + |11i)
2
• This can be done in advance
• Or they can rely on a source that distributes entangled pairs
• Alice applies a CNOT gate to the qubit she wants to
teleport |ψi = a |0i + b |1i and to her part of the Bell pair.
We will have
1
√ (a(|000i + |011i) + b(|110i + |101i))
2
• Alice further applies the H gate to the qubit she wants
teleported. Then, we have
1
|00i (a |0i + b |1i) + |01i (b |0i + a |1i)
2
+ |10i (a |0i − b |1i) + |11i (−b |0i + a |1i)
• Alice measures her two qubits and sends the result (two
classical bits) to Bob (through a classical channel)
67 / 211
Quantum teleportation: Bob’s part
• Bob uses the second bit received from Alice to decide if he

applies X to his qubit
• And he uses the first bit to decide if he applies Z
Image credits: ProjectQ
68 / 211
Quantum teleportation: some comments
• It is not matter that is teleported but information

• When Alice measure her qubit, she looses it (if not, we
would be contradicting the no-cloning theorem)
• To teleport a qubit, we need two classical bits and one
entangled pair:
2bits + 1ebit ≥ 1qubit
• Teleportation is not instantaneous, we need classical

communication (no-communication theorem)
• Quantum teleportation has been shown experimentally
(current record is 1,400 km)
• Demonstration of quantum teleportation in Quirk
69 / 211
Entanglement swapping
• Quantum teleportation can also be used with entangled
qubits
• Alice shares a Bell pair with Bob and another one with
Charlie
• In the figure, the top and bottom qubits belong to Alice.
The second from the top belongs to Bob and the other to
Charlie
• Alice teleports her top qubit to Charlie
• Now Bob’s and Charlie’s qubits are entangled (although
maybe they were never in direct contact)
Image credits: Created with Quirk. Click here to access the circuit
70 / 211
Gate teleportation
• We can generalize the idea of quantum teleportation to
teleport the action of gates
• With the circuit of the figure, we can apply gate U to an
arbitrary state |ψi
• This is useful if preparing √1 (|0i U |0i + |1i U |1i) and
2
applying UXU † , UZU † , UZXU † are easy compared to
applying U to a general qubit
• Such a situation can happen when U = T in the context of
fault-tolerant quantum computing
|ψi • H •
|0i H • •
|0i U U† Z U
71 / 211
Superdense coding: two for the price of one (more or
less)
• As we have seen, in the presence of a Bell pair, we can

send a qubit with just two classical bits
• But... how many classical bits can we communicate with
one qubit?
• Holevo’s bound: the accesible information of one qubit is
just one bit
• However, if Alice and Bob share in advance a Bell pair...
we can send two bits of information with just one qubit!
1qubit + 1ebit ≥ 2bits
• This protocol is, in some sense, the inverse of quantum

teleportation
72 / 211
Superdense coding: Alice’s part
• Alice and Bob share a Bell pair in advance √1 (|00i + |11i)

2
• Alice wants to send to Bob two classical bits b1 and b2
• If b2 = 1, she applies X to her qubit
• If b1 = 1, she applies Z to her qubit
• Then, she sends her qubit to Bob
Image credits: www.quantum-bits.org
73 / 211
Superdense coding: Bob’s part
• Bob receives Alice’s qubit
• He applies a CNOT gate controlled by Alice’s qubit
• He applies H to Alice’s qubit
• He measures and recovers b1 and b2
Image credits: www.quantum-bits.org
74 / 211
Superdense coding: an example
• Suppose Alice wants to send 11

• We start with √1 (|00i + |11i)
2
• After Alice’s operations, we will have √1 (|01i − |10i)
2
• When Bob applies CNOT he obtains
1 1
√ (|01i − |11i) = √ (|0i − |1i) |1i
2 2
• And with the H gate he gets |11i that now he can measure
75 / 211
Part VII
Deutsch’s algorithm: the

grandfather of all quantum
algorithms
76 / 211
Deutsch’s algorithm: statement of the problem
• In 1985, David Deutsch proposed a very simple algorithm
that, nevertheless, hints at the capabilities of quantum
computing
• The problem it solves is only of theoretical relevance and
was later generalized in a joint work with Jozsa
• We are given a circuit (an oracle) that implements a
one-bit boolean function and we are asked to determine
whether the function is constant (returns the same value
for all inputs) or balanced (returns 1 on one input and 0 on
the other)
• Alternatively, we can think of the oracle as indexing a bit
string of length two and we are asked to compute the XOR
of the bits of the string
• In the classical case, we would need to consult the oracle
twice, to compute both values of the function
• In the quantum case, we can make just one oracle call...
but in superposition
77 / 211
Deutsch’s algorithm: the oracle
• An oracle is treated as a black box, a circuit whose interior

we cannot know
• This circuit computes, in a reversible way, a certain
function f (in our case, of just one input)
• For the computation to be reversible, it uses as many
inputs as outputs and “writes the result” with an XOR
|xi |xi
Of
|y i |y ⊕ f (x)i
78 / 211
Deutsch’s algorithm: the circuit
• The quantum circuit that we need to use to solve the

problem is very simple
|0i H H
Of
|1i H
• If the function is constant, we will measure 0

• If the function is balanced, we will measure 1
79 / 211
Deutsch’s algorithm: the magic
|0i H H
Of
|1i H
• The initial state is |0i |1i
• After the H the gates we have
(|0i + |1i)(|0i − |1i)
2
which is the same as
|0i (|0i − |1i) |1i (|0i − |1i)
+
2 2
• When we apply the oracle, by linearity we obtain
|0i (|0 ⊕ f (0)i − |1 ⊕ f (0)i) |1i (|0 ⊕ f (1)i − |1 ⊕ f (1)i)
+
2 2
80 / 211
Deutsch’s algorithm: the magic (2)
|0i H H
Of
|1i H
• If f (0) = 0, we have
|0 ⊕ f (0)i − |1 ⊕ f (0)i = |0i − |1i
• However, if f (0) = 1 we get
|0 + f (0)i−|1 ⊕ f (0)i = |0 ⊕ 1i−|1 ⊕ 1i = |1i−|0i = −(|0i−|1i)
• For f (1) the situation is the same so the global state is
(−1)f (0) |0i (|0i − |1i) (−1)f (1) |1i (|0i − |1i)
+
2 2
81 / 211
Deutsch’s algorithm: the magic (3)
|0i H H
Of
|1i H
• We can also write that state as
|0i (|0i − |1i) (−1)f (0)+f (1) |1i (|0i − |1i)
+
2 2
• So if f (0) = f (1), we will have
|0i (|0i − |1i) |1i (|0i − |1i) (|0i + |1i)(|0i − |1i)
+ =
2 2 2
and when we apply the last H and measure we obtain 0.
• But if f (0) 6= f (1), the state is
|0i (|0i − |1i) |1i (|0i − |1i) (|0i − |1i)(|0i − |1i)
− =
2 2 2
and, then, we obtain 1.
82 / 211
Deutsch’s algorithm: some comments
• When we apply the oracle we have a phase kickback: we
only act on one qubit, but it affects the whole state
• Deutch’s algorithm exploits an interference phenomenon
similar to that found in some physical experiments
(double-slit experiment, Mach-Zehnder interferometer)
Image credits: Wikipedia
83 / 211
Part VIII
Multiqubit systems: growing up!
84 / 211
n-qubit systems
• When he have n qubits, each of them can be in state |0i
and |1i
• Thus, for the n-qubit state we have 2n possibilities:
|00 . . . 0i , |00 . . . 1i , . . . , |11 . . . 1i
or simply
|0i , |1i , . . . , 2n − 1

• A generic state of the system will be
|ψi = α0 |0i + α1 |1i + . . . + α2n −1 2n − 1

where αi are complex numbers such that

n −1
2X
|αi |2 = 1
i=0
85 / 211
Measuring a n-qubit state
• Suppose we have the n-qubit state
|ψi = α0 |0i + α1 |1i + . . . + α2n −1 2n − 1

• If we measure all its qubits, we obtain:

• 0 with probability |α0 |2 and the new state will be |0 . . . 00i
• 1 with probability |α1 |2 and the new state will be |0 . . . 01i
• ...
• 2n − 1 with probability |α2n −1 |2 and the new state will be
|1 . . . 11i
• It is analogous to what we had with one and two qubits, but
now with 2n possibilities
86 / 211
Measuring one qubit in a n-qubit state
• We have
|ψi = α0 |0i + α1 |1i + . . . + α2n −1 2n − 1

• If we measure the j-th qubit

• We will get 0 with probability
X
|αi |2
i∈I0
where I0 is the set of numbers whose j-th bit is 0

• In that case, the new state |ψi will be
P
i∈I0 αi |ii
qP
2
i∈I0 |αi |
• The case in which we obtain 1 is analogous
87 / 211
n-qubit quantum gates
• A n-qubit state is
|ψi = α0 |0i + α1 |1i + . . . + α2n −1 2n − 1

• We can represent it by the column vector

 
α0
 α1 
 
 α2 
 
 .. 
 . 
α2n −1
• To compute inner products with Dirac notation we only

need to note that
hi|ji = δij
• Thus, a n-qubit quantum gate is a unitary matrix U of size
2n × 2n
88 / 211
The Toffoli gate
• The Toffoli gate (or CCNOT ) is a 3-qubit gate. Thus, it can

be represented as a 8 × 8 matrix
• Its action on elements x, y, z ∈ {0, 1} is:
|xi • |xi
|y i • |y i
|zi |z ⊕ (x ∧ y)i
• The Toffoli gate is universal for classical logic, and thus
any classical circuit can be simulated with a quantum
circuit
• However, the Toffoli gate, on its own, is not universal for
quantum computing (and it is not even necessary,
because it can be simulated with one and two-qubit gates)
89 / 211
Universal gates in quantum computing
• The number of quantum gates (even for a single qubit) is

uncountably infinite. Thus, no finite set of gates is universal
in the classical sense
• However, we can obtain finite sets of gates that allow us to
approximate any other gate as much as we want
Theorem
The one-qubit gates together with the CNOT gate are universal
for quantum computing
Theorem
The gates X , H, T and CNOT are universal for quantum
computing
90 / 211
Gate equivalences
Z = H X H
S = T T
Y = Z X S X S X
T† = S S S T
S† = S S S
However, Z , S, Y , S † and T † are usually included among the

available gates in most quantum computers (such as the ones
in the IBM Q Experience).
91 / 211
Equivalence of the Toffoli gate
H T† T T† T H
• • T T†
• • • T •
92 / 211
Part IX
Everything you always wanted to

know about quantum parallelism but
were afraid to ask
93 / 211
Urban legends about quantum parallelism
• But... don’t quantum computers try all 2n possibilities in
parallel?
• The answer is... yes and no (this is quantum computing
after all!)
Image credits: The Talk, by Scott Aaronson and Zach Weinersmith
94 / 211
Evaluating a function: querying the oracle
• As we know, in quantum computing every gate is reversible

• To compute a function f we keep the inputs unchanged
and xor the result to the output qubits
• This type of circuit is called and oracle for f (we have
already used an oracle for a one-bit function in Deutsch’s
algorithm)
 
 

 
|xi |xi

 Of 


|yi |y ⊕ f (x)i
95 / 211
Evaluating a function in parallel: the superposition
hocus-pocus
• Suppose that we have an oracle Of for a function f (x) with
a one-bit input
• We know that, using the H gate, we can put a qubit in
superposition
• If we start with the state |0i |0i and we apply H on the first
qubit, we will have
1 1
√ |0i |0i + √ |1i |0i
2 2
• If we now apply Of , by linearity we have
1 1
√ |0i |f (0)i + √ |1i |f (1)i
2 2
• We have evaluated the function on two different inputs with
just one call!
96 / 211
Evaluating a function in parallel: the tensor-product
abracadabra
• We can do something similar with a function

f (x1 , x2 , . . . , xn ) on n-variables by using the following circuit
H




|0i⊗n H


 Of
H
|0i
• When we apply the H gates we obtain
(|0i + |1i)(|0i + |1i) · · · (|0i + |1i) |0i

√
2n
97 / 211
Evaluating a function in parallel: the tensor-product
abracadabra (2)
• If we expand the product we get
n2 −1
(|0 . . . 0i + |0 . . . 1i + . . . + |1 . . . 1i) |0i 1 X
√ =√ |xi |0i
2n 2n x=0
• And, when we apply the oracle, we will get the state
n
2 −1
1 X
√ |xi |f (x)i
2n x=0
• An exponential number of function evaluations with just
one call!
H




|0i⊗n H


 Of
H
|0i 98 / 211
Quantum parallelism vs. non-deterministic machines
• With a non-deterministic machine, we could choose at will
some value f
• This would allow us to solve NP-complete problems
• A similar idea is used in the plot of Quarantine, a
science-fiction novel by Greg Egan
99 / 211
All that glitters ain’t gold
• And now... how do we retrieve the values f (x)?
• To obtain a result, we need to perform a measurement
• But then we will get a state of the form
|ci |f (c)i
• That is, we only obtain the result of the function for a
randomly chosen input (this may be even worse than
classically evaluating the function)
Image credits: The Talk, by Scott Aaronson and Zach Weinersmith 100 / 211
Interferences come to the rescue
• How can we use the 2n evaluations to extract useful
information?
• One possibility is... to produce interferences!
• The amplitudes of some states can be negative
• If we manage to “annihilitate” the amplitudes of states we
are not interested in, the probability of obtaining the
answer that we need will grow
• This is, in general, no easy task, but we know how to
achieve it in some interesting cases
Image credits: The Talk, by Scott Aaronson and Zach Weinersmith 101 / 211
Part X
The Deutsch-Jozsa algorithm: a

very fast way of solving a problem
that nobody asked to solve
102 / 211
Reminder: Deutsch’s algorithm
• We have an oracle Of for a boolean function f (x)

• f can be constant (returns the same value for all inputs) or
balanced (returns 1 on one input and 0 on the other)
• Distinguishing one situation from the other requires, in the
classical case, evaluating the function on the two possible
inputs
• With a quantum computer, we can solve the problem with
just one call to Of
• The key is to use quantum parallelism together with
interference
|0i H H
Of
|1i H
103 / 211
Upping the ante: the Deutsch-Jozsa algorithm
• The Deutsch-Jozsa algorithm solves a type of problem

called promise problem
• We are given a boolean function f (x1 , . . . , xn )
• We are promised that f is either constant (always 0 or 1) or
balanced (0 for half of the inputs and 1 for the rest)
• We have to decide which of the two cases we are in by
calling the function as few times as possible
• With a classical deterministic algorithm we need (in the
worst case) 2n−1 + 1 calls to f
• With the Deutsch-Jozsa quantum algorithm it is enough to
evaluate f just once
104 / 211
Circuit for the Deutsch-Jozsa algorithm
H H





|0i⊗n H H
Of




H H
|1i H
105 / 211
Steps in the Deutsch-Jozsa algorithm
1 We create the state |0 . . . 0i |1i

2 We use Hadamard gates to create the superposition
X 1
√ |xi (|0i − |1i)
x∈{0,1}n
2n+1
3 We apply the oracle, getting

X 1
√ |xi (|0 ⊕ f (x)i − |1 ⊕ f (x)i) =
x∈{0,1}n
2n+1
X (−1)f (x)
√ |xi (|0i − |1i)
x∈{0,1}n
2n+1
106 / 211
Steps in the Deutsch-Jozsa algorithm (2)
4 We apply again Hadamard gates to the n first qubits and

we obtain
X X (−1)f (x)+x·y
√ |yi (|0i − |1i)
y∈{0,1}n x∈{0,1}n
2n 2
5 Finally, we measure the n first qubits.

6 If the function is constant, we will obtain |0i. Otherwise (if
the function is balanced), we will get a string different from
|0i.
107 / 211
Correctness of the algorithm
• The probability of measuring |0i is exactly

 2  2

X (−1)f (x)+x·0  =
X (−1)f (x) 
2n 2n
x∈{0,1}n x∈{0,1}n
• If f is constant, the sum is 1

• If f is balanced, the sum is 0
108 / 211
Some comments on the Deutsch-Jozsa algorithm
• The problem we have solved is academical, with no

practical interest
• But... it shows how quantum computing can obtain global
information about a function with just one evaluation
• The key is to use:
• Quantum parallelism (because of superposition)
• Interference (constructive and destructive)
• Similar ideas are used in other algorithms, like the
Bernstein-Vazirani and Simon methods
109 / 211
Part XI
Grover’s algorithm: finding the

needle in the haystack
110 / 211
Statement of the problem
• Grover’s algorithm is used to solve search problems
• Imagine we have an unsorted list of N elements
• One of them verifies a certain condition and we want to
find it
• Any classical algorithm requires O(N) queries to the list in
the worst case √
• Grover’s algorithm can find the element with O( N)
queries
Image credits: Downloaded from www.usnewsglobaleducation.com
111 / 211
The oracle
• As in Deutsch-Jozsa’s algorithm, we will use an oracle

• This oracle computes the function f : {0, 1}n ⇒ {0, 1} (with
N = 2n )
• The element we want to find is the one that verifies
f (x) = 1
 
 

|xi  |xi
Of  
|yi |y ⊕ f (x)i
112 / 211
The idea behind the algorithm
• Grover’s algorithm is based on the idea of inversion about

the mean
Image credits: quantumcomputing.stackexchange.com
113 / 211
Grover’s algorithm
√
• Grover’s algorithm performs O( N) iterations, each one
consisting in an oracle query and a call to Grover’s
diffusion operator
• The oracle “marks” those states that verify the condition
• The diffusion operator “amplifies” the amplitudes of the
marked states
√
O( N)
z }| {

 H H X • X H . . .



|0i⊗n H H X • X H ...
O

f



H H X Z X H ...
|1i H ...
114 / 211
Grover’s algorithm as a rotation
• Let us denote by |x1 i the marked element

• Then, the initial state of the upper n qubits is
r r
N −1 1
|x0 i + |x1 i
N N
where r
X 1
|x0 i = |xi
N −1
x∈{0,1}n ,x6=x1
• We can choose θ ∈ (0, π2 ) such that

r r
N −1 1
cos θ = sin θ =
N N
115 / 211
Grover’s algorithm as a rotation (2)
• Define D to be Grover’s diffusion operator and G = DOf

• It can be shown that G acts on the 2-dimensional space
spawned by |x0 i and |x1 i as a rotation of angle 2θ
• That is
G |x0 i = cos 2θ |x0 i + sin 2θ |x1 i
G |x1 i = − sin 2θ |x0 i + cos 2θ |x1 i
r
X 1
|x0 i = |xi
n
N −1
x∈{0,1} ,x6=x1
• Since the initial state is cos θ |x0 i + sin θ |x1 i, after m

iterations we will have
cos (2m + 1)θ |x0 i + sin (2m + 1)θ |x1 i
116 / 211
Grover’s algorithm as a rotation (3)
• In order to obtain |x1 i with high probability when we
measure we need
π
(2m + 1)θ ≈
2
and this gives
π 1
m≈ −
4θ 2
• Since r
1
sin θ =
N
we will have r
1
θ≈
N
and then we can choose
jπ √ k
m= N
4
117 / 211
The case with multiple marked elements
• If the number of marked elements is k > 1, a similar
argument can be made by defining
r
X 1
|x0 i = |xi
N −k
f (x)=0
r
X 1
|x1 i = |xi
k
f (x)=1
• In this case r
k
sin θ =
N
and if k N we can choose
$ r %
π N
m=
4 k
118 / 211
The case with unknown number of marked elements
• If we do not know how many elements are marked, we can

still user Grover’s algorithm
• We can use Grover’s circuit combined with the Quantum
Fourier Transform to estimate k
• Or we can choose m at random.lFor instance:
√ m
• Uniformly from the set {0, . . . , N +1 }
• With an incremental scheme, starting with an upper√bound
for m of b = 1 and increasing it exponentially up to N
• In all the cases, it can be shown that a√marked element will
be found with high probability with O( N) queries to the
oracle
119 / 211
Some comments on Grover’s algorithm
• When we measure, we will obtain x such that f (x) = 1 with
probability depending on:
• The number m of iterations
• The fraction of values x that satisfy the condition
• If we perform too many iterations, we can overshoot and
not find a marked element
• On the other hand, if k = N4 then one iteration will find a
marked element with certainty
• Grover’s algorithm can be used to find minima of functions
(Dürr-Hoyer’s algorithm)
• It can be shown that no other quantum algorithm can
obtain more than a quadratic speed-up over over classical
algorithms in the same setting
• A generalization of Grover’s algorithm called Amplitude
Amplification can be used with states prepared by an
arbitrary unitary A
120 / 211
Part XII
Shor’s algorithm: breaking the

Internet
121 / 211
Shor’s algorithm and factoring
• Shor’s algorithm is, probably, the most famous quantum
algorithm
• It finds a factor of a n-bit integer in time
O(n2 (log n)(log log n))
• The best classical algorithm that we know of for the same
1 2
task needs time O(ecn 3 (log n) 3 )
• Dramatic consequences for current cryptography (RSA)
Image credits: Jose-Luis Olivares/MIT 122 / 211

Steps of Shor’s algorithm
1 Given N, check that N is not a prime or power of a prime. If

it is, stop.
2 Choose 1 < a < N at random
3 If b = gcd(a, N) > 1, output b and stop
4 Find the order of a mod N, that is, r > 0 such that ar ≡ 1
mod N
5 If r is odd, go to 2
6 Compute
r
x = a2 + 1 mod N
r
y = a − 1 mod N
2
r
7 If x = 0, go to 2. If y = 0, take r = 2 and go to 5.
8 Compute p = gcd(x, N) and q = gcd(y, N). At least one of
them will be a non-trivial factor of N
123 / 211
Correctness of Shor’s algorithm
• We know that
ar ≡ 1 mod N
• Thus
r r
x · y ≡ (a 2 + 1)(a 2 − 1) ≡ (ar − 1) ≡ 0 mod N
• This means that x · y is a multiple of N

• Since neither x nor y are multiples of N, either p or q
divides N
• It can be proved that step 8 will be reached with high
probability
124 / 211
Implementation of Shor’s algorithm
• Every step but number 4 are carried out on a classical

computer (efficient algorithms exist)
• For step 4, there exists a quantum circuit with a number of
gates that is polynomial on n (the number of bits of N)
|0i H ··· •
.. .. ..
. . .
QFT†m
|0i H • ···
|0i H • ···
|1i /n Ua2
0
Ua2
1
··· m−1
Ua2
125 / 211
Preparing a periodic sequence
• The first part of the circuit computes

m
2 −1
1 X
√ |xi |ax mod Ni
2m x=0
• When we measure the bottom qubits, we obtain
1 X
p |xi |ci
|C| x∈C
where c is some value in {0, . . . , N − 1} and C = {x : ax

mod N = c}.
126 / 211
Preparing a periodic sequence (2)
• For example, if a = 2, N = 5, m = 4, we would have
1
(|0i |1i + |1i |2i + |2i |4i + |3i |3i + |4i |1i + . . . + |15i |3i)
4
and when we measure we could obtain, for instance
1
(|1i |2i + |5i |2i + |9i |2i + |13i |2i)
2
• Notice that the values of the first register are exactly 4 units
apart and that 24 = 1 mod 5.
• In general, we will obtain values that are r units apart,
where ar = 1 mod N.
127 / 211
Measuring the period
• To retrieve the period r we use the (inverse) of the
Quantum Fourier Transform (QFT)
• Two properties of the QFT are central here:
• Shift-invariance (up to an unobservable phase)
• QFT transforms sequences with period r into sequences
with period Mr (where M = 2m )
• After the use of the inverse QFT, we can measure a value
of the form Mc
r with high probability and, from it, obtain r
Image credits: Umesh Vazirani

128 / 211
Quantum Fourier Transform: definition and circuit
• The QFT of order m is the unitary transformation defined
by
2m −1
1 X 2πijk
QFT |ji = √ e 2m |k i
2m k=0
• The circuit in the figure implements the QFT
• The Rk gates in the circuit are what we call RZ ( 2πk )
2
• The number of gates is quadratic in m, an exponential
speed-up over the classical case (FFT)
• For Shor, m can be chosen to be about 2n
Image credits: Jurgen Van Gael
129 / 211
Using the QFT for phase estimation
• Suppose we are given a unitary operation U and one of its
eigenvectors |ψi
• We know that there exists θ ∈ [0, 1) such that U |ψi = e2πiθ
• We can estimate θ with the circuit shown below
P n −1 2πiθk
• With the first part, we will obtain √1 n 2k=0 e |k i
2
• By using the inverse QFT we can measure j ≈ 2n θ
130 / 211
Shor’s algorithm as a particular case of quantum
phase estimation
• Clearly, the circuit used in Shor’s algorithm is a case of
quantum phase estimation
• It can be shown that the (unitary) operation of modular
mutiplication by a has eigenvalues
k
e2πi r k = 0, . . . , r − 1
where r is the period of a

• It is not easy to prepare one of the eigenvectors |ψk i of the
unitary operation
• But we use the fact that
r −1
1 X
|1i = √ |ψk i
r k=0
• We will then measure a value close to 2m k

r for some k
131 / 211
Using quantum phase estimation to count the number
of marked elements
• We can use Grover’s algorithm together with the QFT to
count the number of elements marked by a boolean
function
• The eigenvalues of Grover’s operator are e±2iθ where
q
sin θ = Nk
• Then, with quantum phase estimation we can recover k,
the number of marked elements
132 / 211
HHL: Applying quantum phase estimations to solve
linear systems of equations
• A quantum algorithm proposed in 2009 by Harrow,
Hassidim and Lloyd can be used to solve linear systems of
equations
• The main steps of the algorithm are
• Computation of the eigenvalues (quantum phase
estimation)
• Inversion of the eigenvalues
• Uncomputation of the eigenvalues (inverse of quantum
phase estimation)
Image credits: Niel de Beaudrap

133 / 211
Visualizing Shor’s algorithm with Qirk
• Case a = 2 and N = 15
• Case a = 4 and N = 15
• Case a = 14 and N = 15
• Case a = 26 and N = 55
Image credits: Created with Quirk
134 / 211
Part XIII
Quantum annealing: when time is

gold
135 / 211
The maximum cut or Max-Cut problem
• Consider the problem of dividing the vertices of a graph
into two sets such that the number of edges with extremes
in both sets is the maximum possible
• It can be proved that this problem, called “maximum cut” or
“Max-Cut”, is NP-hard
• It is also APX-Hard and thus there is no (classical)
polynomial-time approximation scheme (PTAS) which gets
arbitrarily close to the solution (unless P = NP)
Image credits: Wikipedia.org

136 / 211
Stating Max-Cut with spins
• We can identify each vertex i of the graph with a variable Zi

• We assign value 1 to the vertices of one group and -1 to
the others
• Then, if E is the set of edges, the problem can be stated as
X
Minimize Zi Zj
(i,j)∈E
since vertices in different groups contribute -1 and vertices

of the same group contribute 1
137 / 211
Example of Max-Cut problem
• For the graph of the figure we need to minimize
H = Z1 Z2 + Z1 Z3
• By inspection (or enumerating the eight possibilities) it is

easy to see that the solutions are 011 and 100
138 / 211
Enter quantum computing
• Remember that the matrix of gate Z is

1 0
0 −1
and that the vector |0i has coordinates

1
0
• Then
1 0 1
1 0 =1
0 −1 0
• Using Dirac notation, we can denote this by
h0| Z |0i = 1
139 / 211
Enters quantum computing (2)
• Analogously

0
|1i =
1
• And thus

1 0 0
h1| Z |1i = 0 1 = −1
0 −1 1
• If we have more qubits, we evaluate each product

independently and multiply the results. For instance:
h01| Z1 Z2 |01i = (h0| Z1 |0i) · (h1| Z2 |1i) = 1 · (−1) = −1
and
h101| Z1 Z3 |101i = (h1| Z1 |1i)·(h1| Z3 |1i) = (−1)·(−1) = 1
140 / 211
Back to the Max-Cut example
• We had the Max-Cut problem given by
H = Z1 Z2 + Z1 Z3
• We can identify a possible cut with |011i (vertices 2 and 3

in one set and 1 in the other) and evaluate its cost by
h011| H |011i = h011| (Z1 Z2 + Z1 Z3 ) |011i

= h011| Z1 Z2 |011i + h011| Z1 Z3 |011i = −1 + (−1) = −2
• Analogously
h010| H |010i = h010| (Z1 Z2 + Z1 Z3 ) |010i

= h010| Z1 Z2 |010i + h010| Z1 Z3 |010i = −1 + 1 = 0
141 / 211
Hamiltonians, Hamiltonians everywhere
• Then, we are interested in finding a (basis) quantum state

|xi such that
hx| H |xi
P
is minimum, with H = (i,j)∈E Zi Zj the cost function of the
Max-Cut problem
• This is a particular case of a very important problem:
finding the ground state or minimum energy state of a
Hamiltonian
• A Hamiltonian is a Hermitian matrix H (i.e. it verifies
H = H †)
• The (expected) energy of a state |ψi is
hψ|H|ψi
142 / 211
Example: the Ising model
• We have n spins that interact with their neighbours
• The Hamiltonian of the system is
X n
X
H= Jij Zi Zj + hi Zi
1≤i<j≤n i=1
with Jij and hi real coefficients

• We want to find a value assignment (1 or -1) that
minimizes the sum
• The problem is NP-hard (it includes the Max-Cut problem)
Image credits: Peter Eastman

143 / 211
QUBO: Quadratic Unconstrained Binary Optimization
• A closely related family of problems is that of Quadratic
Unconstrained Binary Optimization (QUBO)
• These problems are stated as
n
X
Minimize wij xi xj
1≤i≤j≤n
where each xi is a binary variable and wij are real

coefficients
• We can transform the problem into an Ising model via
1 − zi
xi =
2
and get back to QUBO with
zi = 1 − 2xi
144 / 211
Adiabatic quantum computing
• How to obtain the ground state of H?

• A natural approach is to apply H itself to reach the solution
• The adiabatic theorem (roughly) says that if we start in
the ground state of a Hamiltonian and we change this
Hamiltonian slowly, we will stay in a ground state
• The idea behind adiabatic quantum computing is
• Start with the ground state of a simple Hamiltonian Hi
• Evolve the the system to the ground state of the problem
Hamiltonian Hf
• To achieve that, we apply a time-dependent Hamiltonian
t t
H(t) = (1 − )Hi + Hf
T T
for time T
145 / 211
Adiabatic quantum computing (2)
• To guarantee adiabaticity, T must grow as the inverse of

the square of the spectral gap of H(t) (difference between
the first and the second energy levels)
• The spectral gap is hard to compute
• In practice, quantum annealing is used:
P n −1
• We take Hi = − nj=1 Xj (with ground state 2x=0
P
|xi)
• Hf is an Ising Hamiltonian that encodes our problem
• We let the system evolve for time T (no necessarily
adiabatic)
• We measure to obtain a candidate solution
• We repeat the process a number of times and keep the
best solution
• This is the basis of D-Wave’s quantum computers
146 / 211
D-Wave’s quantum computers
• These are special-purpose computers: they find

approximate solutions of the Ising model
• Free access (1 minute/month) at
https://www.dwavesys.com/take-leap
• We will test them with this example
147 / 211
An application in High Energy Physics
148 / 211
An application in High Energy Physics (2)
• Signal: production of a Higgs boson through the fusion of
two gluons which then decay into two photons
• Background: standard-model two-photon production
processes
149 / 211
• The authors consider 36 weak classifiers ci (x) and
combine them to form a strong classifier
X
O(x) = wi ci (x)
i
with wi ∈ {0, 1}
• They minimize
X X
(y (x) − wi ci (x))2
x i
which, when an additional regularization parameter λ is

added, is equivalent to minimizing
X X
Cij wi wj + (λ − 2Ci )wi
i,j i
P P
where Cij = x ci (x)cj (x) and Ci = x ci (x)y (x).
150 / 211
151 / 211
Part XIV
Quantum Approximate Optimization

Algorithm: going digital
152 / 211
The Quantum Approximate Optimization Algorithm
• The Quantum Approximate Optimization Algorithm (QAOA)

was proposed by Farhi, Goldstone and Gutmann (2014) to
obtain approximate solutions of the problem of minimizing
X
C(x) = wa Ca (x)
a
where x is n-bit string, wa are real weights and each Ca is

a boolean function
• Max-Cut is one such problem, with every wa equal to 1 and
each Ca of the form
xi ⊕ xj
• The maximum satisfiability (MAX-SAT) and weighted
maximum satisfiability (weighted MAX-SAT) are other
examples of that kind of problems
153 / 211
Boolean functions and Hamiltonians
• For each boolean Ca we can find a Hamiltonian Ha of the
form
X X X
a0 I + ai Zi + aij Zi Zj + aijk Zi Zj Zk + · · ·
i i<j i<j<k
such that for every string x it holds that Ca (x) = hx| Ha |xi
• Then, minimizing C(x) is equivalent to finding the ground
state of X
Hf = wa Ha
a
since Hf is diagonal and hx| Hf |xi = C(x).
Image credits: Stuart Hadfield https://arxiv.org/pdf/1804.09130.pdf

154 / 211
The parametrized states of QAOA
• QAOA is an adaptation of the adiabatic model to
gate-based quantum computers
• Remember that the adiabatic Hamiltonian was
t t
H(t) = (1 − )Hi + Hf
T T
Pn
with Hi = − j=1 Xj
• As an approximation of the evolution of the system, we
consider parametrized states of the form
|β, γi = e−iβp Hi e−iγp Hf . . . e−iβ2 Hi e−iγ2 Hf e−iβ1 Hi e−iγ1 Hf |si
where p ≥ 1 and
n −1
2X
|si = |xi
i=0
155 / 211
Optimization with QAOA
• QAOA is a hybrid method in which both a quantum and

classical computer are used
• The steps are:
1 Choose a value for p and some initial angles β, γ
2 Prepare the state |β, γi
3 Estimate the energy E(β, γ) = hβ, γ| Hf |β, γi of |β, γi
4 Vary β and γ in order to minimize E(β, γ)
5 If the stopping criterium is met, stop. Else, go to 2
• Step 2 is carried out on the quantum computer and steps
1, 3 and 4, on a classical one
156 / 211
How to prepare |β, γi
P n
• We already know that |si = 2i=0−1 |xi can be prepared
with Hadamard gates
• Each e−iβk Xj is a rotation RX (2βk ) or equivalently

xj H RZ (2βk ) H
• To implement e−iγk Hf we only need to consider cases of

the form
−iγ Z ···Z
e k i1 ij
because
• All terms of the form Zi1 · · · Zij commute
• The weights in Hf = a wa Ha are “absorbed” by the angles
P
γ
157 / 211
−iγk Zi1 ···Zij
Implementing e
• Notice that e−iγk Zi1 ···Zij is diagonal in the computational

basis
• In fact, for a binary string x = x1 . . . xn it acts on |xi as
• |xi → e−iγk |xi if xi1 ⊕ · · · ⊕ xij = 0 mod 2
• |xi → eiγk |xi if xi1 ⊕ · · · ⊕ xij = 1 mod 2
• This is very similar to the action of a RZ rotation
• Then, we can:
• Compute the parity xi1 ⊕ · · · ⊕ xij with CNOT gates
• Apply RZ (2γk ) on the qubit where we have computed the
parity
• Uncompute the parity
158 / 211
An example
• Imagine that we are working with 4 qubits and we want to

implement e−iγZ1 Z2 Z4
• We can use the following circuit:
|x1 i • •
|x2 i • •
|x3 i
|x4 i RZ (2γ)
159 / 211
Estimating the energy
• Estimating the energy is very easy in the case of QAOA
• We repeat the following process a fixed number of times:
1 Prepare the state |β, γi
2 Measure it to obtain a string x
3 Compute C(x)
and then we average the results
• This works because if
X
|β, γi = ax |xi
x∈{0,1}n
then X
hβ, γ| Hf |β, γi = |ax |2 C(x)
x∈{0,1}n
• It is also interesting to keep the string x with minimum

value C(x) over all we obtain when we measure
160 / 211
Some comments on QAOA
• For the procedure to be efficient, Hf must have a number
−iγ Z ···Z
of terms e k i1 ij that is polynomial in the number n of
qubits and the number m of clauses Ca (x) of C(x)
• If a clause Ca (x) only involves k bits, then its translation Ha
will involve terms with at most k Pauli matrices Zi
• Thus, if p is a constant independent of n and m and all
clauses involve at most k bits (also independent of n and
m) then the number of gates will be polynomial in n and m
• This is the case, for example, of problems such as MaxCut
or Max 3-SAT
• When p → ∞, the ground state of |β, γi tends to the
ground state of Hf
• Interesting results can be obtained in some cases even for
small p
• The choice of classical optimizer is important
161 / 211
Applying QAOA for particle track reconstruction
162 / 211
Applying QAOA for particle track reconstruction (2)
• QUBO formulation to select the best pairs of triplets by
minimizing
X X
O(a, b, T ) = ai Ti + bij Ti Tj
where the ai are bias weights expressing quality of the
triplets (all equal) and the bij are coupling strengths
between triplets
• From this formulation, QAOA is planned to be applied on
Rigetti computers (work by Eric Rohm at Lawrence
Berkeley National Laboratory)
163 / 211
Part XV
Variational Quantum Eigensolver:

endless forms most beautiful
164 / 211
VQE: Variational Quantum Eigensolver
• QAOA can be seen as a particular case of a more general
algorithm: the Variational Quantum Eigensolver (VQE)
• Now, we will have a general Hamiltonian Hf (with a
polynomial number of terms) and we want to approximate
its ground state
• Instead of the parametrized state |β, γi of QAOA we will
use
• An initial state |ψi that is easy to prepare (it could be just
|0i)
• A parametrized unitary U(θ) that is called a variational
form
• We can create an ansatz
|ψ(θ)i = U(θ) |ψi
and try to minimize its energy with respect to Hf by varying

the parameters
165 / 211
The variational principle
• Since Hf is a Hermitian matrix, it has real eigenvalues λi

and an associated orthonormal basis of eigenvectors |φi i
• Then, we can write |ψ(θ)i as a linear combination
X
|ψ(θ)i = αi |φi i
i
• The energy of |ψ(θ)i is

X
hψ(θ)| Hf |ψ(θ)i = |αi |2 λi
i
• If λmin is the minimum of the eigenvalues then
min hψ(θ)| Hf |ψ(θ)i ≥ λmin

θ
166 / 211
Approximating the ground state with VQE
• VQE is also a hybrid method in which both a quantum and

classical computer are used
• The steps are:
1 Choose an initial state |ψi, a variational form U(θ) and
some initial vector θ
2 Prepare the state |ψ(θ)i = U(θ) |ψi
3 Estimate the energy E(θ) = hψ(θ)| Hf |ψ(θ)i of |ψ(θ)i
4 Vary θ in order to minimize E(θ)
5 If the stopping criterium is met, stop. Else, go to 2
• Step 2 is carried out on the quantum computer and steps
1, 3 and 4, on a classical one
167 / 211
Estimating the energy of a state
• The Hamiltonian can be always expressed as a linear

combination of tensor product of Paulis
• For instance
1
Hf = Z1 Z3 − 3X1 Y3 Z4
4
• Given |ψi, we can use linearity and evaluate
1
hψ| Hf |ψi = hψ| Z1 Z3 |ψi − 3 hψ| X1 Y3 Z4 |ψi
4
• To estimate hψ| Z1 Z3 |ψi we can just measure |ψi in the
computational basis and average the energies of the
results (which will be 1 or -1 for each individual
measurement result).
168 / 211
Estimating the energy of a state (2)
• To estimate hψ| X1 Y3 Z4 |ψi we can notice that
X = HZH
and
Y = SHZHS †
• Then hψ| X1 Y3 Z4 |ψi is equal to
hψ| (H ⊗ I ⊗ SH ⊗ I)Z1 Z3 Z4 (H ⊗ I ⊗ HS † ⊗ I) |ψi
• Thus, we can just measure the energy on Z1 Z3 Z4 of

(H ⊗ I ⊗ HS † ⊗ I) |ψi because
†
(H ⊗ I ⊗ HS † ⊗ I) |ψi = hψ| (H ⊗ I ⊗ SH ⊗ I)
• Notice that this is equivalent to measuring in a different

basis
169 / 211
Simulating molecules with VQE
• VQE has been used to estimate ground states of several
molecules
• The fermionic Hamiltonian has to be translated into a qubit
Hamiltonian (Jordan-Wigner, Bravyi-Kitaev...)
• Information of the problem is used for:
• The initial state (vacuum state |0i, Hartree-Fock...)
• The variational form (Unitary Coupled-Cluster Single and
Double excitations...)
Image credits: Kandala, Mezzacapo, Temme, Takita, Brink, Chow, Gambetta. Nature 549, 242–246 (2017)
170 / 211
Finding excited states
• We can also use VQE to find excited states (eigenstates

that are not the ground state)
• Once we have the ground state |ψ0 i = U(θ0 ) |ψi, we
consider the Hamiltonian
Hf0 = Hf + C |ψ0 i hψ0 |
• Then, we have that hϕ| Hf0 |ϕi is
hϕ| Hf |ϕi + C hϕ|ψ0 i hψ0 |ϕi = hϕ| Hf |ϕi + C| hψ0 |ϕi |2
• if C is bigger than the difference between the ground

energy and the next energy level of Hf , then |ψ0 i is not the
ground state of Hf0
171 / 211
Computing inner products of parametrized states
• To compute the inner product in the expression of the
energy we can notice that |ψ0 i = U(θ0 ) |ψi and that the
new states that we try will be of the form |ϕi = U(θ) |ψi for
some θ
• Then, it is easy to estimate | hψ0 |ϕi |2 by running the circuit
of the figure and computing the relative frequency of |0i
because
| hψ0 |ϕi |2 = | h0| V † U(θ0 )† U(θ)V |0i |2
where V is a unitary such that V |0i = |ψi
|0i
|0i V U(θ) U † (θ0 ) V†
|0i
172 / 211
An application of VQE in High Energy Physics
• Work by Li, Macridin, Spentzouris - Fermilab (2019)
• Rabi Hamiltonian: two-level system (TLS) coupled to a
photon mode
Ω
H = ωaa† + Z + g(a† + a)X
2
• Number-basis binary encoding: photon mode truncated to
up to 3 photons
ω Ω p
H = ωZ0 + Z1 + Z2 + g Z0 + 2X1 X2
2 2
g 3ω
+ √ X0 X1 X2 + Y0 Y1 X2 +
2 2
173 / 211
Results on simulator and Rigetti’s quantum computers
174 / 211
Part XVI
Quantum Machine Learning: a

marriage made in heaven
175 / 211
What I talk about when I talk about Quantum Machine
Learning
Image credits: Figure taken from Supervised Learning with Quantum Computers. Schuld, Petruccione (2018)
176 / 211
QBLAS: The Quantum Basic Linear Algebra
Subroutines
• A number of algorithms in Quantum Machine Learning

(QML) rely on the exponential speedup of methods such
as
• Quantum Fourier Transform
• Quantum Phase Estimation
• HHL
• We refer to these methods as Quantum Basic Linear
Algebra Subroutines (QBLAS)
• Other quantum subroutines used in QML include amplitude
amplification and quantum annealing
• Some common problems are how to load the input, how to
read the output and the size of the circuits
177 / 211
QRAM: The elephant in the room
• A Quantum Random Access Memory should allow queries
in superposition
• Several architectures have been proposed (for instance,
the “bucket brigade”) but further investigation is needed
• Loading data can become a bottleneck for many QML
algorithms
178 / 211
Translational QML and speedups
Image credits: Table taken from Biamonte, Wittek, Pancotti, Rebentrost, Wiebe, Lloyd. Nature 549, 195–202(2017)
179 / 211
QML in the times on NISQ
• Noisy Intermediate-Scale Quantum computers are

• Subjet to noise (not fault-tolerant)
• Limited in the number of qubits (50-100)
• Not fully-connected
• Despite these drawbacks, they may be useful for QML
180 / 211
Part XVII
Quantum Support Vector Machines:

exploiting the kernel trick
181 / 211
Support Vector Machines
• Support Vector Machines (SVM) are a very popular
machine learning algorithm used for data classification
• The main idea is to find a hyperplane that separates data
from two different classes with the maximum possible
margin

182 / 211
Finding the hyperplane
• We are given training data points (xi , yi ) where the xi are
vectors of real numbers and yi ∈ {1, −1}
• The problem of finding the separating hyperplane with the
biggest margin can be formulated as
1
Minimize ||w||2 subject to yi (w · xi + b) ≥ 1
2
Image credits: John Daniel, towardsdatascience.com 183 / 211

The soft-margin case
• In the “soft-margin” case we introduce a hyperparameter
C ≥ 0 and reformulate the problem as
1 X
Minimize ||w||2 + C ξi
2
i
subject to
yi (w · xi + b) ≥ 1 − ξi , ξi ≥ 0
Image credits: Rishabh Misra, towardsdatascience.com 184 / 211

Dual formulation of SVM
• An equivalent formulation of the SVM optimization problem
is this dual formulation
X 1X
Maximize αi − yi yj αi αj xi · xj
2
i i,j
subject to X
0 ≤ αi ≤ C αi yi = 0
i
• From the values αi we can recover b and w. In fact
X
w= αi yi xi
i
and to classify a point x we compute

X
w ·x +b = αi yi (xi · x) + b
i
185 / 211
Non-linear separation
• A common technique to improve classification with Support

Vector Machines is to embed the data points xi into a
higher-dimensional space using a feature map φ(xi )
Image credits: C. Moreira, “Learning To Rank Academic Experts’, Master Thesis, Technical University of Lisbon,
2011
186 / 211
The Kernel Trick
• We can easily incorporate the feature map in our
formulation of the dual problem for the SVM
X 1X
Maximize αi − yi yj αi αj φ(xi ) · φ(xj )
2
i i,j
subject to X
0 ≤ αi ≤ C αi yi = 0
i
• Again, we can obtain w as
X
w= αi yi φ(xi )
i
and to classify a point x we only need to compute

X
w ·x +b = αi yi (φ(xi ) · φ(x)) + b
i
• The function K (xi , xj ) = φ(xi ) · φ(xj ) is called “kernel”
187 / 211
Computing kernel functions with quantum computers
• In 2019, Havlı́ček, Córcoles, Temme et al. proposed using

quantum computers as kernel estimators
• Each data point xi is embedded in a Hilbert space by
means of a variational circuit Uφ (xi ) such that
Uφ (xi ) |0i = |φ(xi )i

• We know we can | φ(xj )φ(xi ) |2 by running the circuit of

the figure and computing the relative frequency of |0i
|0i
|0i Uφ (xi ) Uφ† (xj )
|0i
188 / 211
Using QSVM in High Energy Physics
189 / 211
Using QSVM in High Energy Physics (2)
• Classification of Higgs events (H → γγ and H → µµ)
Image credits: Sau Lan Wu et al.
190 / 211
Using QSVM in High Energy Physics (2)
191 / 211
Part XVIII
Quantum Neural Networks: Deep

Learning meets Quantum
Computing
192 / 211
What is a Quantum Neural Network
• Quantum Neural Networks or Variational Quantum
Classifiers are parametrized quantum circuits that can be
“trained” on data and used for classification tasks
• The most common architecture is shown in the figure
below: a feature map that embeds the data point into the
Hilbert space and a variational form that performs the
classification
Image credits: Vojtech Havlı́ček et al. https://arxiv.org/pdf/1804.11326.pdf

193 / 211
Training and classifying with a Quantum Neural
Network
• A QNN prepares a state |ψ(x, θ)i that depends on the
input data x and the parameters θ
• We measure the state and compute an average value, for
instance
f (x, θ) = hψ(x, θ)| Z1 · · · Zn |ψ(x, θ)i
• For each training example xi we have a class yi

• We choose a loss function L and we want to find θ
minimizing X
L(yi , f (x, θ))
i
• Once we obtain the optimal value θmin we can predict a
class for x using f (x, θmin )
194 / 211
Gradients and the parameter shift rule
• To obtain θmin , we can use a classical minimizer

• If we need to compute gradients of f the parameter-shift
rule is useful
• Suppose
U(θ) = e−iθH
with H a Hermitian matrix with eigenvalues ±r (r real)
• This is the case, for instance, if U is a one-qubit rotation
• Then, we have
∂f (x, θ)
= r · [f (x, θ + s) − f (x, θ − s)]
∂θ
π
where s = 4r
• This requires just two extra evaluations of the same circuit
with shifted parameters
195 / 211
Choosing feature maps and variational forms
Image credits: Sim, Johnson, Aspuru-Guzik. Adv. Quantum Tech. 2(12) (2019)
196 / 211
The power of quantum neural networks
Image credits: Amira Abbas et al. https://arxiv.org/pdf/2011.00027.pdf
197 / 211
Quantum Neural Networks in HEP
198 / 211
Quantum Neural Networks in HEP (2)
199 / 211
Image credits: Koji Terashi

200 / 211
Image credits: Koji Terashi et al. https://arxiv.org/pdf/2002.09935.pdf
201 / 211
Image credits: Koji Terashi et al. https://arxiv.org/pdf/2002.09935.pdf 202 / 211

Part XIX
Quantum Generative Adversarial

Networks: this quantum image does
not exist
203 / 211
GANs: Generative Adversarial Networks
• Generative Adversarial Networks (GANs) were introduced
by Ian Goodfellow and his collaborators in 2014
• The objective, is, given a training dataset, learning to
generate new, unseen data with the same distribution
• Impressive results have been achieved in several different
applications
Image credits: Nvidia/StyleGAN https://arxiv.org/abs/1812.04948 204 / 211

Architecture of a GAN
• Two neural networks: generator and discriminator
• The generator tries to “fool” the generator
• The discriminator tries to distinguish between real and fake
images
Image credits: Thalles Silva - www.freecodecamp.org
205 / 211
GAN training
• The generator and discriminator are trained in alternating

phases
• The discriminator tries to maximize
Ex [log D(x)] + Ez [log (1 − D(G(z)))]
• The generator can try to minimize
Ez [log (1 − D(G(z)))]
or (in practice) to maximize
Ez [log D(G(z))]
206 / 211
Quantum GANs
• A Quantum GAN replaces the generator or the
discriminator (or both) with a quantum circuit
207 / 211
Using a QGAN to load a probability distribution
208 / 211
Quantum generator in IBM’s QGAN
209 / 211
Application of QGANs in HEP: Calorimeter output
• Two-dimensional projection of 3D energy shower
Image credits: Su Yeon Chang, Sofia Vallecorsa (CERN openlab)
210 / 211
To learn more...
Image credits: https://arxiv.org/pdf/2005.08582.pdf
Image credits: Modern Physics Letters A
211 / 211

PIQC Lecture 6

Uploaded by

Copyright:

Available Formats

PIQC Lecture 6

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

PIQC Lecture 6

Uploaded by

Copyright:

Available Formats

A Practical Introduction to Quantum

Computing: From Qubits to Quantum

CERN openlab (Geneva, Switzerland) - University of Oviedo (Oviedo, Spain)

CERN - November/December 2020

Introduction: quantum computing...

Image credits: sciencenews.org

Image credits: Modified from an Instagram image by Bob MacGuffie

Image credits: IBM 5 / 211

Image credits: Created with wordclouds.com

Image credits: Erik Lucero

Image credits: Getty Images

Image credits: wikipedia.org

Image credits: Graphic by C. Bickle/Science data by Gabriel Popkin

Image credits: IBM

The Sounds of IBM: IBM Q

Image credits: IBM

• Every computation has three elements: data, operations

Image credits: Adobe Stock

One-qubit systems: one qubit to

Image credits: https://prateekvjoshi.com/ 16 / 211

• Quantum mechanics tells us that the evolution of an

• In the case of quantum circuits, this implies that the

where U † is the conjugate transpose of U.

Image credits: wikipedia.org 19 / 211

• When we have just one qubit |ψi = α |0i + β |1i, we usually

where a, b, c, d are the conjugates of complex numbers

• A state |ψi = α |0i + β |1i is transformed into

|(aα + bβ)|2 + |(cα + dβ)|2 = 1

• The X gate is defined by the (unitary) matrix

• Its action (in quantum circuit notation) is

α |0i + β |1i X β |0i + α |1i

• The Z gate is defined by the (unitary) matrix

• A common way of representing the state of a qubit is by

Image credits: wikipedia.org

• We can define the following rotation gates

• Notice that RX (π) ≡ X , RY (π) ≡ Y , RZ (π) ≡ Z ,

• For any one-qubit gate U there exist a unit vector

U ≡ RZ (α)RY (β)RZ (γ)

• The inner product of two states |ψ1 i = α1 |0i + β1 |1i and

• Notice that h0|0i = h1|1i = 1 and h0|1i = h1|0i = 0

• Orthogonal states are antipodal on the Bloch sphere

• Our very first quantum circuit!

• After applying the H gate the qubit state is

The BB84 protocol: Alice and Bob’s

Image credits: nullprogram.com

• In 1984, Charles Bennett and Gilles Brassard proposed

• Each time Bob receives a qubit, he randomly decides

• After this process, Alice and Bob talk on a classical

Image credits: A. Carrasco-Casado, V. Fernández, N. Denisenko

• Imagine Eve has access to the qubits that Alice sends to

Image credits: hikingandcoding.wordpress.com

Image credits: https://arxiv.org/pdf/1203.4940.pdf

Image credits: wikipedia.org

• The analagous of the one-time pad with quantum

• This cannot be extended to general qubits |ψi because

Image credits: The American Association for the Advancement of Science

Two-qubit systems: more than the

• Suppose we have a state

|ψi = α00 |00i + α01 |01i + α10 |10i + α11 |11i

|ψi = α00 |00i + α01 |01i + α10 |10i + α11 |11i