common.title
Home

Account

Sign in
Sign up

Service


Company

Overview
Service overview
Terms of service

Privacy policy

Contact
common.title

Internship lecture 3 : QAOA

Yuichiro Minato

2022/09/03 12:54

1

This is the third internship lecture. Finally, we are going to start quantum computation.

Quantum States and State Vectors

Unlike today's computers, the data used in a quantum computer is handled differently: a single qubit is represented using a sphere. A qubit has a |0> state and a |1> state, which can be represented by a vector.

∣0⟩=[10],∣1⟩=[01]\mid 0 \rangle = \begin{bmatrix} 1 \\ 0 \end{bmatrix}, \mid 1 \rangle = \begin{bmatrix} 0 \\ 1 \end{bmatrix}
∣ψ⟩=α∣0⟩+β∣1⟩=α[10]+β[01]=[αβ]\mid \psi \rangle = \alpha \mid 0 \rangle + \beta \mid 1 \rangle = \alpha \begin{bmatrix} 1 \\ 0 \end{bmatrix} + \beta \begin{bmatrix} 0 \\ 1 \end{bmatrix} = \begin{bmatrix} \alpha \\ \beta \end{bmatrix}

The following conditions are satisfied

∣α∣2+∣β∣2=1|\alpha|^2+|\beta|^2 = 1

∣ψ⟩\mid \psi \rangle is called the state vector (wave function) and represents the quantum state of a qubit. The α\alpha and β\beta are complex numbers and are called "amplitudes", and squaring them gives the probability of occurrence of the corresponding computational basis, and ∣α∣2|\alpha|^2 and ∣β∣2|\beta|^2 can be obtained by "measurement".

Polar coordinate representation of quantum states

The Bloch sphere is a notation for representing quantum states on the unit sphere that can be expressed as a superposition of two orthogonal pure states.

vqe2

∣ψ⟩=[cosθ−sinθe−iϕsinθeiϕcosθ][10]=[cosθsinθeiϕ]\mid \psi \rangle = \begin{bmatrix} cos\theta & -sin\theta e^{-i\phi}\\ sin\theta e^{i\phi} & cos\theta \end{bmatrix} \begin{bmatrix} 1\\0 \end{bmatrix} = \begin{bmatrix} cos\theta \\ sin\theta e^{i\phi} \end{bmatrix}

You can also use angle-based parameter notation, such as Remember that quantum data is expressed in terms of angles.

Manipulating state vectors and quantum gates

To manipulate state vectors, quantum gates are used. The basic Pauli gate, arbitrary rotation gate, and Hadamar gate are mainly used in variational algorithms.

There are three types of Pauli gates, XYZ, each of which implies a 180-degree rotation around the XYZ axis in the Bloch sphere, and the corresponding matrices are

X=[0110],Y=[0−ii0],Z=[100−1]X= \begin{bmatrix} 0&1 \\ 1&0 \end{bmatrix} , Y= \begin{bmatrix} 0&-i \\ i&0 \end{bmatrix} , Z= \begin{bmatrix} 1&0 \\ 0&-1 \end{bmatrix}

Also, arbitrary rotation around the XYZ axes is made with the RX, RY, and RZ gates, and

Rx(θ)=[cos⁡(θ2)−isin⁡(θ2)−isin⁡(θ2)cos⁡(θ2)],Ry(θ)=[cos⁡(θ2)−sin⁡(θ2)sin⁡(θ2)cos⁡(θ2)],Rz(θ)=[e−iθ200eiθ2]Rx(\theta) = \begin{bmatrix} \cos\left(\frac{\theta}{2}\right) & -i\sin\left(\frac{\theta}{2}\right)\\ -i\sin\left(\frac{\theta}{2}\right) & \cos\left(\frac{\theta}{2}\right) \end{bmatrix}, Ry(\theta) = \begin{bmatrix} \cos\left(\frac{\theta}{2}\right) & -\sin\left(\frac{\theta}{2}\right)\\ \sin\left(\frac{\theta}{2}\right) & \cos\left(\frac{\theta}{2}\right) \end{bmatrix}, Rz(\theta) = \begin{bmatrix} e^{-i\frac{\theta}{2}} & 0\\ 0 & e^{i\frac{\theta}{2}} \end{bmatrix}

The quantum state can be changed by acting these quantum gates on the state vector.

X[10]=[0110][10]=[01]X \begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 0&1 \\ 1&0 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \end{bmatrix}

The Hadamar gate is a convenient gate that rotates around the XZ axis.

H=12[111−1]H= \frac{1}{\sqrt{2}} \begin{bmatrix} 1&1 \\ 1&-1 \end{bmatrix}

Eigenvalue and eigenvector problems

Various problems can be solved if eigenvalues and eigenvectors for a given matrix can be found. For a given matrix HH (called the Hamiltonian), if the eigenvalues are E0E_0 and the eigenvectors are ∣ψ⟩\mid \psi \rangle.

H∣ψ⟩=E0∣ψ⟩H \mid \psi \rangle = E_0 \mid \psi \rangle

