참고

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

Run interactively in the IBM Quantum lab.

그로버 (Grover) 최적화 프로그램

도입

그로버 적응 검색 (그로버 적응성 검색 (GAS)) 은 조합 최적화 문제들을 위한 가능한 솔루션으로서, 다양한 알고리즘, 예를 들어, 변동 (Variational Quantum Eigensolver) (VQE) 및 퀀텀 어근접 최적화 알고리즘 (QAOA) 과 함께 탐색되었다. 알고리즘은 이전 실행에서 가장 잘 알려진 값을 임계값으로 사용하여 목표 함수의 최적 값을 찾기 위해 그로버 검색을 반복적으로 적용합니다. GAS 에서 사용된 적응형 오클은 현재 임계값 이상의 모든 값을 인식하고 (최대 및 최소), 최적이 발견될 때까지, 임계값이 업데이트될 때마다 검색 공간의 크기를 감소시킨다.

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]

참조

[1] A. Gilliam, S. Woerner, C. Gonciulea, Grover Adaptive Search for Constrained Polynomial Binary Optimization, arXiv preprint arXiv:1912.04088 (2019).

그로버 적응 탐색 (Grover Adaptive Search)

Grover Search, the core element of GAS, needs three ingredients:

1. A state preparation operator \(A\) to construct a superposition of all states in the search space.

2. An oracle operator \(O\), that recognizes the states of interest and multiplies their amplitudes by -1.

3. The Grover diffusion operator \(D\), that multiplies the amplitude of the \(|0\rangle_n\) state by -1.

While implementations of GAS vary around the specific use case, the general framework still loosely follows the steps described below.

GroverOptimizer uses QuadraticProgramToNegativeValueOracle to construct \(A_y\) such that it prepares a \(n\)-qubit register to represent the equal superposition of all \(|x\rangle_n\) and a \(m\)-qubit register to (approximately) represent the corresponding \(|Q(x)-y\rangle_m\). Then, all states with \((Q(x) - y)\) negative should be flagged by \(O_y\). Note that in the implementation discussed, the oracle operator is actually independent of \(y\), but this is not a requirement. For clarity, we will refer to the oracle as \(O\) when the oracle is independent of \(y\).

Put formally, QuadraticProgramToNegativeValueOracle constructs an \(A_y\) and \(O\) such that:

where \(|x\rangle\) is the binary encoding of the integer \(x\).

At each iteration in which the threshold \(y\) is updated, we adapt \(A_y\) such that the function values are shifted up or down (for minimum and maximum respectively) by \(y\). For example, in the context of finding the minimum, as the value of \(y\) decreases, the search space (negative values) also decreases, until only the minimum value remains. A concrete example will be explored in the next section.

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.

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')

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.

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.

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).

Check that GroverOptimizer finds the correct value

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

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

import qiskit.tools.jupyter
%qiskit_version_table
%qiskit_copyright

Version Information

Qiskit Software	Version
Qiskit	0.20.0
Terra	0.15.1
Aer	0.6.1
Ignis	0.4.0
Aqua	0.7.5
IBM Q Provider	0.8.0
System information
Python	3.8.5 (default, Jul 21 2020, 10:48:26) [Clang 11.0.3 (clang-1103.0.32.62)]
OS	Darwin
CPUs	2
Memory (Gb)	8.0
Wed Aug 12 19:54:42 2020 JST

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.