程序代做CS代考 DNA finance algorithm MULT20015 – Elements of Quantum Computing

MULT20015 – Elements of Quantum Computing
Lecture 18
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 18
This Week
Lecture 17
17.1 Grover’s algorithm with Unknown number of solutions 17.2 Quantum counting
17.3 Quantum counting example
Lecture 18 Quadratic Unconstrained Binary Optimization (QUBO) 18.1 Optimization Problems
18.2 Number Partitioning
18.3 Graph Partitioning
18.4 Traveling Salesman Problem
Practice class 9
Quantum counting and QAOA using QUI

MULT20015 – Elements of Quantum Computing Lecture 18
Quadratic Unconstrained Binary Optimization (QUBO)
MULT20015 Lecture 18

MULT20015 – Elements of Quantum Computing
Lecture 18
Review: Last Lecture
Quantum counting circuit
Estimate number of solutions:

MULT20015 – Elements of Quantum Computing
Lecture 18
Quantum Computing and Optimization
Today
1. Optimization problems (QUBO)
2. How to map optimization problems onto the lowest energy state of a
quantum system.
Next week
How to use a quantum computer to find the lowest energy state of a quantum system, and so solving the computational problem.
Next Week
Application of quantum optimization to finance problems

MULT20015 – Elements of Quantum Computing Lecture 18
18.1 Optimization Problems
MULT20015 Lecture 18

MULT20015 – Elements of Quantum Computing
Lecture 18
Optimization Problems
Given some cost-function or “objective function” we would like to maximize/minimize. Often the inputs/parameters are constrained.
Optimal value Cost function
Parameters

MULT20015 – Elements of Quantum Computing
Lecture 18
Physics and computation: Cooling
Physical systems naturally perform optimization problems. For example, if you cool a system towards absolute zero, it will populate the the lowest energy level.
Unoccupied
Energy
Occupied
“Ground” state
High temperature
Low temperature
At low temperatures, physical systems are naturally finding the lowest energy configuration they can. They’re performing computation.

MULT20015 – Elements of Quantum Computing
Lecture 18
Energy of a System
In quantum mechanics, different systems can have different energies (depending on the physical setting). Energies are often written in terms of variables Zi:
+1
Zi =
-1
Energy of the |0istate Energy of the |1istate
You can think of zi as a variable which takes two values:
+1 (if the corresponding qubit i is in the 0 state) -1 (if the corresponding qubit i is in the 1 state)

MULT20015 – Elements of Quantum Computing
Lecture 18
Encoding Problems into the Energy
In building a quantum computer, we have built a perfectly controllable quantum system. We can do different algorithms to try to find the state with the lowest energy.
How can we encode an objective function into the energy of a system?
For a single qubit:
Z EZ
EZ
+1 energy for 0 state -1 energy for 1 state
+E energy for 0 state -E energy for 1 state
+E for the 1 state -E for the 0 state

MULT20015 – Elements of Quantum Computing
Lecture 18
Two Qubit Ising Interactions
“Ising spin” couplings only involve two qubits, the product of two Z operators:
Z1Z2 +1 for 00 or 11 state Anti-ferromagnetic -1 for 01 or 10 state
Z1Z2 -1 for 00 or 11 state Ferromagnetic +1 for 01 or 10 state

MULT20015 – Elements of Quantum Computing
Lecture 18
Total Energy of the System
Consider a system that has an energy function:
E = J12z1z2 + J23z2z3 + J13z1z3 + B1z1 + B2z2 + B3z3
where the zi are +/-1, and the J’s and B’s are specific parameters defining the
particular problem at hand.
Equivalently, the total energy is often labeled “H” (which physicists would call the “Hamiltonian” of a system of qubits):
H = J12Z1Z2 + J23Z2Z3 + J13Z1Z3 + B1Z1 + B2Z2 + B3Z3 Pairwise interactions between qubits Bias on individual qubit
2 13

MULT20015 – Elements of Quantum Computing
Lecture 18
Mapping the Spin Glass form to QC
Optimisation problems can often be cast into an equivalent “spin glass” form:
E=XJijzizj +XBizi i6=j i

MULT20015 – Elements of Quantum Computing
Lecture 18
QUBO Problems
QUBO stands for “Quadratic Unconstrained Binary Optimization”
The cost function (which we want to minimize) is:
E(x1,…,xn)=Xcixi +XQijxixj i i,j
Where xi are Boolean (binary) variables, either 0 or 1. NB. we will use x for binary, z for +/-1
Quadratic term

MULT20015 – Elements of Quantum Computing
Lecture 18
Binary to energy
Typically when we write such energy functions we write in terms of the Z variables:
zi (lower case z) But the binary variables in terms of 0 or 1:
xi=0 or xi=1 Can convert between xi and Zi using:
zi + 1 2
xi !

MULT20015 – Elements of Quantum Computing Lecture 18
18.2 Number Partitioning
MULT20015 Lecture 18

MULT20015 – Elements of Quantum Computing
Lecture 18
Example: Number partitioning
Given the numbers:
1, 3, 8, 10, 6, 5, 5
Is there a way to partition these numbers into two disjoint partitions, such that the sum of the elements in both partitions is the same?
Yes (in this case): {1, 8, 10} and {3, 6, 5, 5}