The objective is to find E0E_0 and ∣ψ⟩\mid \psi \rangle such that The ∣ψ⟩\mid \psi \rangle is called the state vector (wave function).

Most quantum computer problems correspond to this eigenvalue problem. We set the problem on the matrix H and look for the eigenvalues E.

Quantum Variational Principle

Finding eigenvalues is the main optimization used in NISQ. We learned how to use numerical optimization on the seconde lecture.

⟨ψ(θ)∣H∣ψ(θ)⟩≥E0\langle \psi (\theta) \mid H \mid \psi (\theta) \rangle \geq E_0

Since it is tough to find the eigenvalues directly, we drop indirectly into an optimization calculation that brings us as close as possible to the expected value of the eigenvalues. Since the Hamiltonian HH is a given expression, all we can do is to find a state vector ∣ψ(θ)⟩\mid \psi (\theta) \rangle as close as possible to the eigenstates as an optimization calculation of the angle is the goal of this project. The search for the state vector is achieved by creating a circuit called ansatz.

Hamiltonian and its expectation value

The Hamiltonian HH is a Hermitian matrix consisting of a Pauli gate XYZ and a unit matrix I. The expected value EE of the Hamiltonian HH, given a certain quantum state ∣ψ⟩\mid \psi \rangle, is obtained by multiplying both of the above equations by ⟨ψ∣\langle \psi \mid from the left

⟨ψ∣H∣ψ⟩=⟨ψ∣E∣ψ⟩⟨ψ∣H∣ψ⟩=E⟨ψ∣ψ⟩⟨ψ∣H∣ψ⟩=E\langle \psi \mid H \mid \psi \rangle = \langle \psi \mid E \mid \psi \rangle\\ \langle \psi \mid H \mid \psi \rangle = E \langle \psi \mid \psi \rangle\\ \langle \psi \mid H \mid \psi \rangle = E

As an example of a single qubit, from any quantum state ∣ψ⟩\mid \psi \rangle and any Hamiltonian HH, we have

⟨ψ∣H∣ψ⟩=[α∗β∗][abcd][αβ]\langle \psi \mid H \mid \psi \rangle = \begin{bmatrix} \alpha^* & \beta^* \end{bmatrix} \begin{bmatrix} a&b\\ c&d \end{bmatrix} \begin{bmatrix} \alpha\\ \beta \end{bmatrix}

Find the expected value of the Hamiltonian Z

The expected value of the Hamiltonian at any state vector when H=ZH = Z is

⟨ψ∣H∣ψ⟩=[α∗β∗][100−1][αβ]=∣α∣2−∣β∣2\langle \psi \mid H \mid \psi \rangle = \begin{bmatrix} \alpha^* & \beta^* \end{bmatrix} \begin{bmatrix} 1&0\\ 0&-1 \end{bmatrix} \begin{bmatrix} \alpha\\ \beta \end{bmatrix} = |\alpha|^2 - |\beta|^2

The expected value of the Hamiltonian HH when H=XH = X is

⟨ψ∣H∣ψ⟩=[α∗β∗][0110][αβ]=α∗β+αβ∗\langle \psi \mid H \mid \psi \rangle = \begin{bmatrix} \alpha^* & \beta^* \end{bmatrix} \begin{bmatrix} 0&1\\ 1&0 \end{bmatrix} \begin{bmatrix} \alpha\\ \beta \end{bmatrix} = \alpha^* \beta + \alpha \beta^*

but this value cannot be obtained by ordinary measurement, so the solution is obtained through a deformation of the Hamiltonian.

Transformation of Hamiltonian

If the Hamiltonian HH is ZZ, we can calculate the expected value, but we cannot find it for X or Y. Therefore, we use a deformation of the Hamiltonian.

X=HZHX = HZH
⟨ψ∣X∣ψ⟩=⟨ψ∣HZH∣ψ⟩=⟨ψ′∣Z∣ψ′⟩\langle \psi \mid X \mid \psi \rangle \\ = \langle \psi \mid HZH \mid \psi \rangle\\ = \langle \psi' \mid Z \mid \psi' \rangle

In the case of Y, this can be handled by transforming the state vector as in

Y=RX(−π/2)ZRX(π/2)Y = RX(-\pi/2) Z RX(\pi/2)
⟨ψ∣Y∣ψ⟩=⟨ψ∣RX(−π/2)ZRX(π/2)∣ψ⟩=⟨ψ′′∣Z∣ψ′′⟩\langle \psi \mid Y \mid \psi \rangle \\ = \langle \psi \mid RX(-\pi/2) Z RX(\pi/2) \mid \psi \rangle\\ = \langle \psi'' \mid Z \mid \psi'' \rangle

These can be used to calculate the expected values by putting the above H and RX gates in the measurement just before the quantum circuit measurement.

Linear Combining

In fact, the Hamiltonian HH is given by the Hermitian matrix, in the form of a unitary matrix sum, which can be decomposed as follows

