CS代写 MULT90063 Introduction to Quantum Computing

MULT90063 Introduction to Quantum Computing
Lecture 21
Adiabatic Quantum Computing
Lecture 22

Further quantum algorithms – HHL algorithm
Adiabatic quantum computation

MULT90063 Introduction to Quantum Computing
Adiabatic Quantum Computation
MULT90063 Lecture 21

MULT90063 Introduction to Quantum Computing
In this lecture we will cover/review
– Quantum Adiabatic Processes – The problem Hamiltonian
– Avoided crossings and energy gap – The adiabatic theorem

MULT90063 Introduction to Quantum Computing
D-Wave systems
D-Wave Systems
– 2000 qubit quantum “annealers”
– Sold quantum computers to Lockheed Martin, Google, NASA, Los Alamos
National Laboratory ($15 million each)

MULT90063 Introduction to Quantum Computing
Review: 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
We have seen in previous lecture how to map these onto QUBO problem Hamiltonians.

MULT90063 Introduction to Quantum Computing
Adiabatic Processes
– Start In the known ground state of a simple Hamiltonian
– Slowly change the Hamiltonian to the problem Hamiltonian
– Provided the change has been “slowly enough” the system will
remain in the ground state, and we will have found the ground state of the problem Hamiltonian.
H(s)=(1s)Hx +sHp 0s1 s = t/T
Bad analogy: Moving a glass full of water slowly enough means that you keep the water in the glass. If you move it too fast all the water slops out.
Note: Quantum adiabatic process is not the same as thermodynamic adiabatic process (Q=0)

MULT90063 Introduction to Quantum Computing
Hamiltonian of transverse field
Eg. Three electrons in a transverse field:
Hx / Bx X Xi i
Hx =gμBBx(X1 +X2 +X3) We call this the transverse Hamiltonian, Hx.
Transverse field Hamiltonian

MULT90063 Introduction to Quantum Computing
Problem Hamiltonian
We have seen many examples of problem Hamiltonians in our discussions of QUBO Problems. Two-body because that’s what nature gives us.
Eg. Number partitioning for the set {1, 2, 3}: 2
H = 4Z1Z2 + 6Z1Z3 + 12Z2Z3 + 14I Finding minimum energy state will solve the problem!
We call this the problem Hamiltonian, Hp.

MULT90063 Introduction to Quantum Computing
Quantum “Annealing”
Definition according to Google:
Annealing: heat (metal or glass) and allow it to cool slowly, in order to remove internal stresses and toughen it. “Copper tubes must be annealed after bending or they will be brittle”
H(s) = (1s)Hx +sHp
Transverse field plays the role of temperature. Causes excitations, strength is slowly being lowered.
Problem Hamiltonian defines the energy landscape of the problem we want to solve.

MULT90063 Introduction to Quantum Computing
Example: Just one Qubit
H(s) = (1s)Hx +sHp s = t/T
System is originally in the state:
Hx = X Hp = Z
“Landau-Zener” avoided crossing
System ends up in Time the state:

MULT90063 Introduction to Quantum Computing
Two qubit example
H(s) = (1s)Hx +sHp |++i
Hp = Z1Z2 + Z1 Hx = X1 + X2

MULT90063 Introduction to Quantum Computing
More complicated problem Hamiltonians
Avoided crossing, Energy gap

MULT90063 Introduction to Quantum Computing
Adiabatic Theorem
How slowly is slowly enough? Adiabatic criterion.
Time derivative of Hamiltonian
m, nth element
Energy of eigenstates: n is the ground state, m is every other state
X ~|hm|H ̇ |ni| = X ~hm|n ̇i ⌧ 1
|En Em|2 En Em m6=n m6=n

