程序代写 MULT90063 Introduction to Quantum Computing

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

Further quantum algorithms – HHL algorithm
Adiabatic Quantum Computation

MULT90063 Introduction to Quantum Computing
Solving Linear Equations Lecture 22

MULT90063 Introduction to Quantum Computing
This lecture we will introduce our final quantum computing algorithm for the course:
– Solving Linear Equations
– Mapping Linear Equations to a Quantum Computer
– Solving them: The HHL Algorithm
Introduction paper: https://arxiv.org/pdf/1802.08227.pdf

MULT90063 Introduction to Quantum Computing
Solving Linear Equations is Ubiquitous!
So many areas of application:
– Engineering (eg. Electronics, civil engineering)
– Defence (eg. Radar)
– Science (Least squares optimization, ODE solving…)
– Machine learning, control theory
– … so many more

MULT90063 Introduction to Quantum Computing
Linear Equations
2x + y = 5 x 2y = 0
What is the solution for x and y?

MULT90063 Introduction to Quantum Computing
Solving Linear Equations
Write as a matrix equation:
In our case:
Can solve by row reduction, or by finding the inverse of A. We will find the inverse of A.
2 1 x=5 12 y 0

MULT90063 Introduction to Quantum Computing
Calculating Matrix Inverse Using Eigenvalues
We would like to invert the matrix A:
To find the eigenvalues, we will first write the characteristic equation:
And find the roots:
A=21 1 2
|AI|= 2 1 1 2
2 5 = 0 p )= 5

MULT90063 Introduction to Quantum Computing
Matrix and Matrix Inverse
A = V DV †
D=1 0 D1=1 0 11
Inverse of A is
A1 =VD1V†
Change back
Change to eigenbasis
AA1 =VDV†VD1V† = V DD1V †

MULT90063 Introduction to Quantum Computing
Eigenvalues to Inverse
We can find the corresponding eigenvectors (exercise for you!):
1 =p5, u1 = 2p5 1
2 =p5, u2 = 2+p5 1
Based on the previous slide we can find the inverse:
A1 =VD1V†
A1=12 1 5 1 2

MULT90063 Introduction to Quantum Computing
Invert the matrix
So in our case:
Ax = b A1Ax = A1b
x=1215 5 1 2 0
And we’ve solved the linear equations. The HHL quantum algorithm works in a similar way on a quantum computer.

MULT90063 Introduction to Quantum Computing
Steps for solving classically
1) Write as a matrix
2) Find eigenvalues of the matrix, A
3) Use eigenvalues to invert matrix, A-1 4) Apply A-1 to b

MULT90063 Introduction to Quantum Computing
HHL Algorithm
Phys. Rev. Lett. vol. 15, no. 103, pp. 150502 (2009) arxiv.org 0811.3171

MULT90063 Introduction to Quantum Computing
HHL Algorithm

MULT90063 Introduction to Quantum Computing
Structure of the HHL Algorithm
Prepare initial state
Calculate eigenvalues of A
Invert eigenvalues
Uncompute eigenvalues of A
Result is solution vector as a state

MULT90063 Introduction to Quantum Computing
Initial State
|xi Set up a quantum state represented by the normalized vector “b”. In our example:
b =  50
Input might be a superposition, and possibly difficult to prepare!
|bi= 10 =|0i

MULT90063 Introduction to Quantum Computing
Final State
Output is a quantum state representing the normalized vector “x”. In our example: 1  2 Corresponds to  2
|xi=p5 1 x= 1 Warning: Output is as a superposition.

MULT90063 Introduction to Quantum Computing
Calculate the Eigenvalues of A
Prepare initial state
Calculate eigenvalues of A
Invert eigenvalues
Uncompute eigenvalues of A
Result is solution vector as a state

MULT90063 Introduction to Quantum Computing
Calculate the Eigenvalues of A
Looks a lot like Shor’s algorithm/Simon’s algorithm which we have seen previously:
– Initial equal superposition
– Application of some function, in this case UA
– Inverse QFT

MULT90063 Introduction to Quantum Computing
UA = exp(iAt)
How to exponentiate a general A as a circuit? One way if A is Hermitian:
– Break up as Pauli matrices
– Use Trotter!
t is the state of the control qubit!
In our case:
A=21 1 2

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:
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 linear combination of Pauli matrices:
For example:
H = XEii i
H = B1X1 + B2X2 + J12Z1Z2
Ei = Tr[iH] d

MULT90063 Introduction to Quantum Computing

