代写代考 MULT90063 Introduction to Quantum Computing

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

MULT90063 Introduction to Quantum Computing
Hybrid Quantum/Classical Optimization Algorithms Lecture 20

MULT90063 Introduction to Quantum Computing
This lecture we will talk about two algorithms to find the minimum energy of a quantum system:
• Quantum Approximate Optimization Algorithm (QAOA) algorithm
• Variational Quantum Eigen-solver (VQE) algorithm
Both algorithms are closely related, combining classical optimization with quantum mechanical states.
Kaye 8.5 Rieffel 13.4.2

MULT90063 Introduction to Quantum Computing
Review of last lecture
Optimal value Cost function
Ising coupling
local “field”
We can encode problems in the energy of the system, but we had no way of minimizing the energy. Today we will see a hybrid technique which allows us to minimize the energy of a quantum system.
H=XJijZiZj +XBiZi i6=j i

MULT90063 Introduction to Quantum Computing
Recall 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
-> 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)

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 a set, S, of numbers:
1, 3, 8, 10, 6, 5, 5
Is there a partition of this set of numbers into two disjoint subsets R and S − R, such that the sum of the elements in both sets 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
|x1i |x2i |x3i |x4i |x5i |x6i
We assign a qubit to each number in the problem set. The qubit being zero indicates it is one subset.
The qubit being one indicates it is in the other.
Qubits are |0i if they’re in subset 0, |1i if they’re in subset 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
Eg. For the set {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
QAOA Overview
QAOA = “Quantum Approximate Optimization Algorithm”
Farhi, Goldstone and Gutman, 2014

MULT90063 Introduction to Quantum Computing
Structure of Algorithm
(1)Prepareatrialstate| (✓)i
on the quantum computer, where θ represents angles in phase and X rotations.
(2) Measure the solution in z basis to obtain the energy, E.
(3) For small depth circuits can analytically calculate optimal values for θ. Original paper found these for a MAX-CUT problem.
QUI/Quantum Computer

MULT90063 Introduction to Quantum Computing
Structure of Algorithm
(1) Prepare a trial state | (✓)i
on the quantum computer, where θ can be any adjustable gate parameter.
(2) Measure the expectation value of the energy, E.
(3) Use a classical optimization technique such as the Nelder–Mead simplex method, determine new values of θ that decrease E.
Repeat these steps until the value of the energy converges
QUI/Quantum Computer

MULT90063 Introduction to Quantum Computing
QAOA overview
Initialisation
1st iteration
extract E value re-set
parameters αi and βi
repeat until min is found
Let’s say we want to find an optimal solution for the cost function:
H =Z1Z2 +2Z2Z3 +Z1
measurement

MULT90063 Introduction to Quantum Computing
Example QAOA: Phase operations
We want to find an optimal solution (minimum) for the cost function:
H =Z1Z2 +2Z2Z3 +Z1
Our first step is to apply Hadamard gates, to produce an equal superposition:

MULT90063 Introduction to Quantum Computing
Phase gates in QAOA circuit: P(𝛼) For every Z term in the Hamiltonian:
H=XJijZiZj +XBiZi i6=j i
For every ZZ term in the Hamiltonian:
𝐻 = … + 𝐵! 𝑍! + …
𝜃i =−𝐵!𝛼 2
𝐻 = … + 𝐽!” 𝑍! 𝑍𝑗 + …
𝜃𝑖𝑗 =−𝐽!”𝛼 2
Angles all proportional to their term in the Hamiltonian.

MULT90063 Introduction to Quantum Computing
Phase operation example
Each term’s sequence can be placed consecutively. Order of terms does not matter.
H =Z1Z2 +2Z2Z3 +Z1
Each term in the cost function gets a gate sequence.
Each rotation angle is proportional to the energy term.
𝜃 # = − 𝛼2
2 𝛼 2 𝜃$% = − 2 = −𝛼

MULT90063 Introduction to Quantum Computing
X-rotations
X-rotations on every qubit
Trial state
|𝜓(𝛼#,𝛽#)⟩
Preparation of a trial state, for k=1 iterations

MULT90063 Introduction to Quantum Computing
X rotation
After the phase operation, we add x-rotations (again with an angle, 𝛽, which we optimize):

MULT90063 Introduction to Quantum Computing
Two iterations
Trial state
|𝜓(𝛼#, 𝛽#, 𝛼$, 𝛽$)⟩
Preparation of a trial state, for k=2 iterations

MULT90063 Introduction to Quantum Computing
Measuring the energy
The Hamiltonian of a QUBO problem can be expressed as a sum of several terms:
Ising coupling
local “field”
For example:
H=XJijZiZj +XBiZi i6=j i
H = B1Z1 + B2Z2 + J12Z1Z2
A better approximation to the ground state (depending on the number of steps, k, and the choice of angles) will have a higher probability of measuring the minimum energy, and the lowest energy state.

MULT90063 Introduction to Quantum Computing
One round QAOA
The whole circuit (using just one round, p=1) is therefore:
Using values of α = 0.2𝜋 and 𝛽 = −0.1𝜋, we get:
Here 101 is the solution. We have not optimized the angles at all, but already you can see (even on our first try) that its amplitude has increased. Optimising the angles would increase it further.

MULT90063 Introduction to Quantum Computing
One round QAOA
The whole circuit (using just one round, p=1) is therefore:
Using values of α = 0.2𝜋 and 𝛽 = −0.1𝜋, we get:
Work out the average energy, adjust the angles and rerun the experiment, until we come to a minimum energy.

MULT90063 Introduction to Quantum Computing
Calculating the average energy

MULT90063 Introduction to Quantum Computing
Calculating the energy
H =Z1Z2 +2Z2Z3 +Z1

MULT90063 Introduction to Quantum Computing
Calculating the average energy
Obtained from running quantum computer
Probability, pi
*Made up probabilities for demonstration!
Calculate the average energy: 𝐸 = 9 𝑝! 𝐸! = −1.8 !

MULT90063 Introduction to Quantum Computing
Measure to find energy
Measure Z:
In the QUI you can look directly at probabilities rather than measure and building statistics!
Unlike for QEC codes, you don’t need to add an extra qubit to measure correlations. Eg. For ZZ you can just multiply yourself for a given state!

MULT90063 Introduction to Quantum Computing
Multiple measurements
Original function we would like to minimize:
H = B1Z1 + B2Z2 + J12Z1Z2
Take many samples, to determine:
hHi = B1hZ1i + B2hZ2i + J12hZ1Z2i

MULT90063 Introduction to Quantum Computing
QAOA overview
Initialisation
1st iteration
extract E value re-set
parameters αi and βi
repeat until min is found
measurement

MULT90063 Introduction to Quantum Computing
VQE overview
VQE = Variational Quantum Eigensolver
We need not confine ourselves to Ising/Z terms. Many interesting quantum systems have a Hamiltonian, H, which includes terms in X and Y (and might not even come from a qubit system at all!).
Or perhaps we have a Hermitian matrix, and we just want to find the smallest eigenvalue. How do we do that?
1) PickaconvenientbasistoexpressH
2) Writeoutthetotalenergy,H,asamatrix
3) ConvertyourmatrixalinearcombinationofPaulimatrices 4) Parameterizean“Ansatz”wavefunctioncandidatesolution
to problem
5) Usehybridclassical/quantumoptimizationtofindthe
lowest energy and lowest energy state.

