Quantum Computing

Dr. Andrés Gómez

Andres.gomez.tato@cesga.es
Jan. 2020
 Schedule
 Lecture 1: Introduction to Quantum Computing.
 My First Quantum Program.

 Lecture 2: Programming Quantum Algorithms

 My first Quantum Program with ProjectQ

 Lecture 3: Basic Quantum algorithms

 Lecture 4: Advanced algorithms

2
 Lecture 1
 A brief history of QC and needs.
Types of quantum computers.
 Basic concepts: qubit, tensors,
multiqubit, quantum gates,
measurement, amplitudes
 My first quantum program.
 Quantum Circuits. Width, Depth,
Quantum Volume.
 Welcome to a Dream!
Yuri Manin (1980) and Richard Feynman (1981) proposed
independently the concept of Quantum Computer

I’m here very “hot”!!

-273ºC

Source: IBM

https://en.wikipedia.org/wiki/Timeline_of_quantum_computing
4
 Welcome to a Dream!
Google

Rigetti

D-Wave
Intel

Qilimanjaro (Spain) And more in Europe, China, Australia, etc……

5
 Welcome to (my) Nightmare!(*)

Superposition and Entanglement

±
𝟏
|𝜱 > = ( 𝟎𝟎 > ± 𝟏𝟏 >)
𝟐
𝟏
|𝜳± > = ( 𝟎𝟏 > ± 𝟏𝟎 >)
𝟐
Bell States
(*) When I was a student long time ago!
6
 Quantum Technologies

NV-Defect
Ion Trap Diamond

Transmon
Photons

Quantum
Dots

Majorama

And more in the future….

7
Quantum Technologies
 Quantum Computer
 Quantum simulator [1]. Simulate a quantum system using another one,
maybe simpler, that can be controlled by the experimenter.

 Adiabatic Quantum Computer [2]. Prepares a known and easy Hamiltonian

and lets it evolve to solution.

 Topological Quantum Computer[4]. Uses topological properties.

 Continuous Variable Quantum Computer [5].

 Universal Quantum Computer [3].

[1] Reviewed in Georgescu, I. M., Ashhab, S., & Nori, F. (2014). Quantum simulation. Reviews of Modern Physics, 86(1), 153–185.
http://doi.org/10.1103/RevModPhys.86.153 arXiv:1308.6253
[2] Reviewed in Albash, T., & Lidar, D. A. (2016). Adiabatic Quantum Computing. arxiv:1611.04471
[3] Proposed in Deutsch, D. (1985). http://doi.org/10.1098/rspa.1985.0070 and
Deutsch, D. (1989). http://doi.org/10.1098/rspa.1989.0099
[4] Lahtinen V., Pachos J.K.. SciPost Phys. 3, 021 (2017) arXiv:1705.04103
[5] Lloyd S. & Braunstein, A.L. Phys.Rev.Lett. 82 (1999) 1784-1787. arXiv:quant-ph/9810082

11
 Adiabatic Quantum Computer
HB = Initial Hamiltonian, which ground state is easy to find

HP = Problem Hamiltonian, whose ground state encodes the

solution to the problem

H(s) = Combined Hamiltonial to evolve slowly:

A(s) decrease smoothly and monotonically
B(s) increase smothly and monotonically
H(s) = A(s)HB + B(s)HP

Li, R. Y., Felice, R. Di, Rohs, R., & Lidar, D. A. (2018). Quantum annealing versus classical machine learning applied to a simplified
computational biology problem. Npj Quantum Information 2018 4:1, 4(1), 14. http://doi.org/10.1038/s41534-018-0060-8

12
 A real example: Traffic Flow Optimisation
Classical Computer
Preprocess Map&GPS
QPU

Find congestions Find Alternatives Minimisation model

Solve model
Redistribute cars

Unoptimised Optimised
D-Wave Adiabatic Computer
Optimisation
Classical Computer + QPU

Neukart, F., Dollen, D. Von, Compostella, G., Seidel, C., Yarkoni, S., & Parney, B. (2017). Traffic flow optimization
using a quantum annealer. arXiv:1708.01625v2

13
 Xanadu. Continuous
Variable

 Language:
Strawberry
Fields

 Cloud service for

Research

https://www.xanadu.ai/

14
 European Quantum Flagship

 AQTION : Trapped Ions

 OpenSuperQ : Superconducting

 SQUARE: Scalable Rare Earth Ion Quantum Computing Nodes

 MicroQC: Microwave driven ion trap quantum computing

http://qt.eu
15
 Quantum Networks

http://english.cas.cn/newsroom/news/201709/t20170928_183577.shtml
16
 Google Quantum “Supremacy”

Arute F, Arya K, Babbush R, Bacon D, Bardin JC, Barends R, et al. Quantum supremacy using a
programmable superconducting processor. Nature. 2019;574:505.
Google Quantum “Supremacy”
 Lecture 1
 A brief history of QC and needs.
Types of quantum computers.
 Basic concepts: qubit,
tensors, multiqubit, quantum
gates, measurement,
amplitudes
 My first quantum program.
 Quantum Circuits. Width, Depth,
Quantum Volume.
 DiVincenzo’s Criteria

1. A scalable physical system with well characterized qubits.

2. The ability to initialize the state of the qubits to a simple fiducial
state, such as |000….000>
3. Long relevant decoherence times, much longer than the gate
operation time.
4. A “universal” set of quantum gates.
5. A qubit-specific measurement capability.

D. DiVincenzo (2000). “The Physical Implementation of Quantum Computation“, arXiv:quant-ph/0002077

20
 What do you need (today)?

Complex numbers

Matrix multiplication

Understand TENSOR products

Understand measurement and probabilities

Imagination
21
 BIT, QUBIT AND SUPERPOSITION

Classical Computer Business Card

BIT: A “classical” physical system with TWO states

0 OR 1
What 0 or 1 means is a convention
Information is codified as a list of BITs
BIT can be transformed from 0 to 1 and vice versa
BITs can be operated with logical gates (OR,XOR,AND…)
One BIT can be cloned
BITs can be stored
BITs can have a long life
BITs move through logical gates
22
 BIT, QUBIT AND SUPERPOSITION
Quantum Computer Business Card
QuBIT: A “Quantum” physical system which yields
one of TWO states when is measured

0 OR 1
What 0 or 1 means is a convention*
Information is codified in several ways
QuBIT can be transformed from 0 to 1 and vice versa
QuBITs can be operated with UNITARY gates
QuBITs cannot be cloned (no-clone theorem)
QuBITs cannot be stored (yet)
QuBITs cannot have a long life (yet)
Usually, QuBITs are quiet
23
 Quantum Technologies

Krantz P, Kjaergaard M, Yan F, Orlando TP, Gustavsson S, Oliver WD. A Quantum

Engineer’s Guide to Superconducting Qubits. Arxiv: 1904.06560
 Our current nightmare!

NOISE
Noisy Intermediate-Scale Quantum” (NISQ)

https://medium.com/@pchojecki/quantum-advantage-b3458646bd9
Parametric Quantum Circuit
Learning

Send Circuit

Return Shots
“QPU” CPU
Parametric Quantum Circuit
Learning
Parametric Quantum Circuit
Learning
 Parametric Quantum Circuit
Learning
SIMULATING
WITH NOISE
FEW SHOTS
 Parametric Quantum Circuit
Learning
IBMQ_VIGO
Nov. 17th, 2019

Source: IBM© Nov. 24th, 2019

N=3, D=3
Parametric Quantum Circuit
Learning
 Algorithms with shallow
circuits
• QVE: Quantum Variational Eigensolver:
https://arxiv.org/abs/1304.3061

• QAOA: Quantum Approximate Optimization Algorithm.

http://arxiv.org/abs/1411.4028

• Variational Quantum Factoring:

https://arxiv.org/abs/1808.08927

• Quantum Machine Learning:

• Quantum Support Vector Machine
• Quantum Principal Component Analysis
• Quantum Variational Autoencoder,
• Etc.
 Quantum Variational Eigensolver

QPU CPU

Figure source: Wang, D., Higgott, O., & Brierley, S. (n.d.). A Generalised
Variational Quantum Eigensolver.
 Quantum Machine
Learning?
“Despite a number of promising results, the theoretical evidence presented in
the current literature does not yet allow us to conclude that quantum techniques
can obtain an exponential advantage in a realistic learning setting”

Ciliberto et.al. “Quantum machine learning: a classical perspective”

http://dx.doi.org/10.1098/rspa.2017.0551

So:

A lot of research to do!!!

34
www.inl.int
 Complex Numbers

If 𝑖2 = −1, a complex number is defined by:

c=𝑎 + 𝑏 ∗ 𝑖, with 𝑎, 𝑏 ∈ ℝ, 𝑐 ∈ ℂ

Complex conjugate: 𝑐 = 𝑎 − 𝑏 ∗ 𝑖
2
Modulus: 𝑐 = 𝑐𝑐 = (𝑎 + 𝑏 ∗ 𝑖)(𝑎 − 𝑏 ∗ 𝑖) = 𝑎2 + 𝑏 2

Polar form: c = 𝑐 𝑐𝑜𝑠𝜃 + 𝑐 𝑠𝑖𝑛𝜃 𝑖 = 𝑐 𝑒 𝑖𝜃

35
www.inl.int
 QUBIT
Complex numbers
1 Superposition
|0 > =
0
|𝜙 > = 𝛼 0 > + 𝛽 1 >
0
|1 > = 2 2
1 𝛼 + 𝛽 =1

2
𝛼 𝑃𝑟𝑜𝑏𝑎𝑏𝑖𝑙𝑖𝑡𝑦 𝑑𝑒𝑛𝑠𝑖𝑡𝑦
𝐴𝑚𝑝𝑙𝑖𝑡𝑢𝑑𝑒 𝛼 = 𝛼 𝑒 𝑖𝜑
𝜑 Phase

36
 QUBIT
𝛼 𝛾
|𝜙 > = 𝛼 0 > + 𝛽 1 >= 𝛽 |𝜓 > = 𝛾 0 > + 𝛿 1 >=
𝛿

< 𝜙 = 𝛼 < 0 + 𝛽 < 1| = 𝛼 𝛽

2 2 < 𝜓|𝜙 > = 𝛼 𝛾 + 𝛽 𝛿

< 𝜙|𝜙 > = 𝛼 + 𝛽

Measurement of |𝜙 > in standard basis (|0>, |1>) :

|0> with probability 𝛼 2 . State after measurement |0>

or
|1> with probability 𝛽 2 . State after measurement |1>

37
 Bloch’s Sphere
𝜃 𝜃 𝑖𝜑
|𝜓 > = cos( )|0 > + sin( ) 𝑒 |1 >
2 2
z
|𝟎 >
𝜋 |0 > + |1 >
𝜃= , 𝜑 = 0, | +> =
2 2

| −> 𝜋 |0 > −|1 >

𝜃 𝜃= , 𝜑 = 𝜋, |− > =
|𝜓 > 2 2
|𝒊 >
|−𝒊> y
𝜋 𝜋 |0 > +𝑖|1 >
𝜑 𝜃= , 𝜑 = , |𝑖 > =
2 2 2
| +>
x 𝜋 3𝜋 |0 > −𝑖|1 >
𝜃= ,𝜑 = ,| −𝑖 >=
2 2 2
|𝟏 >

Hint: 𝑒 𝑖𝜑 = cos(𝜑)+i sin(𝜑)

38
 One-Qubit Transformations
𝛼
|𝜙 > = 𝛼 0 > + 𝛽 1 >= 𝛽

′ 𝑎11 𝑎12 𝛼
 Transform vector space in itself |𝜙 > = U |𝜙 > = 𝑎 𝑎22 𝛽
21

 Unit lengh vectors must go to unit lenght vectors: < 𝜓 𝑈 † 𝑈 𝜙 > =< 𝜓|𝜙 >⇒ 𝑈 † 𝑈=I

 Reversible

 Geometrically, they are rotations of the complex vector space associated to |𝜙 >

𝑁𝑜𝑡𝑒: 𝑈 † = 𝑈 𝑇

39
 One-Qubit Transformations
 Phase shift 𝐾(𝛿) = 𝑒 𝑖𝛿 𝐼

cos(𝛽) sin(𝛽)
 Rotation, 𝑅(𝛽) =
−sin(𝛽) 𝑐𝑜𝑠(𝛽)
𝑖𝛼
 Phase rotation, 𝑇(𝛼) = 𝑒 0
0 𝑒 −𝑖𝛼

 Any other Qubit unitary transformation can be written as:

𝑒 𝑖(𝛿+𝛼+𝛾) cos 𝛽 𝑒 𝑖(𝛿+𝛼−𝛾) sin 𝛽

𝐾 𝛿 𝑇 𝛼 𝑅 𝛽 𝑇 𝛾 =
− 𝑒 𝑖(𝛿−𝛼+𝛾) sin 𝛽 𝑒 𝑖(𝛿−𝛼−𝛾) cos 𝛽

Source: Eleanor G. Rieffel.Quantum Computing: A Gentle Introduction

40
 One-Qubit Transformations

 Phase shift 𝐾(𝛿) = 𝑒 𝑖𝛿 𝐼

𝜃 𝜃
cos −𝑖 sin 𝜃 𝜃
2 2
 Rotation around 𝑥, 𝑅𝑥 𝜃 ≡ 𝑒 −𝑖𝜃𝑋 = 𝜃 𝜃
= cos 𝐼 − 𝑖 𝑠𝑖𝑛 𝑋
2 2
−𝑖 sin cos
2 2

𝜃 𝜃
cos(2 ) −sin(2 )
 Rotation around 𝑦, 𝑅𝑦 𝜃 ≡ 𝑒 −𝑖𝜃𝑌 = 𝜃 𝜃
sin(2) 𝑐𝑜𝑠(2)

−𝑖𝜃/2
 Phase rotation, Rotation around 𝑧, 𝑅𝑧 𝜃 ≡ 𝑒 −𝑖𝜃𝑍 = 𝑒 0
0 𝑒 𝑖𝜃/2

 Any other QuBit unitary transformation can be written as:

𝑈 = 𝐾(𝛿)𝑅𝑧 𝛾 𝑅𝑦 𝛽 𝑅𝑧 𝛼

Source: Nielsen & Chuang, Quantum Computation And Quantum Information

42
 One-Qubit Transformations
 Pauli Gates
0 1
𝑋= , bit-flip or NOT.
1 0
0 −𝑖
 Y=
𝑖 0
1 0
 Z=
0 −1

 IBM group
 Cliffort group
1 0
1 1 1 𝑈1 𝜆 =
 𝐻𝑎𝑑𝑎𝑚𝑎𝑟𝑑, 𝐻 = 0 𝑒 𝑖𝜆
2 1 −1
1 0 1 −𝑒 𝑖𝜆
 𝑃ℎ𝑎𝑠𝑒, 𝑆 = 𝑈2 𝜙, 𝜆 = 1
0 𝑖
2 𝑒 𝑖𝜙 𝑒 𝑖(𝜙+𝜆)
𝜋 1 0
 ,𝑇 = 𝜋
𝑖4
8 0 𝑒 𝜃 𝜃
cos(2 ) −sin(2 )𝑒 𝑖𝜆
† 𝑈3 (𝜃, 𝜙, 𝜆) =
Hint:𝑈 = 𝑈 𝑇 𝜃
sin(2 )𝑒 𝑖𝜙
𝜃
cos(2 )𝑒 𝑖(𝜙+𝜆)

44
 Expectation Value of U

< 𝑈 >≡< 𝜑|𝑈|𝜑 >

Example:

1 0 1
< 0 𝑍 0 >= 1 0 =1
0 −1 0

1 0 0
< 1 𝑍 1 >= 0 1 = −1
0 −1 1

𝜑 > = 𝑎 0 > +𝑏|1 >

2 2
< 𝜑 𝑍 𝜑 > = 𝑎 < 0 +𝑏 < 1 𝑍 𝑎 0 > +𝑏 1 > = 𝑎 <0𝑍0>+𝑏 <1𝑍1>
Exercise with 1 QuBit

OPEN QUIRK.HTML
 Multi-Qubits

TENSOR PRODUCT
𝑎1
|𝑎 > = 𝑎 𝑏1 𝑎1 𝑏1
2 𝑎1 𝑏1 𝑎1
𝑏2 𝑎 𝑏
𝑎2 ⨂ = = 1 2
𝑏1 𝑏2 𝑏 𝑎2 𝑏1
𝑎2 1
|𝑏 > = 𝑏2 𝑎2 𝑏2
𝑏2