⟨ψ∣aH1+bH2∣ψ⟩=⟨ψ∣aH1∣ψ⟩+⟨ψ∣bH2∣ψ⟩=a⟨ψ∣H1∣ψ⟩+b⟨ψ∣H2∣ψ⟩\langle \psi \mid aH_1 + bH_2 \mid \psi \rangle \\ = \langle \psi \mid aH_1 \mid \psi \rangle + \langle \psi \mid bH_2 \mid \psi \rangle \\ = a\langle \psi \mid H_1 \mid \psi \rangle + b\langle \psi \mid H_2 \mid \psi \rangle

Let's see an example

H=1.2X0Z2+2.5Z0X1Y2−3.4Z2X1H = 1.2 X_0 Z_2 + 2.5 Z_0 X_1 Y_2 - 3.4 Z_2 X_1

Expectation value is,

⟨ψ∣1.2X0Z2+2.5Z0X1Y2−3.4Z2X1∣ψ⟩=1.2⟨ψ∣X0Z2∣ψ⟩+2.5⟨ψ∣Z0X1Y2∣ψ⟩−3.4⟨ψ∣Z2X1∣ψ⟩\langle \psi \mid 1.2 X_0 Z_2 + 2.5 Z_0 X_1 Y_2 - 3.4 Z_2 X_1 \mid \psi \rangle\\ = 1.2\langle \psi \mid X_0 Z_2 \mid \psi \rangle + 2.5 \langle \psi \mid Z_0 X_1 Y_2\mid \psi \rangle - 3.4 \langle \psi \mid Z_2 X_1 \mid \psi \rangle

can be calculated by doing the calculations individually and finding the sum, as in the example.

Quantum adiabatic computation

Quantum adiabatic calculation is a theory that allows time evolution while keeping the ground state by intermittently changing the state vector.

Let HstartH_{start} be the Hamiltonian of the initial state and HfinalH_{final} be the Hamiltonian of the final problem to be solved, then from the time tt and the overall schedule TT, we have

Htemp=(1−tT)Hstart+tTHfinalH_{temp} = (1-\frac{t}{T})H_{start} + \frac{t}{T}H_{final}

Then T→∞T\rightarrow\infty, the state vector changed in time evolution can follow the instantaneous Hamiltonian, take eigenstates and have eigenvalue.

Htemp∣ψ⟩=E0temp∣ψ⟩H_{temp}\mid \psi \rangle = E_{0temp}\mid \psi \rangle

The time evolution is aquired by,

∣ψt+1⟩=U∣ψt⟩=e−iHt∣ψt⟩\mid \psi_{t+1} \rangle = U \mid \psi_t \rangle = e^{-iHt} \mid \psi_t \rangle

The challenge is where the ground state and the first excited state are closest, but we can keep the ground state by paying attention to the energy difference between E1(t)−E0(t)E_1(t)-E_0(t).

QAOA circuit

QAOA is the time evolution calculation of the above quantum adiabatic calculation applied to a variational algorithm as ansatz.

|0> --H-- --RZZ--RZ-- --RX-- --RZZ--RZ-- --RX--
            |                  |
|0> --H-- --RZZ--RZ-- --RX-- --RZZ--RZ-- --RX--

The overall structure can be divided into two main parts

1.Selecting a mixer determines the initial state
2. create a formulation in QUBO or Z

The second formulation is automatically time evolved.

The leftmost formulation creates the initial eigenstate|+>. The corresponding Hamiltonian X comes out in Rx in the form of a time evolution. Usually the mixer chooses X by default, and H⊗NH^ {\otimes N} is often used to create the corresponding|+> initial state.

Also, CX-Rz-CX (orRZZ) corresponds to the weight of the Hamiltonian in the problem setup, and the next Rz corresponds to the bias of the Hamiltonian.

blueqat's QaoaAnsatz will automatically construct this time evolution ansatz for you if you decide on the Hamiltonian and the number of step divisions. Since the library does the appropriate calculations for us, all we have to do is formulate the Hamiltonian and select the mixer. Let's solve a simple formulation.

Ising Formulation

A physical model called the Ising model is used to solve combinatorial optimization problems. In the Ising model, the problem is usually formulated using up and down spins. The formulation uses Z as the operator, where Z has the expected value of +1 and -1.

H=−Z0−Z0∗Z1H = -Z_0 -Z_0*Z_1

QUBO

Next, we will check QUBO, which is derived from the Hamiltonian Z formulation above and formulated in terms of 0s and 1s. QUBO is a rewriting of the Z formulation, but blueqat has a tool that automatically converts it.

The formulation is

H=2q1−4q0q1H = 2q_1-4q_0q_1
from blueqat import Circuit
from blueqat.utils import qaoa
from blueqat.pauli import qubo_bit as q
from blueqat.pauli import X,Y,Z,I

hamiltonian = 2*q(1)-4*q(0)*q(1)
step = 1

result = qaoa(hamiltonian, step)
result.circuit.run(shots=100)
Counter({'11': 47, '00': 36, '10': 17})

© 2023, blueqat Inc. All rights reserved