程序代写代做代考 AI algorithm MULT20015 Elements of Quantum Computing Lecture 10

MULT20015 Elements of Quantum Computing Lecture 10
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 10
Week 5
Lecture 9
9.1 Algorithms
9.2 Example Classical Algorithms and Complexity Analysis 9.3 Quantum Algorithms
Lecture 10
10.1 Deutsch-Josza Algorithm 10.2 Simon’s Algorithm
Practice class 5
Simple Quantum Algorithms

MULT20015 Elements of Quantum Computing Lecture 10
Recap: Lecture 9
Classical Algorithms
Algorithms are set of instructions which when executed on a computer solves a computational problem.
Examples:
1) Binary Search
2) Insertion Sort
3) Greatest Common Divisor (GCD)
Quantum Complexity
The total time to run an algorithm on a computer is: Tn = Ce*f(n)
Classical Computersàimproves Ce Quantum Computersàimproves f(n)
Complexity Classes
Algorithms are classified by asymptotic cost analysis.
For algorithm cost function f(n),
f(n) = O(g(n)) if g(n) is upper bound to f(n) f(n) = 𝛺(g(n)) if g(n) is lower bound to f(n) Here “n” is the size of the input.
Intractable problems:
Problems for which no polynomial time algorithm exits
Example:
Sampling of a Random Quantum Circuit

MULT20015 Elements of Quantum Computing Lecture 10
10.1 Deutsch-Josza Algorithm
MULT20015 Lecture 10

MULT20015 Elements of Quantum Computing Lecture 10
Example 1: Deutsch-Josza algorithm
Problem: Given a Boolean function, f(x), determine if:
f(x) is constant (always gives the same result), or
f(x) is balanced (gives equal numbers of 0s and 1s)
Note:
Single qubit version -> Deutsch Algorithm Multi qubit version -> Deutsch-Josza Algorithm
Applications:
No well-defined real-world application
First algorithm that showed quantum solution has fewer steps than any known classical solution Inspiration for Simon’s algorithm which was then inspiration for Shor’s famous algorithm

MULT20015 Elements of Quantum Computing Lecture 10
Classical Complexity
For an input “x” of “n” bits, the function f(x) is: n=1
n=2
CONSTANT
f(0) = 0 f(1) = 0
f(0) = 1 f(1) = 1
BALANCED
f(0) = 0 f(1) = 1
f(0) = 1 f(1) = 0
CONSTANT
f(00) = 0 f(01) = 0 f(10) = 0 f(11) = 0
f(00) = 1 f(01) = 1 f(10) = 1 f(11) = 1
Elementary Operation: Evaluation of f(x) for n Classical algorithm (worst case) needs (2n/2)+1 queries
Cost = (2n/2)+1 = O(2n)
Quantum algorithm (Deutsch-Josza) needs just 1 query Cost = 1 = O(1)
BALANCED
f(00) = 0 f(01) = 0 f(10) = 1 f(11) = 1
f(00) = 1 f(01) = 1 f(10) = 0 f(11) = 0

MULT20015 Elements of Quantum Computing Lecture 10
Example of a constant function
Recall for n=1:
|xi
CONSTANT
f(0) = 0 f(1) = 0
f(0) = 1 f(1) = 1
|xi |0⟩ |?⟩
X
The X-gate in the circuit always flips (ie. NOT) the second qubit, regardless of the input. This function is constant, since the output is always 1.

MULT20015 Elements of Quantum Computing Lecture 10
Example of a balanced function
Recall for n=1:
BALANCED
f(0) = 0 f(1) = 1
f(0) = 1 f(1) = 0
|xi |xi |0⟩ |?⟩
The circuit only flips (ie. NOT) the second qubit, if the input is a 1.
This function is balanced, since the output has equal numbers of 0 and 1 output.