MULT20015 – Elements of Quantum Computing
Lecture 18
Graph Partitioning to QUBO
1, 3, 8, 10, 6, 5, 5
1 3 8 10 6 5 5
|x7 i The qubit being zero indicates it is one partition.
|x1i |x2i |x3i |x4i |x5i |x6i
We assign a qubit to each number.
The qubit being one indicates it is in the other.
Qubits are |0i if they’re in partition 0,|1i if they’re in partition 1

MULT20015 – Elements of Quantum Computing
Lecture 18
Number partitioning as a QUBO problem
1, 3, 8, 10, 6, 5, 5
As an optimization problem: We want
Xwizi =0 i
±1
Unfortunately if we just minimize this, all the qubits will end up with zi=-1!
The ith number

MULT20015 – Elements of Quantum Computing
Lecture 18
Number partitioning as a QUBO problem
But if we square, we should get a positive solution (or zero). We want to find the assignment of spins which has the minimum energy (ie. closest to zero):
X!2X X2 H = wiZi = 2wiwjZiZj + wi I
i i6=j i Coupling is the product of numbers
Simple example using the numbers {1, 2, 3}: 2
4 H = 4Z1Z2 + 6Z1Z3 + 12Z2Z3 + 14I 1 12
Finding minimum energy state will solve the problem!
6
3

MULT20015 – Elements of Quantum Computing
Lecture 18
Solution for our Number Partitioning
H = 4Z1Z2 + 6Z1Z3 + 12Z2Z3 + 14I
|110i |001i 1,2 3
E = 4 6 12 + 14 = 0 And of course, they correctly partition the numbers: 1+2 = 3
Other combinations require higher energy, eg, |111i
E = 4 + 6 + 12 + 14 = 36
Two degenerate solutions:

MULT20015 – Elements of Quantum Computing Lecture 18
18.3 Graph Partitioning
MULT20015 Lecture 18

MULT20015 – Elements of Quantum Computing
Lecture 18
Example: Graph Partitioning
1
2
6
What is a partition of the set of vertices, V, into two subsets of equal size such that the number of edges connecting the two partitions is minimized?
53
4

MULT20015 – Elements of Quantum Computing
Lecture 18
Example: Graph Partitioning
Subset 0
1
4
Subset 1
6
5
2
3
What is a partition of the set of vertices, V, into two subsets of equal size such that the number of edges connecting the two partitions is minimized?

MULT20015 – Elements of Quantum Computing
Lecture 18
Graph Partitioning to QUBO
123456
|x1i |x2i |x3i |x4i |x5i |x6i Qubits are |0i if they’re in parition 0, |1iif they’re in parition 1

MULT20015 – Elements of Quantum Computing
Lecture 18
Even numbers in each subset
HA= XZi!2 i
As before, having an equal number of terms in each partition will evaluate to zero. Unequal numbers result in a positive value.

MULT20015 – Elements of Quantum Computing
Lecture 18
Number of edges joining the subsets
H B = X I1 Z i Z j i,j2E 2
Evaluates to 0 if the both vertices connected to an edge are in the same partition, but +1 if the edge goes between partitions. In total HB counts the number of edges between the two partitions.

MULT20015 – Elements of Quantum Computing
Lecture 18
Total Hamiltonian
HA= XZi i
!2
Same number of vertices in each partition.
Number of edges between partitions.
HB = X I1 ZiZj i,j2E 2
In total then, with A>>B:
H = AHA + BHB

MULT20015 – Elements of Quantum Computing Lecture 18
18.4 Travelling Salesman Problem
MULT20015 Lecture 18

MULT20015 – Elements of Quantum Computing
Lecture 18
Travelling Salesman Problem (TSP)
Given several (n) cities and the distances between them, find the shortest path (Hamiltonian cycle) which visits all of them once and returns to the original city.
• TSP is an example of an NP-Complete problem (Karp, 1972) and best known classical algorithms require exponential time.
• Has many direct practical applications including planning, logistics, DNA sequencing, and astronomy.
• Largest solved tour is approximately 85,000 sites with heuristic methods able to find solutions (for million site tours) within 2-3% of the optimal tour.

MULT20015 – Elements of Quantum Computing
Lecture 18
Mapping TSP to QUBO problem
i
1st 2nd stop stop
3rd stop
4th stop
v
Sydney
Canberra
Melbourne Adelaide
xi,v = ⇢ 1, tour passes through city v at step i 0, otherwise

MULT20015 – Elements of Quantum Computing
Lecture 18
Energy Penalties
Each city appears exactly once in the cycle:
Hcity =X 1Xxv,i!2 vi
Each step has exactly one city:
!2
Only paths between cities with edges between them are taken:
Hcycle = X X xu,ixv,i+1
i
Any path making a cycle will have energy, E=0, with all other combinations having higher energy.
Hstep=X 1Xxv,i iv
u ! v 2/ E

MULT20015 – Elements of Quantum Computing
Lecture 18
Shortest cycle
To find the shortest cycle, add an energy penalty of the length of the cycle:
Hlength = X X
i u!v2E
Wuvxu,ixv,i+1 Finding the lowest energy arrangement of xv,I of
HT SP = A(Hcity + Hsite + Hcycle) + BHlength
will solve the corresponding TSP problem (A>>B).
We can make the problem quantum mechanical by mapping classical
variables xv,I to qubits (and operators):
xv,i ! I + Zv,i
2
The problem is now to find the ground state of a quantum mechanical Hamiltonian. We will see a method to do this: QAOA. Next lecture!
1

Related Posts