Bemerkung

This page was generated from tutorials/optimization/3_minimum_eigen_optimizer.ipynb.

Run interactively in the IBM Quantum lab.

# Minimum Eigen Optimizer¶

## Introduction¶

An interesting class of optimization problems to be addressed by quantum computing are Quadratic Unconstrained Binary Optimization (QUBO) problems. Finding the solution to a QUBO is equivalent to finding the ground state of a corresponding Ising Hamiltonian, which is an important problem not only in optimization, but also in quantum chemistry and physics. For this translation, the binary variables taking values in \(\{0, 1\}\) are replaced by spin variables taking values in \(\{-1, +1\}\), which allows to replace the resulting spin variables by Pauli Z matrices, and thus, an Ising Hamiltonian. For more details on this mapping we refer to [1].

Qiskit provides automatic conversion from a suitable `QuadraticProgram`

to an Ising Hamiltonian, which then allows to leverage all the `MinimumEigenSolver`

such as - `VQE`

, - `QAOA`

, or - `NumpyMinimumEigensolver`

(classical exact method).

Qiskit wraps the translation to an Ising Hamiltonian (in Qiskit Aqua also called `Operator`

), the call to an `MinimumEigensolver`

as well as the translation of the results back to `OptimizationResult`

in the `MinimumEigenOptimizer`

.

In the following we first illustrate the conversion from a `QuadraticProgram`

to an `Operator`

and then show how to use the `MinimumEigenOptimizer`

with different `MinimumEigensolver`

to solve a given `QuadraticProgram`

. The algorithms in Qiskit automatically try to convert a given problem to the supported problem class if possible, for instance, the `MinimumEigenOptimizer`

will automatically translate integer variables to binary variables or add a linear equality constraints as a
quadratic penalty term to the objective. It should be mentioned that Aqua will through a `QiskitOptimizationError`

if conversion of a quadratic program with integer variable is attempted.

The circuit depth of `QAOA`

potentially has to be increased with the problem size, which might be prohibitive for near-term quantum devices. A possible workaround is Recursive QAOA, as introduced in [2]. Qiskit generalizes this concept to the `RecursiveMinimumEigenOptimizer`

, which is introduced at the end of this tutorial.

### References¶

[1] A. Lucas, Ising formulations of many NP problems, Front. Phys., 12 (2014).

## Converting a QUBO to an Operator¶

```
[1]:
```

```
from qiskit import BasicAer
from qiskit.aqua import aqua_globals, QuantumInstance
from qiskit.aqua.algorithms import QAOA, NumPyMinimumEigensolver
from qiskit.optimization.algorithms import MinimumEigenOptimizer, RecursiveMinimumEigenOptimizer
from qiskit.optimization import QuadraticProgram
```

```
[2]:
```

```
# create a QUBO
qubo = QuadraticProgram()
qubo.binary_var('x')
qubo.binary_var('y')
qubo.binary_var('z')
qubo.minimize(linear=[1,-2,3], quadratic={('x', 'y'): 1, ('x', 'z'): -1, ('y', 'z'): 2})
print(qubo.export_as_lp_string())
```

```
\ This file has been generated by DOcplex
\ ENCODING=ISO-8859-1
\Problem name: CPLEX
Minimize
obj: x - 2 y + 3 z + [ 2 x*y - 2 x*z + 4 y*z ]/2
Subject To
Bounds
0 <= x <= 1
0 <= y <= 1
0 <= z <= 1
Binaries
x y z
End
```

Next we translate this QUBO into an Ising operator. This results not only in an `Operator`

but also in a constant offset to be taking into account to shift the resulting value.

```
[3]:
```

```
op, offset = qubo.to_ising()
print('offset: {}'.format(offset))
print('operator:')
print(op)
```

```
offset: 1.5
operator:
SummedOp([
-0.5 * IIZ,
0.25 * IZI,
-1.75 * ZII,
0.25 * IZZ,
-0.25 * ZIZ,
0.5 * ZZI
])
```

Sometimes an `QuadraticProgram`

might also directly be given in the form of an `Operator`

. For such cases, Qiskit also provides a converter from an `Operator`

back to a `QuadraticProgram`

, which we illustrate in the following.

```
[4]:
```

```
qp=QuadraticProgram()
qp.from_ising(op, offset, linear=True)
print(qp.export_as_lp_string())
```

```
\ This file has been generated by DOcplex
\ ENCODING=ISO-8859-1
\Problem name: CPLEX
Minimize
obj: x_0 - 2 x_1 + 3 x_2 + [ 2 x_0*x_1 - 2 x_0*x_2 + 4 x_1*x_2 ]/2
Subject To
Bounds
0 <= x_0 <= 1
0 <= x_1 <= 1
0 <= x_2 <= 1
Binaries
x_0 x_1 x_2
End
```

This converter allows, for instance, to translate an `Operator`

to a `QuadraticProgram`

and then solve the problem with other algorithms that are not based on the Ising Hamiltonian representation, such as the `GroverOptimizer`

.

## Solving a QUBO with the MinimumEigenOptimizer¶

We start by initializing the `MinimumEigensolver`

we want to use.

```
[5]:
```

```
aqua_globals.random_seed = 10598
quantum_instance = QuantumInstance(BasicAer.get_backend('statevector_simulator'),
seed_simulator=aqua_globals.random_seed,
seed_transpiler=aqua_globals.random_seed)
qaoa_mes = QAOA(quantum_instance=quantum_instance, initial_point=[0., 0.])
exact_mes = NumPyMinimumEigensolver()
```

Then, we use the `MinimumEigensolver`

to create `MinimumEigenOptimizer`

.

```
[6]:
```

```
qaoa = MinimumEigenOptimizer(qaoa_mes) # using QAOA
exact = MinimumEigenOptimizer(exact_mes) # using the exact classical numpy minimum eigen solver
```

We first use the `MinimumEigenOptimizer`

based on the classical exact `NumPyMinimumEigensolver`

to get the optimal benchmark solution for this small example.

```
[7]:
```

```
exact_result = exact.solve(qubo)
print(exact_result)
```

```
optimal function value: -2.0
optimal value: [0. 1. 0.]
status: SUCCESS
```

Next we apply the `MinimumEigenOptimizer`

based on `QAOA`

to the same problem.

```
[8]:
```

```
qaoa_result = qaoa.solve(qubo)
print(qaoa_result)
```

```
optimal function value: -2.0
optimal value: [0. 1. 0.]
status: SUCCESS
```

## RecursiveMinimumEigenOptimizer¶

The `RecursiveMinimumEigenOptimizer`

takes a `MinimumEigenOptimizer`

as input and applies the recursive optimization scheme to reduce the size of the problem one variable at a time. Once the size of the generated intermediate problem is below a given threshold (`min_num_vars`

), the `RecursiveMinimumEigenOptimizer`

uses another solver (`min_num_vars_optimizer`

), e.g., an exact classical solver such as CPLEX or the `MinimumEigenOptimizer`

based on the `NumPyMinimumEigensolver`

.

In the following, we show how to use the `RecursiveMinimumEigenOptimizer`

using the two `MinimumEigenOptimizer`

introduced before.

First, we construct the `RecursiveMinimumEigenOptimizer`

such that it reduces the problem size from 3 variables to 1 variable and then uses the exact solver for the last variable. Then we call `solve`

to optimize the considered problem.

```
[9]:
```

```
rqaoa = RecursiveMinimumEigenOptimizer(min_eigen_optimizer=qaoa, min_num_vars=1, min_num_vars_optimizer=exact)
```

```
[10]:
```

```
rqaoa_result = rqaoa.solve(qubo)
print(rqaoa_result)
```

```
optimal function value: -2.0
optimal value: [0. 1. 0.]
status: SUCCESS
```

```
[11]:
```

```
import qiskit.tools.jupyter
%qiskit_version_table
%qiskit_copyright
```

### Version Information

Qiskit Software | Version |
---|---|

Qiskit | None |

Terra | 0.16.0 |

Aer | 0.7.0 |

Ignis | 0.5.0 |

Aqua | 0.8.1 |

IBM Q Provider | 0.10.0 |

System information | |

Python | 3.7.4 (default, Aug 13 2019, 15:17:50) [Clang 4.0.1 (tags/RELEASE_401/final)] |

OS | Darwin |

CPUs | 2 |

Memory (Gb) | 12.0 |

Wed Nov 11 11:22:40 2020 EST |

### This code is a part of Qiskit

© Copyright IBM 2017, 2020.

This code is licensed under the Apache License, Version 2.0. You may

obtain a copy of this license in the LICENSE.txt file in the root directory

of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.

Any modifications or derivative works of this code must retain this

copyright notice, and modified files need to carry a notice indicating

that they have been altered from the originals.

```
[ ]:
```

```
```