MULT20015 Elements of Quantum Computing Lecture 10
Quantum circuits for constant/balanced functions For one qubit input case, the implementations for 4 choices of function are:
CONSTANT
BALANCED
f(0) = 0 f(1)=0 f(0) = 1 f(1) = 1 f(0) = 0 f(1)=1 f(0) = 1 f(1) = 0
X
X

MULT20015 Elements of Quantum Computing Lecture 10
General Deutsch/Deutsch-Josza Circuit
The general quantum circuit for Deutsch/Deutsch-Josza algorithm is:
Here Uf will be designed for constant/balanced implementations. Recall from multi-qubit Lecture 8:
|𝑦⟩ = |0′ -> |𝑦 ⊕ 𝑓(𝑥)⟩ = |𝑓(𝑥)’ Therefore, U!|𝑥⟩|0′ = |𝑥⟩|𝑓(𝑥)⟩
|xi
|yi |y f(x)i
|xi
Uf

MULT20015 Elements of Quantum Computing Lecture 10
Deutsch algorithm (single bit functions): constant function
Let’s carefully look at the working of quantum circuit for the constant case:
|0i |1i
Uf
H
H
H
X
The function, U, is implemented by the gates inside this box

MULT20015 Elements of Quantum Computing Lecture 10
Deutsch algorithm: walkthrough
|0i |1i
Uf
H
H
H
X
| i=|0i⌦|1i

MULT20015 Elements of Quantum Computing Lecture 10
Deutsch algorithm: walkthrough
|0i |1i
H
H
H
| i=H|0i⌦H|1i
|0i + |1i |0i |1i
= p2 ⌦ p2 = |+i ⌦ |i
Uf
X
Note:
|+⟩= |0⟩+|1⟩ 2
|−⟩= |0⟩−|1⟩ 2

MULT20015 Elements of Quantum Computing Lecture 10
Deutsch algorithm: walkthrough
|0i |1i
Uf
H
H
H
X
| i=|+i⌦X|i
|0i + |1i |0i |1i
= p2 ⌦X p2 |0i + |1i |1i |0i
= p2 ⌦ p2 = |+i ⌦ |i
Global phase is un-measurable

MULT20015 Elements of Quantum Computing Lecture 10
Deutsch algorithm: walkthrough
| i=H|+i⌦|i = |0i ⌦ |i
|0i |1i
Uf
H
H
X
H
Note:
H|+⟩ = H |0⟩ + |1⟩ 2
= |0⟩+|1⟩+|0⟩−|1⟩ 2
= |0⟩ Hence: H|+⟩ = |0⟩

MULT20015 Elements of Quantum Computing Lecture 10
Deutsch algorithm: walkthrough
|0i |1i
Uf
H
H
H
X
|0i |1i | i=|0i⌦ p2
= |0i ⌦ |i
We will measure “0” on upper qubit with 100% probability.
As we will see when we look at all cases, this indicates (with a single evaluation of the function) that the function is constant.

MULT20015 Elements of Quantum Computing Lecture 10
Deutsch algorithm: balanced function
Now let’s carefully look at the working of quantum circuit for the balanced case:
|0i |1i
Uf
H
H
H
The function, U, is implemented by the gates inside this box

MULT20015 Elements of Quantum Computing Lecture 10
Deutsch algorithm: walkthrough
|0i |1i
Uf
H
| i=|0i⌦|1i
H
H

MULT20015 Elements of Quantum Computing Lecture 10
Deutsch algorithm: walkthrough
|0i |1i
Uf
H
H
H
| i=H|0i⌦H|1i
|0i + |1i |0i |1i
= p2 ⌦ p2 = |+i ⌦ |i

MULT20015 Elements of Quantum Computing Lecture 10
Deutsch algorithm: walkthrough
|0i |1i
Uf
H
H
H
|𝜓⟩ = CNOT|+⟩|−⟩ = CNOT |0⟩ + |1⟩ ⊗ |0⟩ − |1⟩ 22
|𝜓⟩ = CNOT |0⟩|0⟩ − |0⟩|1⟩ + |1⟩|0⟩ − |1⟩|1⟩ 2
|𝜓⟩ = CNOT |0⟩|0⟩ − |0⟩|1⟩ + |1⟩|1⟩ − |1⟩|0⟩ = |−⟩|−⟩ 2