Hamiltonian as
linear combination of Pauli operators
MULT90063 Introduction to Quantum Computing
Always possible decompose a matrix as a sum of Paulis. If you have a matrix only:
Ei = Tr[iH] d
Where d is the dimension of the system, H is the Hamiltonian and σi is the Pauli. If the matrix is Hermitian, the co-efficients you find, Ei, should be real.
Express the Hamiltonian as a sum of Paulis:
For example:
H = XEii i
H = B1X1 + B2X2 + J12Z1Z2

MULT90063 Introduction to Quantum Computing
Find the expectation value of H
We can express the expectation value of the energy as a sum of expectation values of the Paulis:
hHi = XEihii i
hHi = B1hX1i + B2hX2i + J12hZ1Z2i
For a given trial state, these can be found directly from experiment (or through the QUI)
For our example:

MULT90063 Introduction to Quantum Computing
Reminder: How to measure X: Measure Y:
Measure Z:
In the QUI you record probabilities rather than measure and building statistics!
Unlike for QEC codes, you don’t need to add an extra qubit to measure correlations. Eg. For ZZ you can just multiply yourself given the state which is measured!

MULT90063 Introduction to Quantum Computing
VQE: Transformation
A classic of physics from 1928, by Jordan and Wigner. You’ve got a system of qubits. You want to use it to simulate fermions (eg. someone’s given you a chemistry problem involving electrons). Electrons do not behave the same as qubits.
How do we do this?
Tempting solution: 
j+!Xj+iYj = 0 0 =fj+ Createafermionatthejthsite? 2 10j
j ! Xj iYj = 0 1 =fj Destroyafermionatthejth site? 2 00j
This is close but WRONG! The commutation relations between different sites are
wrong (fermions anti-commute).
[fj,fk] = 0

MULT90063 Introduction to Quantum Computing
Transformation
Correct solution:
+ !Z Z …Z Xj +iYj j 12 j1 2
!Z Z …Z Xj iYj j 12 j1 2
Jordan and Wigner: Images from Wikipedia

MULT90063 Introduction to Quantum Computing
Picking a VQE Ansatz
QAOA State
Use a combination of X rotations and phase rotations.
Adiabatic Methods
Slowly vary the Hamiltonian, in a parameterized way, to obtain an approximation to the ground state.
Coupled Cluster Methods
First start in a (often unentangled) reference state, which can be calculated classically, eg. with mean field methods.
Consider successively more complicated perturbations away from this reference state: First we consider just (parameterized) single qubit rotations away from the reference state. Then we consider unitaries with both single qubit rotations and two body interactions, then one, two and three body interactions. As with QAOA we can consider several rounds of interaction.

MULT90063 Introduction to Quantum Computing
Nelder- Optimization
A classical method of optimization.
– Classical optimization technique
– Requires only the calculation of few points at each
Based on simplex:
A simplex S in n dimension is defined as the convex hull of n+1 vertices: x0,…,xn
Eg. Triangle in 2D

MULT90063 Introduction to Quantum Computing
Nelder-Mead operations
Start with an initial simplex
Repeat until the convergence is reached:
Test if we’ve reached convergence
If not then transform the working simplex
Four types of transformation to test:
1) Reflection
Worst point
Centroid of all other points

MULT90063 Introduction to Quantum Computing
Nelder-Mead operations
3) Contract
Worst point
Centroid of all other points
Worst point
Centroid of all other points

MULT90063 Introduction to Quantum Computing
Visualization
Image: Nicoguaro, Wikipedia

MULT90063 Introduction to Quantum Computing
Example: Inter-molecular distance
Peruzzo, Aspuru-Guzik, O’Brien et al, Nature Communications, 5, 4213 (2014)

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

Related Posts