[PYTHON] Follow the flow of QAOA (VQE) at the source code level of Blueqat

QAOA and VQE

QAOA (Quantum Approximate Optimization Algorithm) is an algorithm that optimizes the singing model using a quantum gate type quantum computer. VQE (Variational Quantum Eigensolver) is an algorithm for finding the eigenvalues of a matrix using a quantum gate type quantum computer, and is often used for quantum chemical calculations.

In recent years, QAOA and VQE have been actively developed because they work reasonably well on quantum computers without error correction.

At the quantum computer library level, QAOA is often treated as a type of VQE, and Blueqat also treats QAOA as a type of VQE.

The problem you want to solve with VQE / QAOA

Given a matrix $ \ hat H $ called the Hamiltonian. For this matrix, $ \ boldsymbol {X, which is a vector of norm 1 and has the smallest $ \ boldsymbol {X} \ cdot \ hat H \ boldsymbol {X} $ (where $ \ cdot $ is the inner product) When looking for} $, VQE / QAOA can solve the problem of what the value of $ \ boldsymbol {X} \ cdot \ hat H \ boldsymbol {X} $ is. Depending on the shape of the Hamiltonian and the purpose of solving the problem, it is called QAOA or VQE.

Also, $ \ boldsymbol {X} \ cdot \ hat H \ boldsymbol {X} $ is also called "energy". This is because in quantum mechanics, this actually corresponds to the equation for energy.

If this can be solved efficiently

--Some kind of optimization problem can be dropped into this form, so it can be used to solve the optimization problem. ――QAOA is close to here as a motivation --Such $ \ boldsymbol {X} $ is the eigenvector of the matrix $ \ hat H $, and $ \ boldsymbol {X} \ cdot \ hat H \ boldsymbol {X} $ is the smallest eigenvalue of $ \ hat H $. Is known to be, so it can be used to solve so-called eigenvalue problems. ――VQE is close to here as a motivation ――In quantum chemistry, I am very happy to be able to solve the eigenvalue problem. --You can find the electron configuration that minimizes the energy.

There are applications such as.

Rough flow of VQE

Quantum computers are good at creating huge matrices, multiplying them by vectors called qubits, and sampling bit strings according to the resulting probability distribution.

A quantum computer is roughly a device that operates a "quantum circuit" made by combining quantum gates. If you pass a quantum circuit, it will sample the bit string.

Since $ \ boldsymbol {X} \ cdot \ hat H \ boldsymbol {X} $ can be obtained from the sampling result of the bit string, the quantum circuit is passed to the quantum computer while changing the quantum circuit little by little, and $ \ Find a quantum circuit that minimizes boldsymbol {X} \ cdot \ hat H \ boldsymbol {X} $.

If you want it

-Minimum value of $ \ boldsymbol {X} \ cdot \ hat H \ boldsymbol {X} $ -Probability distribution of measurement result (bit string) of $ \ boldsymbol {X} $ such that $ \ boldsymbol {X} \ cdot \ hat H \ boldsymbol {X} $ is minimized

Can be obtained.

While changing the quantum circuit little by little?

Some quantum gates correspond to the "rotate qubit" operation. By having the rotation angle as a parameter, it is possible to create a quantum circuit according to the parameter.

Since the angle is just a floating point value, Parameters (floating point type) → Quantum circuit → Bit string sampling result → Energy (floating point type) You can think of it as a function that returns a floating-point type if you give it a floating-point type.

By minimizing this function, you will get the result you want. Often, scipy.optimize.minimize is used for these optimizations. Bayesian optimization may also be used.

Circumstances peculiar to quantum computer simulator

In the actual quantum computer, the bit string was obtained by sampling (by calculating the same quantum circuit many times and taking the result many times). This is because the internal state of the quantum computer (sometimes called the state vector, wave function, etc.) cannot be extracted as it is.

On the other hand, in the case of a simulator, since the internal state is stored as an array, it can be extracted as it is, and the probability distribution of the bit string can be obtained more efficiently than calculating the same quantum circuit many times.

When reading VQE and QAOA papers, it is very important to consider whether it is a simulator or an actual machine, because it affects not only the calculation speed but also the calculation accuracy.

Try to make a picture

In other words, this is what it is.

Write with Blueqat