47
 Multi-Qubits
TENSOR PRODUCT
1
|0 > ⨂|0 >= |00> = 0 = |0>
0
0

1 0
|0 > =
0 |1 > ⨂|0 >= |10> = 0 = |2>
1
0
0
0 |0 > ⨂|1 >= |01> = 1 = |1>
|1 > =
1 0
0
0
|1 > ⨂|1 >= |11> = 0 = |3>
0
1

48
 Superposition Multi-Qubits

For 2 QuBits:
|𝝍 > = 𝜶 𝟎𝟎 > +𝜷 𝟎𝟏 > +𝜸 𝟏𝟎 > +𝜹 𝟏𝟏 >

|𝝍 > = 𝜶 𝟎 > +𝜷 𝟏 > +𝜸 𝟐 > +𝜹 𝟑 >

For N QuBits:
𝟐𝑵 −𝟏

|𝝍 > = 𝝀𝒊 |𝒊 >
𝒊=𝟎

Pay Attention. You can map classical information to:

• |𝑖 >, example Shor ′ s algorithm
and/or
• 𝜆𝑖 , example HHL algorithm

49
 Entanglement Multi-Qubits

When you cannot write a state as a product of single states

𝟏
|𝜱± > = 𝟐
𝟎𝟎 > ± 𝟏𝟏 > ≠ (𝜶 |𝟎 > +𝜷|𝟏 >) ⨂ (𝜸 𝟎 > + 𝜹 𝟏 > )

AND NOW, YOU HAVE WONDERFUL

THINGS AS TELEPORTATION!

13/09/2017 50
 Multi-Qubit Transformations
𝑈11 𝑈12 𝑉11 𝑉12
𝐿𝑒𝑡 𝑈1 = on qubit 1 𝐿𝑒𝑡 𝑉2 = on qubit 2
𝑈21 𝑈21 𝑉21 𝑉21

𝑉11 𝑉12 𝑉11 𝑉12

𝑈11 𝑈12
𝑉21 𝑉21 𝑉21 𝑉21
𝑈1 ⊗ 𝑉2 =
𝑉11 𝑉12 𝑉11 𝑉12
𝑈21 𝑈22
𝑉21 𝑉21 𝑉21 𝑉21

𝑈11 𝑉11 𝑈11 𝑉12 𝑈12 𝑉11 𝑈12 𝑉12

𝑈 𝑉 𝑈11 𝑉22 𝑈12 𝑉21 𝑈12 𝑉22
𝑈1 ⊗ 𝑉2 = 11 21
𝑈21 𝑉11 𝑈21 𝑉12 𝑈22 𝑉11 𝑈22 𝑉12
𝑈21 𝑉21 𝑈21 𝑉22 𝑈22 𝑉21 𝑈22 𝑉22

51
 Multi-Qubit Transformations

Example: Apply X gate on second qubii. Let first qubit unchanged

0 1 0 1
1 0
1 0 1 0
𝐼⊗𝑋 =
0 1 0 1
0 1
1 0 1 0

0 1 0 0
𝐼⊗𝑋 = 1 0 0 0
0 0 0 1
0 0 1 0

13/09/2017 52
 Controled Gates
Apply one gate on one qubit, depending on the values of other qubits

𝐶𝑁𝑂𝑇 = 0 >< 0 ⊗ 𝐼 + 1 >< 1 ⊗ 𝑋

1 0 0 0
𝐶𝑁𝑂𝑇|00 > = |00 >
𝐶𝑁𝑂𝑇 = 0 1 0 0
0 0 0 1
𝐶𝑁𝑂𝑇|01 > = |01 >
0 0 1 0
𝐶𝑁𝑂𝑇|10 > = |11 >

𝐶𝑁𝑂𝑇|11 > = |10 >

53
Measurement
Classical Bit

QuBit

54
 Quantum Circuit
Depth

Width

13/09/2017 55
MY FIRST QUANTUM PROGRAM:
Superdense Coding
OPEN QUIRK.HTML
 My First Quantum Program
 Using Quirk. Launch quirk.html. QUIRK does not
