{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Grover Optimizer"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Introduction\n",
"\n",
"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.\n",
"\n",
"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]\n",
"\n",
"### References\n",
"\n",
"[1] [A. Gilliam, S. Woerner, C. Gonciulea, *Grover Adaptive Search for Constrained Polynomial Binary Optimization,* arXiv preprint arXiv:1912.04088 (2019).](https://arxiv.org/abs/1912.04088)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Grover Adaptive Search\n",
"Grover Search, the core element of GAS, needs three ingredients:\n",
"\n",
"1. A state preparation operator $A$ to construct a superposition of all states in the search space.\n",
"\n",
"2. An oracle operator $O$, that recognizes the states of interest and multiplies their amplitudes by -1.\n",
"\n",
"3. The Grover diffusion operator $D$, that multiplies the amplitude of the $|0\\rangle_n$ state by -1.\n",
"\n",
"While implementations of GAS vary around the specific use case, the general framework still loosely follows the steps described below.\n",
"\n",
"
\n",
"
Qiskit Software | Version |
---|---|
qiskit-terra | 0.23.0 |
qiskit-aer | 0.11.1 |
qiskit-optimization | 0.5.0 |
qiskit-machine-learning | 0.6.0 |
System information | |
Python version | 3.9.15 |
Python compiler | Clang 14.0.0 (clang-1400.0.29.102) |
Python build | main, Oct 11 2022 22:27:25 |
OS | Darwin |
CPUs | 4 |
Memory (Gb) | 16.0 |
Tue Dec 06 21:47:01 2022 JST |
© Copyright IBM 2017, 2022.
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.