In QAOA, the Hamiltonian is described using only what is called the Z-ZZ interaction, similar to the Ising model solved by quantum annealing.

As a simple QUBO, consider q (0) ―― 2 * q (1) ―― 3 * q (0) * q (1). Let q (0) and q (1) be the qubits, and consider which combination takes the values 0 and 1, respectively, to minimize this equation. If it is 2 variables, you can brute force by hand calculation

Therefore, the minimum value is taken at (1, 1). To ask for this

from blueqat.pauli import qubo_bit as q
from blueqat.vqe import Vqe, QaoaAnsatz

h = q(0) - 2 * q(1) - 3 * q(0) * q(1)

ansatz = QaoaAnsatz(h, 4) #The second argument is how much to increase the parameters and circuits. The more you have, the higher the probability of solving, but it takes time to solve
runner = Vqe(ansatz)
result = runner.run()
print(result.most_common())

And the result is

(((1, 1), 0.944590105656669),)

And, (1, 1) was obtained with a probability of 94% or more.

Read the source

qubo_bit Omit the docstring. qubo_bit is just like this.

def qubo_bit(n):
    return 0.5 - 0.5*Z[n]

This is a rewrite of what was written in bits of QUBO ($ q_i \ in \ {0, 1 \} ) into the Ising model (\ sigma_i \ in \ {\ pm 1 \} $) I'm just there. It is calculated so that $ \ sigma_i = 1 $ when $ q_i = 0 $ and $ \ sigma_i = -1 $ when $ q_i = 1 $.

Z is defined as messy in blueqat.pauli, but when used for VQE or QAOA,

--The Z [i] is used as it is, or it is multiplied by a coefficient or other Z [i] to make it a Term type. --Furthermore, add and subtract the Term type to the ʻExpr` type.

Will be used. Also,

--ʻExprtype is made ofTermtuple --TheTermtype is made up of tuples and coefficients (float or complex) of Pauli matrices X, Y, Z. --TheTerm` type provides a function for adding a calculation called" time evolution "to a quantum circuit.

It has become a relationship.

Time evolution is a very important calculation in VQE and QAOA. Actually, I would be happy if I could write the time evolution of Hamiltonian $ \ hat H $, so I would like to evolve the ʻExprtype over time, but it is generally difficult to write it with a combination of gates, and usually it is an approximate calculation by Suzuki Trotter expansion etc. Will be done. On the other hand, theTerm` type, which consists only of multiplication, can easily evolve in time by combining gates.

QaoaAnsatz.__init__

Ansatz is a German word that seems to be translated as "temporary" in Japanese, but it is a candidate for $ \ boldsymbol {X} $ in $ \ boldsymbol {X} \ cdot \ hat H \ boldsymbol {X} $. In VQE, it is quite possible to call a quantum circuit that is a candidate for $ \ boldsymbol {X} $ in this way. As we will see later, the most important method in QaoaAnsatz isget_circuit (), which is responsible for creating quantum circuits from parameters.

class QaoaAnsatz(AnsatzBase):
    def __init__(self, hamiltonian, step=1, init_circuit=None):
        super().__init__(hamiltonian, step * 2)
        self.hamiltonian = hamiltonian.to_expr().simplify()
        if not self.check_hamiltonian():
            raise ValueError("Hamiltonian terms are not commutable")

        self.step = step
        self.n_qubits = self.hamiltonian.max_n() + 1
        if init_circuit:
            self.init_circuit = init_circuit
            if init_circuit.n_qubits > self.n_qubits:
                self.n_qubits = init_circuit.n_qubits
        else:
            self.init_circuit = Circuit(self.n_qubits).h[:]
        self.init_circuit.make_cache()
        self.time_evolutions = [term.get_time_evolution() for term in self.hamiltonian]

#Of the parent class__init__Click here
class AnsatzBase:
    def __init__(self, hamiltonian, n_params):
        self.hamiltonian = hamiltonian
        self.n_params = n_params
        self.n_qubits = self.hamiltonian.max_n() + 1

What to pass to the parent class __init__ is hamiltonian ($ \ hat H $), the number of parameters, and the number of qubits. The number of parameters is passed twice the number of steps.

In addition, hamiltonian is forced to match the type withhamiltonian.to_expr (). Simplify (), andsimplify ()is used to remove or combine extra terms.

check_hamiltonian checks if it is a Hamiltonian suitable for QAOA.

As an initial circuit, unless otherwise specified, all qubits multiplied by H are passed. This is equivalent to starting annealing from the state where a lateral magnetic field is first applied, as it is called in quantum annealing.

If you call make_cache (), some simulators will perform quantum computation up to this stage and save the result. From now on, I will move the initial circuit with a gate added, so by doing this, unnecessary calculations can be reduced. self.time_evolutions = [term.get_time_evolution () for term in self.hamiltonian] extracts the Term type term from the Expr type hamiltonian to get the function for time evolution. I will.

Vqe.__init__

class Vqe:
    def __init__(self, ansatz, minimizer=None, sampler=None):
        self.ansatz = ansatz
        self.minimizer = minimizer or get_scipy_minimizer(
            method="Powell",
            options={"ftol": 5.0e-2, "xtol": 5.0e-2, "maxiter": 1000}
        )
        self.sampler = sampler or non_sampling_sampler
        self._result = None

Takes three objects: ʻansatz, minimizer, sampler. If you omit minimizer and sampler, the default ones will be used. minimizer is a function for minimization, and by default, it is a wrapping of scipy.optimize.minimize. sampler` is a function to run the actual machine or simulator and obtain sampling results, and the simulator is used by default.