But what if you do want to create the gate:
We might try:
exp(A + B) ⇡ exp(A) exp(B)
e x p ( A + B ) ⇡ e x p ✓ A2 ◆ e x p ✓ B2 ◆ e x p ✓ A2 ◆ e x p ✓ B2 ◆
e x p ( A + B ) ⇡ ✓ e x p ✓ An ◆ e x p ✓ Bn ◆ ◆ n
This is called the Trotter (sometimes Trotter-Suzuki) approximation – useful!
exp(A + B)

MULT90063 Introduction to Quantum Computing
If A is not Hermitian
If A is not Hermitian, can make it Hermitian:
A0=0 A A† 0

MULT90063 Introduction to Quantum Computing
Step by Step
Initially, the state is:
| i = |0i|0i|bi

MULT90063 Introduction to Quantum Computing
Step by Step
After the Hadamard gates the “t” register is in an equal superposition:
| i = pN t=0 |0i|ti|bi

MULT90063 Introduction to Quantum Computing
Step by Step
We then apply the UA gate:
| i = pN t=0 |0i |ti exp(iAt) |bi
Angle depends on the “t” register.

MULT90063 Introduction to Quantum Computing
Step by Step
Applying IQFT extracts the eigenvalue:
| i = UIQF T pN t=0 |0i exp(ibt) |ti |bi
= |0i | ̃bi |bi
Giving an approximation to the Eigenvalue in the “t” register.

MULT90063 Introduction to Quantum Computing
Superposition of Eigenstates
If, instead of a single Eigenstate, b was made up of a superposition of Eigenstates of A:
|bi = Xbi |uii i
Then so too, after performing the algorithm, would we be in a superposition of states:
| i = Xbi |0i| ̃ii|uii i
What we want is the solution, which depends on quantities we have calculated:
|xi=Xbi |uii i i
How can we reduce each amplitude bi by a factor of λ? This is not even unitary!

MULT90063 Introduction to Quantum Computing
Inverting the Eigenvalues
The t register contains register contains the eigenvalue. Based on this register we can make a controlled rotation on the ancilla qubit to obtain the state (of the ancilla register):
We now measure. If we obtain the state 0, we redo the algorithm (“post-select”) until we have measured the 1 state. X ̃
s 1 ̃ 2 | 0 i + ̃ | 1 i
Initially the state is: Becomes:
| i =s bi |0i |ii |uii 0i1
X@ C2 CA ̃
bi 1 ̃2 |0i+ ̃ |1i |ii|uii i
✓ = 2 cos1

MULT90063 Introduction to Quantum Computing
Applied to our state
After rotation, R:
0s 1 X@ C2 CA ̃
| i = Xbi |0i| ̃ii|uii i
bi 1 ̃2 |0i+ ̃ |1i |ii|uii | i = X b C | 1 i | ̃ i | u i
And after post-selecting based on measuring the state 1,
Badly normalized:
| i = b i | 1 i | ̃ i i | u i i i ̃

MULT90063 Introduction to Quantum Computing
“Uncompute” the Eigenvalues
Prepare initial state
Calculate eigenvalues of A
Invert eigenvalues
Uncompute eigenvalues of A
Result is solution vector as a state

MULT90063 Introduction to Quantum Computing
Invert the eigenvalues
From our state: X bi ̃
| i = ̃ | 1 i | i i | u i i
We apply the opposite procedure which we used to calculate the eigenvalues. This resets them to the zero state:
| i = X bi |1i|0i|uii i ̃
Compare to the solution:
|xi = i |uii

MULT90063 Introduction to Quantum Computing
Obtain solution
Obtain an approximation to the solution:
| x ̃ i = X b i | u i i i ̃
Notice this is as a superposition, so we are left with a state whose vector represents the answer to the problem. Completely determining this state, in itself can be a costly exercise, potentially requiring an exponentially large number of measurements. However it can be used in other ways, such as for calculating average energy, or as an input to another such function.

MULT90063 Introduction to Quantum Computing
Condition Number
The condition number, κ, of a matrix A is given by the ratio of largest to smallest eigenvalues,
κ=λmax/λmin

MULT90063 Introduction to Quantum Computing
Running time
Best general classical algorithm is the conjugate gradient method, with runtime:
O (N s log(1/✏)) HHL algorithm has runtime:
O log(N)s22/✏
Where N is the dimension of the matrix
s is the sparsity, κ is the condition number of A, and ε is the error

MULT90063 Introduction to Quantum Computing
– HHL algorithm solves systems of linear equations
– Need a method for emulating exp(iAt)
– Can be used as a quantum subroutine
– Has a runtime, exponentially faster than classical versions.

MULT90063 Introduction to Quantum Computing
Lecture 21
Adiabatic Quantum Computation
Lecture 22
– Further quantum algorithms – HHL algorithm
Adiabatic Quantum Computation

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

Related Posts