MULT20015 Lecture 1 2021 v1
MULT20015 Elements of Quantum Computing
Lecture 1
Welcome to MULT20015
“Elements of Quantum Computing”
University of Melbourne
Staff:
Physics/Maths: Prof. Lloyd Hollenberg, Dr. Charles Hill
Computer Science: Dr. Muhammad Usman, Dr. Casey Myers, Prof. Udaya Parampalli
Finance: Dr. Nitin Yadav, Prof. Carsten Murawski
MULT20015 Lecture 1, 2021
MULT20015 Elements of Quantum Computing
Lecture 1
MULT20015 Elements of Quantum Computing
In this subject we will cover:
• The basic concepts of quantum information and quantum logic
• Programming quantum computers to perform computational tasks
• How quantum computers can be applied to problems in the context of mathematics,
computing and finance
• The status of current quantum computer technology
Teaching system: UoM Quantum User Interface (QUI)
• Prior to Practice Class 1: access and sign in at QUIspace.org
(using your unimelb email address)
• In Practice Class: registered users -> expanded capabilities
This subject is a relatively gentle introduction to quantum computing and applications
for students from a range of backgrounds. NB – new in 2020 -> “MULT20015” 2021
The aim is to give you an overview of quantum computing (and some related topics)
-> position for further studies in quantum computing
(e.g. Masters: MULT90063 Intro to QC, COMP90084 Quantum Software Fundamentals)
MULT20015 Elements of Quantum Computing
Lecture 1
MULT20015: subject summary 2021
24 Lectures:
Wednesday 11am-12pm: PAR-Physics South-L105 (Hercus Theatre)
Thursday 11am-12pm: PAR-Physics South-L105 (Hercus Theatre)
12 Computer-based practice class tutorials (commencing in week 1):
Baker Computer Lab, Room 661, Level 6 David Caro Building (Physics)
All practice classes are scheduled on Thursday (see LMS)
Assessment (see Subject Outline on LMS for timing):
2 assignments (20%+30%), 2 hour exam (50%)
Staff (see LMS for contact details):
Team Physics/Maths: Prof. Lloyd Hollenberg, Dr. Charles Hill
Team Computer Science: Dr. Muhammad Usman, Dr. Casey Myers, Prof. Udaya Parampalli
Team Finance: Dr. Nitin Yadav, Prof. Carsten Murawski
Head tutor: Mr. Spiro Gicev
Suggested reading:
E. Rieffel and W. Polak – “Quantum Computing: A Gentle Introduction”
IBM Quantum Experience – on-line textbook (qiskit.org/textbook)
LMS: Access lecture notes, practice class notes, assignments
MULT20015 Elements of Quantum Computing
Lecture 1
Subject outline
Lecture topics (by week)
1 – Introduction to quantum computing and maths basics
2 – Single qubit representations and logic operations
3 – Two qubit states and logic gates
4 – Multi-qubit states and quantum arithmetic
5 – Basic quantum algorithms
6 – Period finding, cryptography and quantum factoring
7 – Shor’s algorithm, post-quantum crypto, quantum key distribution
8 – Quantum search algorithms
9 – Grover search applications, optimisation problems
10 – Solving optimisation problems on quantum computers
11 – Applications in quantum machine learning
12 – Real quantum computer devices
Assignment schedule:
#1: Hand out in Week 2
#2: Hand out in Week 8
MULT20015 Elements of Quantum Computing
Lecture 1
Week 1
Lecture 1
1.1 A very brief overview of computing
1.2 The quantum world and quantum computing
Lecture 2
2.1 The mathematics of quantum states
2.2 Complex numbers and quantum amplitudes
2.3 Basic linear algebra: ket and matrix notation
2.4 State representation in the QUI
Tutorial 1
The Quantum User Interface (QUI), lecture review exercises
MULT20015 Elements of Quantum Computing
Lecture 1
1.1 A very brief overview of computing
MULT20015
Lecture 1
MULT20015 Elements of Quantum Computing
Lecture 1
The limits of conventional computing
Quantum computers based on the laws of quantum mechanics circumvent
limitations of classical information processing
Conventional computers: some problems are just too hard to solve on even the biggest
supercomputers -> More powerful CPUs?
Moore’s Law – since 1960’s transistor size halves every 1.5 years
But, as transistor size <10nm we’re getting close to the limit (atoms are about 1nm or less)… [also, they require increasing energy density to operate classically] The end-of-Moore’s law signals new computer technology is needed… Many people believe quantum computers are the evolutionary step. MULT20015 Elements of Quantum Computing Lecture 1 The limits of conventional computing Quantum computers based on the laws of quantum mechanics circumvent limitations of classical information processing Conventional computers: some problems are just too hard to solve on even the biggest supercomputers -> More powerful CPUs?
Moore’s Law – since 1960’s transistor size halves every 1.5 years
But, as transistor size <10nm we’re getting close to the limit (atoms are about 1nm or less)… [also, they require increasing energy density to operate classically] The end-of-Moore’s law signals new computer technology is needed… Many people believe quantum computers are the evolutionary step. MULT20015 Elements of Quantum Computing Lecture 1 1.2 “Classical” computing: bits and binaries From classical bits ® we can construct binary numbers 0000 or 1010 etc A classical bit (e.g. in an Intel chip) is like a switch with two values: 22 nm Tri-Gate Transistor Gates 8 Fins on “1” off “0” Intel.com Only “0” or “1” at a time in any given physical representation (transistor) Wait, what’s a binary number again? Conventional computers obey the laws of “classical physics” (pre-quantum) -> we call anything not quantum “classical”…i.e. “classical computers” vs. “quantum computers”
MULT20015 Elements of Quantum Computing
Lecture 1
Numbers…we need to re-learn some things
If you are like most people, you never stop to think about how numbers actually work…
Consider a humble speed sign: 110
c. 100,000 BC
CX
Roman
1×102 + 1×101 + 0x100
= one of 102 plus one of 101 plus zero of 100
Our number convention (left) is very efficient…
It is also decimal – based on powers of 10. What does this mean?
We know instinctively that “110” is shorthand for:
1×100 + 1×10 + 0x1 = “one hundred and one ten and no ones”
102 = 100
101 = 10
100 = 1
110
base 10
”one hundred
and ten”
110
base 2
”six”
If we remember we’re in base 10, we write it as:
But, in base 2 the number “110” is actually “six”, i.e.
MULT20015 Elements of Quantum Computing
Lecture 1
Decimals and binaries
Let’s break that down lest we get confused driving a car:
110 = 1×102 + 1×101 + 0x100 = one of 102 plus one of 101 plus zero of 100
= 100 + 10 + 0 = 110 as we normally read it
102 = 100
101 = 10
100 = 1110
base 10
”one hundred
and ten”
110
base 2
”six”
110 = 1×22 + 1×21 + 0x20 = one of 22 plus one of 21 plus zero of 20
= 4 + 2 + 0 = 6
22 = 4
21 = 2
20 = 1
Hence: “There are 10 types of people in this world…
– those who understand binary numbers…and those who don’t”
Decimal
Binary
MULT20015 Elements of Quantum Computing
Lecture 1
Some examples
57 = 5×101 + 7×100 = five of 101 plus seven of 100 = 50 + 7 = 57
103 = 1000
102 = 100
101 = 10
100 = 1
57Base 10
“decimal” Note: the numbers in blue run over base 10 “digits” i.e. 0-9
Roman
57 = L + VII = fifty plus two after five = 50 + 7 = 57 100 = C50 = L
4 = IV
1 = I
LVII
Base 2
“binary”
111001 = 1×25 + 1×24 + 1×23 + 0x22 + 0x21 + 1×20
= 1×32 + 1×16 + 1×8 + 0x4 + 0x2 + 1×1
= 32 + 16 + 8 + 0 + 0 + 1 = 57
25 = 32
24 = 16
23 = 8
22 = 4
21 = 2
20 = 1
Note: the numbers in blue run over base 2 “bits” i.e. 0-1
111001
10’s
1’s
57
111001
2’s
1’s
4’s
8’s
16’s
32’s
The point: as computers naturally use binary numbers, so do
quantum computers
® need to be familiar with bits and binary and decimals (see table)
Decimal Binary Decimal Binary
0 000 4 100
1 001 5 101
2 010 6 110
3 011 7 111
Note: incredibly cumbersome
MULT20015 Elements of Quantum Computing
Lecture 1
1.2 “Classical” computing: bits and binaries
Continuing:
From classical bits ® we can construct binary numbers 0000 or 1010 etc
One binary number at one time in the physical representation
A classical bit (e.g. in an Intel chip) is like a switch with two values:
22 nm Tri-Gate Transistor
Gates
8
Fins
on “1”
off “0”
Intel.com
Only “0” or “1” at a time in any given
physical representation (transistor)
Quantum information is very different…
Conventional computers obey the laws of “classical physics” (pre-quantum)
-> we call anything not quantum “classical”…i.e. “classical computers” vs. “quantum computers”
MULT20015 Elements of Quantum Computing
Lecture 1
1.2 The quantum world and quantum computing
MULT20015
Lecture 1
MULT20015 Elements of Quantum Computing
Lecture 1
The Quantum World
Y
quantum mechanics
nature of the physical world
nature of “reality”
Some meta-physics…
Advances in experimental
and theoretical
quantum science:
® quantum sensing
quantum communication
quantum computing
…
MULT20015 Elements of Quantum Computing
Lecture 1
Quantum superposition:
Systems can be in indeterminate (multiple) states prior to measurement
Quantum entanglement:
Systems can be linked such that measurement of one part correlates to
that of another part
Quantum measurement:
Result of any given measurement a-priori unknown, system “collapses” to
an outcome
Key concepts for quantum computing
We’ll go through each of these systematically…
MULT20015 Elements of Quantum Computing
Lecture 1
Planck (1900): postulated that energy is quantised
Bohr (1913): constructed a simple “quantised” model of the hydrogen atom
2
2
0
2
2
1
42 n
em
En ÷÷
ø
ö
çç
è
æ
-=
ep!
…
n = 3
n = 2
n = 1
…
n = ¥
energy levels
ground state ®
excited state ®
proton
electron
|0i
|1i
Consider lowest two levels
Simply re-label states to a bit
notation
® quantum bit, or “qubit”
(Not to be confused with “cubit”!)
Start with a (semi) familiar concept – the atom
MULT20015 Elements of Quantum Computing
Lecture 1
|0ñ “and” |1ñ
|0ñ
state collapse ® random
outcome
quantum superposition
measurement/observation
|1ñ
|0ñY|0i
|1i
Quantum superposition and measurement
Bubble: Brocken commons.wikimedia.org
Bursting bubble: wallpaperswide.com
One electron in quantum
superposition.
MULT20015 Elements of Quantum Computing
Lecture 1
|0ñ “and” |1ñ
|1ñ
state collapse ® random
outcome
quantum superposition
measurement/observation
|1ñ
|0ñY|0i
|1i
Quantum superposition and measurement
One electron in quantum
superposition.
Bubble: Brocken commons.wikimedia.org
Bursting bubble: wallpaperswide.com
MULT20015 Elements of Quantum Computing
Lecture 1
Quantum entanglement
Measurement outcomes for e.g. qubit-1 are random, but result of qubit-2 depends on qubit-1
outcome ® the qubits are somehow connected…
|00ñ
|10ñ
|01ñ
|11ñ
Y
Imagine two qubits. We can prepare two distinct classes of overall
state:
a) Separable state: independent quantum superpositions
qubit-1 ~ |0ñ + |1ñ
qubit-2 ~ |0ñ + |1ñ
Or we write (|0ñ + |1ñ) x (|0ñ + |1ñ) ® |0ñ |0ñ + |0ñ |1ñ + |1ñ |0ñ + |1ñ |1ñ ® |00ñ + |01ñ + |10ñ + |11ñ
Measurement outcomes for each qubit: random and independent
b) An entangled state: e.g. in above notation |0ñ |1ñ + |1ñ |0ñ
Measurement on qubit-1:
qubit-1 = |0ñ (random) ® qubit-2 = |1ñ
qubit-1 = |1ñ (random) ® qubit-2 = |0ñ
(NB for later: ignoring
normalisation for now)
(and vice-versa if we first
measured qubit-2)
MULT20015 Elements of Quantum Computing
Lecture 1
Multi qubits – state counting
1 qubit:
|0ñ, |1ñ
2 qubits:
|0ñ, |1ñ |0ñ, |1ñ
Binary combinations
|00ñ, |01ñ, |10ñ, |11ñ
|0ñ, |1ñ
3 qubits:
|0ñ, |1ñ |0ñ, |1ñ
|000ñ, |001ñ, |010ñ, |011ñ
|100ñ, |101ñ, |110ñ, |111ñ
|0ñ, |1ñ
4 qubits:
|0ñ, |1ñ |0ñ, |1ñ |0ñ, |1ñ |0ñ, |1ñ
|0000ñ, |0001ñ, |0010ñ, |0011ñ
|0100ñ, |0101ñ, |0110ñ, |0111ñ
|1000ñ, |1001ñ, |1010ñ, |1011ñ
|1100ñ, |1101ñ, |1110ñ, |1111ñ
binary representation of decimals 0 to 1
binary representation of decimals 0 to 3
binary representation of decimals 0 to 7
binary representation of decimals 0 to 15
MULT20015 Elements of Quantum Computing
Lecture 1
Multiple qubits and quantum processing
Independent quantum superpositions ® superposition over
N-bit binaries |000…0ñ,…, |111…1ñ (and there are 2N of these)
Basic representation of binaries as quantum information:
Quantum computation: qubits interact to create
complex superpositions and entangled states
N qubits …
101100
10
10101110
00101110
11100001
11101010
101100
10
10101110
00101110
11100001
11101010
Not very useful…measurement of qubits collapses to one random N-bit string
11
10
00
01
00
10
00
10
10
11
00
11
binaries time
probability
…
Bubble: Brocken commons.wikimedia.org
QC Immersion Project
Quantum information processing
|0000ñ
|0001ñ
|0010ñ
|0011ñ
|0100ñ
|1010ñ
|0110ñ
|0111ñ
|1000ñ
|1001ñ
|0101ñ
|1011ñ
|1100ñ
|1101ñ
|1110ñ
|1111ñ
01
01 11
10
10
11
binaries time
probability
|0000ñ
|0001ñ
|0010ñ
|0011ñ
|0100ñ
|0101ñ
|0110ñ
|0111ñ
|1000ñ
|1001ñ|1010ñ
|1011ñ
|1100ñ
|1101ñ
|1110ñ
|1111ñ
11
00
00
10
11
11
• logic gates between qubits perform mathematical operations on binary data
• complex entangled states created ® binary data are quantum “linked”
• quantum interference amplifies probability of desired output (answer)
start
quantum program
finish
Bubble: Brocken commons.wikimedia.org
Bursting bubble: wallpaperswide.com
CNOT
H
Digital quantum computing:
|0101ñ
read-out
MULT20015 Elements of Quantum Computing
Lecture 1
co
m
pu
ta
tio
na
l t
im
e
problem size
polynomial
speed-up
• Intermediate quantum computers (IQC)
– medium-scale system (10 ~1000 qubits)
– simplified control and error correction
– potentially polynomial speed-up (e.g. √CPU)
– optimisation, machine learning, chemistry,…
– pathway to full-scale universal QC…
(NISQ = “Noisy Intermediate Scale Quantum”)
problem size
exponential
speed-up
co
m
pu
ta
tio
na
l t
im
e
problem size
• Full universal quantum computers (UQC)
– large-scale system (>>1000 qubits)
– high redundancy for quantum error correction
– potentially exponential speed-up for some
problems (e.g. Shor’s factoring algorithm)
– large class of problems: financial, data-base
analysis, security, bio-molecular simulation
– polynomial to exponential speed-up
Types of quantum computers
Broadly, there are two classes of digital quantum computers*:
*c/f “analogue” machines for Adiabatic Quantum Computing, such as D-Wave systems
MULT20015 Elements of Quantum Computing
Lecture 1
Meanwhile: quantum computers emerge
2019: “System One” IBM state-of-the-art
Stand-alone QC systems (20 ® 65 qubits),
fully programmable
2016: IBM provides cloud access to QC hardware, programming interface
2017: IBM Network Q
2019: Quantum supremacy
Other players: Rigetti, Google, IonQ, Microsoft, Intel, D-Wave,…
Google.com: quantum circuit sampler machine
2019: Google achieves “Quantum Supremacy”
53 qubits vs. HPC for random circuits
200 sec (QC) vs. 10,000 yrs (HPC)
[Nature Oct 23 2019]
2020: Hefei photonic QC
100-qubit equiv. vs. HPC for Boson Sampling
200 sec (QC) vs. 600 m years
[Science Dec 03 2020]
Big goal: “Quantum advantage”
i.e. beat HPC on a useful problem (if/when?)
IBM.com
IBM Quantum Network Hub
at the University of Melbourne
MULT20015 Elements of Quantum Computing
Lecture 1
Quantum
advantage
100-1000 qubits?
In the meantime, the era of quantum
software and app development has begun…
Google: “Quantum Supremacy”,
Hefei: Boson Sampling problem
Theory: large-scale
simulations,
e.g. quantum factoring,
60 qubits
(exa ® tera bytes)*
*A. Dang et al,
arXiv:1712.07311
Universal QC:
(millions of qubits)
poly to exponential
speed-up on
various problems
increasing # qubits and quality (error rates)
Hardware race: IBM, Google, Intel,
D-Wave, Rigetti, Microsoft, SQC,…
Timeline and state of the art
DWave: 2000 “qubits”
-> analogue QC
DWave.com IBM.com
IBM-Q: 65 qubits
-> digital QC
2020 2021 2022 2023
433
127
2019
53
2024 2025 2026
65
1,121
IBM QC roadmap [1]
QC = 100 trillion x
World #1 supercomputer
(100 qubits: Hefei, China)
QC vs. HPC
High-impact end-user areas:
ICT and finance
Machine-learning/AI
Digital/cyber security
Traffic/supply/network optimisation
Manufacturing/autonomy
Materials/chemistry/health
System size
(# qubits)
MULT20015 Elements of Quantum Computing
Lecture 1
Week 1
Lecture 1
1.1 A very brief overview of computing
1.2 The quantum world and quantum computing
Lecture 2
2.1 The mathematics of quantum states
2.2 Complex numbers and quantum amplitudes
2.3 Basic linear algebra: ket and matrix notation
2.4 State representation in the QUI
Tutorial 1
The Quantum User Interface (QUI), lecture review exercises
MULT20015 Elements of Quantum Computing
Lecture 1
Subject outline
Lecture topics (by week)
1 – Introduction to quantum computing and maths basics
2 – Single qubit representations and logic operations
3 – Two qubit states and logic gates
4 – Multi-qubit states and quantum arithmetic
5 – Basic quantum algorithms
6 – Period finding, cryptography and quantum factoring
7 – Shor’s algorithm, post-quantum crypto, quantum key distribution
8 – Quantum search algorithms
9 – Grover search applications, optimisation problems
10 – Solving optimisation problems on quantum computers
11 – Applications in quantum machine learning
12 – Real quantum computer devices
Assignment schedule:
#1: Hand out in Week 2
#2: Hand out in Week 8