CS计算机代考程序代写 finance algorithm MULT20015 Lecture 1 2021 v1

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