need measurement. Remember to add it in
your real circuit.

 Apply a Hadamard Gate (H) on the first qubit

 Apply a second H to the same qubit. Result?

 Remove Second H and apply a CNOT on a second

qubit.
 Result: an entangled system (Bell’s)

13/09/2017 57
 Superdense Coding
 Transmit two classical bits with a single qubit

A. Bobs generates a Bell’s state

B. Bob sends one qubit to Alice. Bob keeps the
second.
C. Alice applies a single-qubit gate to her qubit
to encode 2 bits:
• 01 -> X
• 10 -> Z
• 11 -> Y
• 00 -> I

D. Alice returns her qubit to Bob.

E. Bob uncomputes entanglement (applies the
gates in reverse order)
F. Bob measures both qubits.

58
 Superdense Coding

|00> |01>

|10> |11>

59
Caution!!!

60
 Exercise 2: IBM Quantum Experience
CONNECT TO: HTTPS://QUANTUM-COMPUTING.IBM.COM/
 Quantum Volume
 Width: The number of physical qubits;

 Depth: The number of gates that can be applied before errors make
the device behave essentially classically;

 Topology: The connectivity of the device;

 Gate Parallelism: The number of operations that can be run in

parallel

62
 TOPOLOGY

https://medium.com/rigetti/the-rigetti-128-qubit-chip-
and-what-it-means-for-quantum-df757d1b71ea

https://github.com/Qiskit/ibmq-device-
information/blob/master/backends/melbourne
 Quantum Volume
 Effective error rate εeff: specifying how
well a device can implement arbitrary
pairwise interactions between qubits

 n is the number of qubits of the

Computer

 n’ number of qubits used by the

algorithm
1
 Depth 𝑑 ≃
𝑛 𝜀𝑒𝑓𝑓

 Quantum Volume
2 Source: IBM, 2019
′ 1
𝑉𝑄 = max 𝑚𝑖𝑛 𝑛 , 𝑛′ 𝜀 ′)
′
𝑛 <𝑛 𝑒𝑓𝑓 (𝑛

64
 Classical Resources
1 qubit 2 qubits 3 qubits N qubits
|0> |00> = |0> |000> = |0> |0….0> = |0>
|1> |01> = |1> |001> = |1> |0….1> = |1>
|10> = |2> |010> = |2>
|11> = |3> |011> = |3>
|100> = |4>
|101> = |5>
|110> = |6>
|111> = |7>
|1…..1> = |2N-1>
2 4 8 𝟐𝑵
𝜶 |𝟎 > + 𝜷 |𝟏 > 𝟑 𝟕 𝟐𝑵−𝟏

𝜶𝒏 |𝒏 > 𝜶𝒏 |𝒏 > 𝜶𝒏 |𝒏 >

𝒏=𝟎 𝒏=𝟎 𝒏=𝟎
2 * complex= 4*2*8=64 bytes 8*2*8=128 𝟐𝑵 ∗ 𝟐𝟒 = 𝟐𝑵+𝟒
2x2x8=32 bytes bytes
65
 How many states?

Asimov calculated the number of nucleons+electrons in

the Universe as ∼1079
∼ 10.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000

Having a QPU with 270 qubits, one can store in the

amplitudes: ∼1081 FPs.

Year 2025: ∼170ZB/year ∼ 1023 bytes/year

75 qubits: ∼ 3·1023 FPs = ∼ 24 years!!!!

 Classical Resources
qubits RAM
1 32 bytes + memory for gates
2 64 bytes + memory for gates
3 128 bytes + memory for gates
4 256 bytes + memory for gates
8 4 kbytes + memory for gates
16 1 Mbytes + memory for gates
32 64 Gbytes + memory for gates
36 1TB + …..
38 4TB (Limit CESGA FT2 FAT node
….)
45 0,5PB [1]
64 512 ExaBytes!!!

THIS IS ONLY TRUE IF YOU NEED ALL POSSIBLE STATES!

[1] Häner, T., & Steiger, D. S. (2017). 0.5 Petabyte Simulation of a 45-Qubit Quantum Circuit. Arxiv:1704.01127
67