MULT20015 Elements of Quantum Computing Lecture 10
Deutsch algorithm: walkthrough
| i=H|i⌦|i = |1i ⌦ |i
|0i |1i
Uf
H
H
H
Note:
H|−⟩ = H |0⟩ − |1⟩ 2
= |0⟩+|1⟩−|0⟩+|1⟩ 2
= |1⟩ Hence: H|−⟩ = |1⟩

MULT20015 Elements of Quantum Computing Lecture 10
Deutsch algorithm: walkthrough
|0i |1i
Uf
H
H
H
| i=|1i⌦|i We will measure “1” with 100% probability.
As we will see in the summary, this indicates (with a single evaluation of the function) that the function is balanced.

MULT20015 Elements of Quantum Computing Lecture 10
Deutsch Algorithm – summary
|0i |1i
H
Uf
H
H
BALANCED
f(0) = 1 f(1) = 1
f(0) = 0 f(1) = 1
f(0) = 1 f(1) = 0
Measured
CONSTANT
f(0) = 0 f(1) = 0
0
0
1
1
The Deutsch algorithm determines in just one query whether the function is constant or balanced.
Classically, this would require two queries.

MULT20015 Elements of Quantum Computing Lecture 10
Deutsch-Josza – Multi-Qubit Version
This means that there are multiple qubits in the register
Only a single qubit here
The multi-qubit Deutsch-Josza algorithm will still require only one query to determine whether the function is constant or balanced.
|0i |1i
H
Uf
H
H
Note: 0s in output register -> constant, any other valve -> balanced.
n qubit register:
|0i |0i
|0i |0i
|0i
H
H
H
H
H
…

MULT20015 Elements of Quantum Computing Lecture 10
10.2 Simon’s Algorithm
MULT20015 Lecture 10

MULT20015 Elements of Quantum Computing Lecture 10
Example 2: Simon’s Problem
Problem: Given a 2-to-1 function, f , such that f (x) = f (x ⊕ 𝑎)
Find a.
Here the range of f (x) is Z, integers.
Just like the previous algorithm, Simon’s algorithm also did not have immediate real-
world application. However, it is exponentially faster than the classical algorithm. Simon’s algorithm was the inspiration for Shor’s factoring algorithm.

MULT20015 Elements of Quantum Computing Lecture 10
Example of a hidden a
Note: for all values of x, f (x) will have the same value for exactly two valves of x. Suppose the input x is a 3-bit number.
f(001) = f(111)
We would like to find the hidden ‘a’ s.t. f(x) = f(x ⊕ 𝑎)
To find a, compute bitwise XOR between the two values of x that generate same f (x):
001 ⊕ 111 = 110, hence in this case: a =1102=6
x
f(x)
000
0
001
1
010
2
011
3
100
2
101
3
110
0
111
1

MULT20015 Elements of Quantum Computing Lecture 10
Classical Complexity
Classically, this is a hard problem because you might have to probe the function with many successive values of input x until you get the same f (x) for two different input values.
The number of possible inputs (N) increase exponentially with the number of bits (n) in x. i.e. n=3 will have N=23=8 possible inputs, n=4 will have N=24=16 possible inputs, and so on…
Elementary operation: evaluation of f (x) for a given value of x
So how many elementary operations are actually required to find a?
Actually, this is equivalent to the famous “birthday” problem and takes fewer queries than you might expect.
Probabilistically, if there are N (=2n) different inputs we need O 𝑁 = O 2 “# = O ( 2 ” )
Evaluations of the function before we find a collision. Simon’s algorithm does the same with O(n) queries.
f (000) = 0 f (011) = 3
f (111) = 1 f (010) = 2 f (001) = 1

MULT20015 Elements of Quantum Computing Lecture 10
Simon’s algorithm circuit
Randomly measure a result of the function.
Collapse to a superposition of inputs which give that value. Send these through Hadamard gates, and measure:
x
Note: x is a multi-qubit state [recall Lecture 8].
Measure to find a
Uf
|0i |0i
H
H
|xi |xi
|0i |0f(x)i
Uf

MULT20015 Elements of Quantum Computing Lecture 10
Simon’s algorithm
After evaluation of the function:
1X
| i=pN
Uf|xi|0i |xi|f(x)i
|0i |0i
H
Uf
H
|xi |xi
|0i |0f(x)i
Uf
Xx = pN x
1

MULT20015 Elements of Quantum Computing Lecture 10
Simon’s algorithm
|0i |0i
It’s easiest to consider that the bottom register is measured first. Before measurement (red dashed) the state is: X
1
| i=pN x |xi|f(x)i
Some value, f (x0) will be measured at random, and the top register collapses to
(green line):
|x0i+|x0 ai |i= p2
H
Uf
H

MULT20015 Elements of Quantum Computing Lecture 10
Example: measuring the function register
1X
| i=pN x |xi|f(x)i
1
= p8(|0i|0i+|1i|1i+|2i|2i+ +|4i|2i+ +|6i|0i+|7i|1i)
If we measure the second register, and measure obtain “3”, the state collapses to only those states compatible with this measurement:
0 |3i |3i + |5i |3i |i= p2
|3i + |5i
= p2 ⌦|3i
|x0i + |x0 ai | i= p2
x
f(x)
000
0
001
1
010
2
011 3
100
2
101
3
110
0
111
1
Firstregister:
Here x
the measured f (x0)
|3i |3i
0
|5i |3i
is the value of x corresponding to

MULT20015 Elements of Quantum Computing Lecture 10
Simon’s algorithm
After measuring the bottom function register:
We now apply Hadamard to the top register (over all qubits):
⌦n|x0i+|x0 ai | i=H p2
y is the measured value in the top register after H operation.
|0i |0i
H
Uf
H

MULT20015 Elements of Quantum Computing Lecture 10
Simon’s algorithm
Constraint on the measured value of y:
After H gate on first/upper output, you will only measure y’s for which:
a·y=0 mod2 a·y=0 mod2
|0i |0i
H
Uf
H
Each time we measure, we randomly measure a “y” which is orthogonal to “a”:
Note:
a . y = a1y1 + a2y2 + a3y3

MULT20015 Elements of Quantum Computing Lecture 10
Example of Simon’s algorithm
x
f(x)
000
0
001
1
010
2
011
3
100
2
101
3
110
0
111
1
We would like to find the hidden ‘a’ s.t. f (x) = f (x ⊕ 𝑎)
In this case, a =1102=6
We run the circuit, and at random, measure the results:
001
110
111
a·y=0 mod2
y=

MULT20015 Elements of Quantum Computing Lecture 10
Finding a
Now, how do we find a?
a·y=0 mod2
We have three values of ‘y’ for which this is true, so we can write a system of linear
equations for the bits of ‘a’: Measured
values
𝑎$ = 0
𝑎% + 𝑎# = 0 𝑎% + 𝑎# + 𝑎$ = 0
Solving for a1, a2, and a3
Solution is degenerate. a =(0,0,0) or a1= a2=1 i.e. a=(1,1,0)
We know that
Note:
a is a 3-bit number: (a1,a2,a3)
001
110
111

MULT20015 Elements of Quantum Computing Lecture 10
Simon’s Algorithm – Summary
H
Uf
H
Given a 2-to-1 function, f, such that
Find a.
f(x) = f(x a)
|0i |0i
Classical algorithm: O 𝑁 = O 2″# = O(2″)
Queries to the oracle (probabilistically)
Quantum algorithm: O(𝑛)
Queries to the oracle

Related Posts