If you put these in the previous figure, it will be as follows. I omitted it because the figure becomes complicated, but ansatz also calculates the energy from the sampling result. (Because we need hamiltonian for energy calculation, we let the object that has hamiltonian do it)

Vqe.run()

    def run(self, verbose=False):
        objective = self.ansatz.get_objective(self.sampler)
        if verbose:
            def verbose_objective(objective):
                def f(params):
                    val = objective(params)
                    print("params:", params, "val:", val)
                    return val
                return f
            objective = verbose_objective(objective)
        params = self.minimizer(objective, self.ansatz.n_params)
        c = self.ansatz.get_circuit(params)
        return VqeResult(self, params, c)

ʻIf verbose:` The following is just a mess for those who want to see the parameters and energy changes, so don't worry too much, if you ignore it

--Get the objective function with get_objective (sampler) --Call minimizer to minimize the value of the objective function --Create a circuit from the parameters obtained as a result of minimization and produce the result.

It is a simple process.

get_objective

    def get_objective(self, sampler):
        """Get an objective function to be optimized."""
        def objective(params):
            circuit = self.get_circuit(params)
            circuit.make_cache()
            return self.get_energy(circuit, sampler)
        return objective

The objective function is exactly as it is done in the figure

--Receive the parameter params and create a quantum circuit --Move the quantum circuit with sampler to get energy

It has become a flow.

For the objective function obtained in this way, the parameters are optimized by minimizer, so it turns out that it really works as shown in the figure.

Summary

VQE and QAOA are not complicated algorithms as long as you can understand the flow. This time, I tried to write in the figure while reading the source how it actually works.

Bonus: Problems with the current Blueqat VQE module

I made the module to delegate authority to the child class as much as possible so that it would be as loosely coupled as possible. However, the key to VQE is "how to optimize the parameters". Especially in chemical calculations, the parameters obtained from the molecular structure can be used as the initial values, and optimization is performed using whatever can be used. I want to do.

It's a very incompatible idea with the current structure of VQE modules.

Currently, minimizer is not given any information about what function to optimize, other than the function itself and the number of parameters. The content of the function is optimized as a black box.

How can I reassemble the module for better optimization? (For now, instead of passing the minimizer from the outside, I'm thinking of inheriting the Vqe object and using it as a method.)

There is also a problem interacting with the sampler. In the current sampler, it was assumed that each circuit would work, but in fact, with IBM Q, multiple circuits can be packed and thrown to a quantum computer on the cloud. In IBM Q, it is normal that the waiting time is longer than the calculation time, and being able to pack and execute multiple circuits saves a lot of time. So how can we make it so that multiple circuits can be packed together? (I just get a list of circuits, run them all together and return a list of results, etc.)

Blueqat has a lot of worries about software development, rather than worries about crappy quantum computing. It's open source software, so I'm looking for someone to help with the development. If you are confident in your skills, please let us know.