# Adiabatic evolution for solving an Exact Cover problem#

Code at: https://github.com/qiboteam/qibo/tree/master/examples/adiabatic3sat

## Introduction#

Adiabatic quantum computation aims to reach the ground state of a problem Hamiltonian encoding the solution of a hard problem, by adiabatically evolving a system from the ground state of a known, easy to prepare, Hamiltonian to the problem Hamiltonian.

An Exact Cover instance of a 3SAT problem is characterized by a set of clauses containing 3 bits that are considered satisfied if one of them is in position 1, while the other remain at 0. The solution of this instance is bitstring that fulfils all the clauses at the same time.

## Adiabatic evolution#

Adiabatic computation deals with finding the ground state of a Hamiltonian that encodes the solution of a computational problem. This has to be mapped to the time dependent Hamiltonian in the form

where H_0 and H_p are the initial and problem Hamiltonian respectively, and s(t) defines the schedule that the adiabatic evolution follows. How fast this evolution can be performed depends on the minimum gap energy of the system during the evolution, that is the difference of energy between the ground state and the first excited state along the schedule. The smaller the gap energy the slower the evolution has to be.

The initial Hamiltonian used in this example is the following,

which has a ground state of the equal superposition of all possible computational states.

As for the problem Hamiltonian that encodes the solution of an Exact cover problem, first we define the operator

that can be used to create a Hamiltonian with a ground state when the Exact Cover clause is satisfied. This clause Hamiltonian reads

where the indices i, j, k represent the three different qubits that the particular clause addresses. After this is defined, the problem Hamiltonian only needs to add up all clause Hamiltonians, so that the only state that remains at 0 energy will be the one that fulfils at the same time

## How to run the example?#

Run the file `main.py`

from the console to perform an adiabatic evolution for an instance of 8 qubits.

The program supports the following basic arguments:

`--nqubits`

(int) allows for instances with different number of qubits (default=8).`--instance`

(int) choose instance to use (default=1).`--T`

(float) set the total time of the adiabatic evolution (default=10).`--dt`

(float) set the interval of the calculations over the adiabatic evolution (default=1e-2).`--solver`

(str) set the type of solver for the evolution (default=’exp’).`--plot`

add this modifier to output energy and gap plots during the evolution. Capped under 14 qubits due to memory.`--trotter`

add this modifier to perform the trotterization of the Hamiltonian.

The program returns:

The most common solution found after the evolution.

The probability of the most common solution.

`{}_qubits_energy.png`

plots detailing the evolution of the lowest two eigenvalues for {} qubits.**(if enabled)**`{}_qubits_gap.png`

plots detailing the evolution of the gap energy for {} qubits.**(if enabled)**

Initially supported number of qubits are [4, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30], with 10 different instances for qubits 8 and up.

The `main.py`

script uses linear scheduling for the adiabatic evolution by
default. The user may switch the scheduling function to a polynomial of
arbitrary order by passing the following argument:

`--params`

(str) list of float values separated with commas (`,`

) that define the coefficients of the polynomial scheduling. The polynomial is constructed so that it satisfies s(0)=0 and s(T)=T by definition.

It is also possible to optimize the polynomial coefficients using the following arguments:

`--method`

(str) optimization method to use. See the Qibo optimizer documentation for more details on the available optimization methods.`--maxiter`

(int) maximum number of optimization iterations

When an optimization method is given then the given `--params`

are used as the
initial guess for the variational parameters. If no `--params`

are given linear
scheduling is used and only the final time `T`

is optimized.

The functions used in this example, including problem hamiltonian creation are
included in `functions.py`

.

## Create your own instances#

An example of an instance for 4 qubits reads:

```
4 3 1
0 1 0 0
1 2 3
2 3 4
1 2 4
```

The first line includes:

number of qubits

number of clauses

number of 1’s in the solution

The second line is the solution of the instance.

The following lines correspond to the three qubits present in each clause.

Should the solution not be known, leave an empty line in place of the solution as well as remove the number of 1’s in the solution.

## Optimization example#

For demonstration we use `main.py`

to optimize a 3SAT instance with N=10 qubits.
We use a fourth order polynomial as the ansatz for the scheduling and after
optimizing the coefficients and the total evolution time T using
`scipy`

s BFGS method
we find that the optimal values are:
`-3.96837267,0.6582704,1.29674208`

and `T=46.85073995`

.
Executing the script for these parameters we find the correct bitstring
solution `0110000101`

to the 3SAT problem with probability 99%.

In the plot that follows we show the ground and excited state energies for the adiabatic evolution Hamiltonian, as well as the difference between them (gap) and the final form of the optimized scheduling function. We observe that in agreement with what we expect from theory the scheduling is “slower” at the area where the gap is minimum.

Below we plot the probability to measure the correct solution from the final state of the evolution as a function of the total evolution time T. We find that when using the optimized scheduling (fourth order polynomial) the probability reaches 99% within T=50, while for the default linear scheduling T=400 is required to reach the same probability.