MULT90063 Introduction to Quantum Computing
Roughly speaking…
X ~|hm|H ̇ |ni| = X ~hm|n ̇i ⌧ 1
|En Em|2 En Em m6=n m6=n
For ground state, largest contribution from the smallest two eigenvalues. En-Em
|En Em| > Energy gap between ground state and first
For our linear schedule:
Time required scales inversely proportional to the gap:
excited Eigenstate
H ̇ m n ⇡ H m n T
For a given problem: How big is the gap? Difficult to work out in general!

MULT90063 Introduction to Quantum Computing
Energy gap
Energy gap

MULT90063 Introduction to Quantum Computing
Quantum Tunneling
When might AQC give an advantage?
Classical path requires energy to go over the peaks
Quantum path tunnels
Quantum annealing has been shown to outperform classical annealing in the case where the barriers are high, but thin.
Configuration

MULT90063 Introduction to Quantum Computing
Equivalent of Grover’s algorithm
Roland and Cerf demonstrated that AQC could be used to implement an unordered search:
NX1 |i = pN i=0 |ii
Marked state, m
Optimization, since the energy spectrum is known:
Change Hamiltonian faster when the gap is larger, faster when it is smaller.
O(pN) speedup as Grover’s algorithm.
Hx =I2|ih| Hp =I2|mihm|
This achieves the same

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
Adiabatic from Start to Finish
(1) Map computational problem to QUBO/Hamiltonian
(2) Embed problem on physical architecture
(3) Execute the adiabatic algorithm
(4) Read the ground state configuration for the answer to the

MULT90063 Introduction to Quantum Computing
MAX-Cut Problem
Partition the nodes into two disjoint subsets (not necessarily with equal numbers of nodes in each!) so that there is the maximum number of edges between the two subsets.

MULT90063 Introduction to Quantum Computing
Graph Partitioning to QUBO
|x1i |x2i |x3i |x4i |x5i Qubits are |0i if they’re in subset 0, |1i if they’re in subset 1

MULT90063 Introduction to Quantum Computing
Map Problem to QUBO/Hamiltonian
Hamiltonian which counts the edges between subsets:
Score -1 if edges are in different subsets Score 0 if the edges are in the same subset
Most edges between subsets will have the minimum energy. Ground state gives the answer to the MAX-CUT problem.
H = X ZiZj I i,j2E 2

MULT90063 Introduction to Quantum Computing
Map QUBO to Hamiltonian
In our case:
H = X ZiZj I i,j2E 2
H = Z1Z2 I + Z2Z3 I + Z3Z4 I + 222
Z4Z5 I + Z5Z1 I + Z2Z4 I 222

MULT90063 Introduction to Quantum Computing
Map QUBO to Hamiltonian

MULT90063 Introduction to Quantum Computing
Embed on Physical Architecture
Let’s imagine that our quantum computing architecture was made up of a square pattern:
Actual architecture
Problem we want to embed

MULT90063 Introduction to Quantum Computing
Embed on Physical Architecture
Let’s imagine that our quantum computing architecture was made up of a square pattern:
3 1/2 2 1/2 1 1 -2 1/2 1/2 2
3 1/2 4 1/2 5 3
Problem we want to embed
Actual architecture

MULT90063 Introduction to Quantum Computing
Execute algorithm
At this point you would program the couplings into your physical quantum computer, and physically perform the annealing schedule:
In our case, we will enter the couplings in our MATLAB environment
H(s)=(1s)Hx +sHp s = t/T

MULT90063 Introduction to Quantum Computing
Energy for our MAX-CUT example
Prepare in |i⌦5 state
In ground state,
solving computational problem

MULT90063 Introduction to Quantum Computing
Read Ground State configuration
After the adiabatic evolution we read the state of the quantum computer. Provided we have changed our Hamiltonian slowly enough, we will be in the ground state:

MULT90063 Introduction to Quantum Computing
MATLAB environment in the lab

MULT90063 Introduction to Quantum Computing
Lecture 21
Adiabatic Quantum Computing
Lecture 22
Optimisation
Adiabatic quantum computation

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts