English
Languages
English
Japanese
German
Korean
Portuguese, Brazilian
Shortcuts

Note

This page was generated from tutorials/optimization/4_grover_optimizer.ipynb.

Run interactively in the IBM Quantum lab.

Grover Optimizer

Introduction

Grover Adaptive Search (GAS) has been explored as a possible solution for combinatorial optimization problems, alongside variational algorithms such as Variational Quantum Eigensolver (VQE) and Quantum Approximate Optimization Algorithm (QAOA). The algorithm iteratively applies Grover Search to find the optimum value of an objective function, by using the best-known value from the previous run as a threshold. The adaptive oracle used in GAS recognizes all values above or below the current threshold (for max and min respectively), decreasing the size of the search space every iteration the threshold is updated, until an optimum is found.

In this notebook we will explore each component of the GroverOptimizer, which utilizes the techniques described in GAS, by minimizing a Quadratic Unconstrained Binary Optimization (QUBO) problem, as described in [1]

Find the Minimum of a QUBO Problem using GroverOptimizer

The following is a toy example of a minimization problem.

\begin{eqnarray} \min_{x \in \{0, 1\}^3} -2x_1x_3 - x_2x_3 - 1x_1 + 2x_2 - 3x_3. \end{eqnarray}

For our initial steps, we create a docplex model that defines the problem above, and then use the from_docplex() function to convert the model to a QuadraticProgram, which can be used to represent a QUBO in Qiskit Optimization.

[1]:
from qiskit.aqua.algorithms import NumPyMinimumEigensolver
from qiskit.optimization.algorithms import GroverOptimizer, MinimumEigenOptimizer
from qiskit.optimization.problems import QuadraticProgram
from qiskit import BasicAer
from docplex.mp.model import Model

backend = BasicAer.get_backend('statevector_simulator')
[2]:
model = Model()
x0 = model.binary_var(name='x0')
x1 = model.binary_var(name='x1')
x2 = model.binary_var(name='x2')
model.minimize(-x0+2*x1-3*x2-2*x0*x2-1*x1*x2)
qp = QuadraticProgram()
qp.from_docplex(model)
print(qp.export_as_lp_string())
\ This file has been generated by DOcplex
\ ENCODING=ISO-8859-1
\Problem name: docplex_model1

Minimize
 obj: - x0 + 2 x1 - 3 x2 + [ - 4 x0*x2 - 2 x1*x2 ]/2
Subject To

Bounds
 0 <= x0 <= 1
 0 <= x1 <= 1
 0 <= x2 <= 1

Binaries
 x0 x1 x2
End

Next, we create a GroverOptimizer that uses 6 qubits to encode the value, and will terminate after there have been 10 iterations of GAS without progress (i.e. the value of \(y\) does not change). The solve() function takes the QuadraticProgram we created earlier, and returns a results object that contains information about the run.

[3]:
grover_optimizer = GroverOptimizer(6, num_iterations=10, quantum_instance=backend)
results = grover_optimizer.solve(qp)
print("x={}".format(results.x))
print("fval={}".format(results.fval))
x=[1 0 1]
fval=-6.0

This results in the optimal solution \(x_0=1\), \(x_1=0\), \(x_2=1\) and the optimal objective value of \(-6\) (most of the time, since it is a randomized algorithm). In the following, a custom visualization of the quantum state shows a possible run of GroverOptimizer applied to this QUBO.

92cfb29a5d16442281f7313536835f6b

Each graph shows a single iteration of GAS, with the current values of \(r\) (= iteration counter) and \(y\) (= threshold/offset) shown in the title. The X-axis displays the integer equivalent of the input (e.g. ‘101’ \(\rightarrow\) 5), and the Y-axis shows the possible function values. As there are 3 binary variables, there are \(2^3=8\) possible solutions, which are shown in each graph. The color intensity indicates the probability of measuring a certain result (with bright intensity being the highest), while the actual color indicates the corresponding phase (see phase color-wheel below). Note that as \(y\) decreases, we shift all of the values up by that amount, meaning there are fewer and fewer negative values in the distribution, until only one remains (the minimum).

31a08df8287441a887c24d42d6bfa020

Check that GroverOptimizer finds the correct value

We can verify that the algorithm is working correctly using the MinimumEigenOptimizer in Qiskit.

[4]:
exact_solver = MinimumEigenOptimizer(NumPyMinimumEigensolver())
exact_result = exact_solver.solve(qp)
print("x={}".format(exact_result.x))
print("fval={}".format(exact_result.fval))
x=[1. 0. 1.]
fval=-6.0
[5]:
import qiskit.tools.jupyter
%qiskit_version_table
%qiskit_copyright

Version Information

Qiskit SoftwareVersion
Qiskit0.24.0
Terra0.16.4
Aer0.7.6
Ignis0.5.2
Aqua0.8.2
IBM Q Provider0.12.1
System information
Python3.8.8 (default, Feb 19 2021, 19:42:00) [GCC 9.3.0]
OSLinux
CPUs2
Memory (Gb)6.7913818359375
Thu Mar 04 21:33:28 2021 UTC

This code is a part of Qiskit

© Copyright IBM 2017, 2021.

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.

[ ]: