MULT90063 Introduction to Quantum Computing
Lecture 19
Optimization problems, Encoding problems as energies, Quadratic Binary Optimization (QUBO), Problem embedding
Lecture 20
Copyright By PowCoder代写 加微信 powcoder
Quantum Approximate Optimization Algorithm (QAOA), Variational Quantum Eigensolver (VQE), classical feedback
Optimization problems
MULT90063 Introduction to Quantum Computing
Quantum Optimization Lecture 19
MULT90063 Introduction to Quantum Computing
This lecture we will talk about mapping Optimization Problems to physical systems:
• Cooling as an optimization algorithm
• QUBO problems
• Examples of QUBO problems:
– Subsetsum,GraphPartitioningandTravellingSalesman
• Embedding problems in quantum computing architectures
Kaye 8.5 Rieffel 13.4.2
MULT90063 Introduction to Quantum Computing
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
MULT90063 Introduction to Quantum Computing
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
“Ground” state
High temperature
Low temperature
At low temperatures, physical systems are naturally finding the lowest energy configuration they can. They’re performing computation.
MULT90063 Introduction to Quantum Computing
Reminder: Measuring Observables
IN QM an observable (eg. energy) is represented by a Hermitian matrix. The values measured of when measuring the observable are the eigenvalues of the corresponding matrix.
In the simplest case, the matrix is a diagonal matrix and the eigenvalues are listed down the diagonal:
H stands for “Hamiltonian” The total energy in the system.
H = Z = 1 0
Energy of the |0istate Energy of the |1istate
In more complicated cases you may have to diagonalize the matrix first, using an eigenvalue decomposition.
MULT90063 Introduction to Quantum Computing
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:
+1 energy for 0 -1 energy for 1
+E energy for 0 -E energy for 1
+E for the 1 state -E for the 0 state
MULT90063 Introduction to Quantum Computing
Measuring Observables (multiple qubits)
Each observable (eg. energy) is represented by a Hermitian matrix. The values measured of when measuring the observable are the eigenvalues of the corresponding matrix.
In the simplest case, the matrix is a diagonal matrix and the eigenvalues are listed down the diagonal:
H stands for “Hamiltonian” The total energy in the system.
21 H = Z ⌦ Z = 60
0 0 03 1 0 07 0 1 05
Energy of the|00istate Energy of the|01istate Energy of the|10istate Energy of the |11istate
In more complicated cases you may have to diagonalize the matrix first, using an eigenvalue decomposition.
MULT90063 Introduction to Quantum Computing
Two Qubit Ising Interactions
“Ising spin” couplings only involve two qubits, and just 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
MULT90063 Introduction to Quantum Computing
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.
To get ready to map to a QC, we write the total energy as the operator “H” (which physicists would call the “Hamiltonian”) on a system of qubits as a sum of these terms with zi -> Zi (where Zi is the Z operator on the ith qubit):
H = J12Z1Z2 + J23Z2Z3 + J13Z1Z3 + B1Z1 + B2Z2 + B3Z3 Pairwise interactions between qubits Bias on individual qubit
MULT90063 Introduction to Quantum Computing
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
This is convert to a convenient form to map onto a quantum computer:
Ising coupling
local “field”
H=XJijZiZj +XBiZi i6=j i
The Zi are now operators defined as per our definitions with eigenvalues +/-1 (which can be mapped to binary variables 0/1)
In QM, energy is represented as a matrix!
MULT90063 Introduction to Quantum Computing
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
MULT90063 Introduction to Quantum Computing
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:
MULT90063 Introduction to Quantum Computing
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}
MULT90063 Introduction to Quantum Computing
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
MULT90063 Introduction to Quantum Computing
Number partitioning as a QUBO problem
1, 3, 8, 10, 6, 5, 5
As an optimization problem: We want
Xwizi =0 i
Unfortunately if we just minimize this, all the qubits will end up with zi=-1!
The ith number
MULT90063 Introduction to Quantum Computing
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
Example for the numbers {1, 2, 3}: 2
H = 4Z1Z2 + 6Z1Z3 + 12Z2Z3 + 14I Finding minimum energy state will solve the problem!
MULT90063 Introduction to Quantum Computing
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 go worse, eg, |111i
E = 4 + 6 + 12 + 14 = 36
Two degenerate solutions:
MULT90063 Introduction to Quantum Computing
Example: Graph Partitioning
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?
MULT90063 Introduction to Quantum Computing
Example: Graph Partitioning
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?
MULT90063 Introduction to Quantum Computing
Graph Partitioning to QUBO
|x1i |x2i |x3i |x4i |x5i |x6i Qubits are |0i if they’re in parition 0, |1iif they’re in parition 1
MULT90063 Introduction to Quantum Computing
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.
MULT90063 Introduction to Quantum Computing
Number of edges joining the subsets
HB = X I ZiZj i,j2E 2
Evaluates to 0 if the edge is in the same partition, but +1 if the edge goes between partitions. In total HB counts the number of edges between the two partitions.
MULT90063 Introduction to Quantum Computing
Total Hamiltonian
In total then, with A>>B:
HB = X I ZiZj i,j2E 2
Same number of vertices in each partition.
Number of edges between partitions.
H = AHA + BHB
MULT90063 Introduction to Quantum Computing
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.
MULT90063 Introduction to Quantum Computing
Mapping TSP to QUBO problem
1st 2nd stop stop
Melbourne Adelaide
xi,v = ⇢ 1, tour passes through city v at step i 0, otherwise
MULT90063 Introduction to Quantum Computing
Energy Penalties
Each city appears exactly once in the cycle:
Hcity =X 1 Xxv,i!2 vi
Each step has exactly one city:
Only paths between cities with edges between them are taken:
Hcycle = X X xu,ixv,i+1
Any path making a cycle will have energy, E=0, with all other combinations having higher energy.
Hstep=X 1 Xxv,i iv
u ! v 2/ E
MULT90063 Introduction to Quantum Computing
Shortest cycle
To find the shortest cycle, add an energy penalty of the length of the cycle:
Hlength = X X
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 -> several ways to do this by coding the problem onto a QC
i.e. digital (e.g. QAOA/VQE next lecture) or analogue (e.g. AQC, later on)
MULT90063 Introduction to Quantum Computing
Quantum Computer Layouts
S. Tonetto MSc thesis
MULT90063 Introduction to Quantum Computing
Embedding computational problems
Ferromagnetic couplings, both qubits the same
Minor embedding
S. Tonetto MSc thesis
MULT90063 Introduction to Quantum Computing
Embedding complete graph
Graph from: S. Tonetto MSc thesis
MULT90063 Introduction to Quantum Computing
Speed up of optimization algorithms
It is proven (Aharononv, Kempe, et al) that you can map any circuit onto an equivalent optimization problem, with only a polynomial difference in resources (including time required to solve).
Their cost functions involve more than just “Z” – carefully worked out “gadgets”.
Just because we can find an encoding of a problem in a way which a quantum computer could solve it, doesn’t say anything about the speed up.
Typically, we when considering hard problems such as NP-Complete problems (e.g. TSP) we expect to achieve a quadratic speedup in accordance with quantum search on unstructured problems.
Given the power of classical heuristics to attack such problems, the development and power of “quantum heuristics” is an open question.
MULT90063 Introduction to Quantum Computing
Lecture 19
Optimization problems, Encoding problems as energies, Quadratic Binary Optimization (QUBO), Problem embedding
Lecture 20
Quantum Approximate Optimization Algorithm (QAOA), Variational Quantum Eigensolver (VQE), classical feedback
Optimization problems
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com