review : reading the paper on QAOA combinatorial optimization algorithm on Google’s sycamore processor.

Google published a paper on quantum computing on April.

https://arxiv.org/pdf/2004.04197.pdf

Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor

Google AI Quantum and Collaborators∗ (Dated: April 10, 2020)

This paper shows the result of experiment on actual quantum computer with combinatorial optimization problem.

QAOA

Quantum Approximate optimization algorithm is an algorithm for NISQ quantum computer. NISQ is a shor name of Noisy Intermediate Scale Quantum, which has errors and small number of qubits. QAOA is optimized the quantum circuit to work on these kind of near term devices.

Quantum Annealing

Quantum annealing is an algorithm to simulate the annealing process with quantum effect. Basically we use quantum adiabatic process and prepare two hamiltonians. One is the hamiltonian to solve as cost function and another is the driver/mixer to define how to search the answer.

Quantum annealing is using transverse field ising model and using X for the initial hamiltonian on each qubit.

The initial state corresponding to the initial hamiltonian X is |+> state and this is first prepared with H gate or rotation gate on the quantum circuit.

Eigenvalue and Variational principle

To solve combinatorial optimization, the quantum circuit solve the eigenvalue problem with provided cost hamiltonian H.

And to solve this with numerical optimization, the variational principle applied on the expectation value of H. The variational principle shows the minimum lower limit of the expectation value of hamiltonian H as the eigenvalue E0.

NISQ hybrid algorithm

NISQ has a lot of error and not possible to get a good result from a long quantum circuit.

The process is first we do a calc on quantum circuit and get the result from probability distribution. and then get the expectation value of hamiltonian.

And the optimize it. Because the minimum limit of expectation value is defined by the variational principle we can get closer value to the minimum state. Usually gradient descent algorithm is used to optimize the value of expectation value.

NISQ and Hermitian matrix

The cost function of hamiltonian is written in Hermitian matrix. Usually to solve the problem, trotter decomposition is used. But this decomposition need a long depth of quantum circuit to run. For NISQ variational algorithm, short circuit is used.

The Hermitian matrix will be decomposed into a sum of Unitary matrix. And each unitary matrix of hamiltonian of expectation value is acquired independently from the trial of quantum circuit.

Time evolution operator

To do quantum adiabatic process on quantum circuit, we use time evolution. This operator changing the quantum state according to the hamiltonian.

This time the hamiltonian is written in X and ZZ form. Hamiltonian will be converted into the form of rotation gate by the diagonalization.

The diagonalization will be done with converting the hamiltonian with some rotation gate and finally converted into the arbitrary rotation gate with angles.

Finally the angle is defined as the time, but this time we use variational method and not using the exact time evolution. The angle will be a simple parameter to be adjusted.

We just use simply theta for the angle.

Ansatz

We cannot solve every problem on eigenvalue problem efficiently. Only some sort of problem like chemistry or adiabatic calc can be solved. Because we need Ansatz which is an efficient quantum circuit to find the answer.

QAOA ansatz is written with cost function (pink) and driver/mixer hamiltonian (blue RX).

H gate is corresponding to RX operator which makes |+> state as the eigenstate or X hamiltonian.

Let’s look at the Google’s paper

The Google’s paper is very well written. We can easily understand the process and the result.

The model

On the paper 3models are shown.

from: https://arxiv.org/pdf/2004.04197.pdf

The first one is the actual ladder shape of sycamore processor. 2D graph based shape.

The second one is 3-regular maxcut and it has maximum 3 connection to the neighbor nodes.

The last one is SK model of full connection.

The last figure d shows the ansatz. |+> is prepared and blue is the cost function part and red is the X hamiltonian part of transverse-field. “p” is the step of the adiabatic process to simulate the quantum annealing.

The adiabatic process is analogue, besides QAOA is a digital step. And we need to discritize the step. “p” is the number of digitized step. Generally if the p is bigger the result will be better.

The cost hamiltonian

from: https://arxiv.org/pdf/2004.04197.pdf

The cost is written with ZZ which each expectation value is +1 or -1. w is weight and takes -1 or +1.

The time evolution / parameterized hamiltonian

from: https://arxiv.org/pdf/2004.04197.pdf

The time evolution of hamiltonian C is like above.

from: https://arxiv.org/pdf/2004.04197.pdf

And the driver hamiltonian X is also written in the form of time evolution.

from: https://arxiv.org/pdf/2004.04197.pdf

Finally QAOA will be done start from eigen state of initial hamiltonian X and then apply parameterized adiabatic process.

The network connection

The hardware qubit location is 2D grid. But for each combinatorial optimization problem they need much more connection. Google’s sycamore processor, they are doing a technique using swap network and combining a new gate set of SYC with arbitrary 1qubit rotation. This set realize the swap and time evolution of ZZ at the same time. And finally realize a full connection of network using swap.

from: https://arxiv.org/pdf/2004.04197.pdf

SYC gate is also called fsim gate and combination of iswap dagger and controlled phase gate.

Optimization process using gradient descent

The paper also shows the process to optimize the process of variational hybrid algorithm.

The blue star shows the local/global minimum. And we can see the calculation process start from red square to the final state of red point finally going the minimum state.

from: https://arxiv.org/pdf/2004.04197.pdf

The result

The result is very simple.

from: https://arxiv.org/pdf/2004.04197.pdf

The result on the paper is very simple. The square is the ideal simulation without noise. The SK model with full connection is going to random with 17qubits. Hardware grid is not bad. It is doing a similar scale out as the simulation.

It is showing what we can do with actual machine. We can learn a lot of things from this paper.

Let’s enjoy quantum life!