Minimum Eigen Optimizer¶
소개¶
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].
키스킷은 QuadraticProgram 에서 이싱 해밀토니안으로의 적절한 자동 변환을 제공한다. 이로서 - VQE, - QAOA, 혹은 - NumpyMinimumEigensolver (classical exact method) 와 같은 모든 MinimumEigenSolver 들을 활용할 수 있다.
키스킷은 Ising Hamiltonian (키스킷 아쿠아에서는 Operator 라고도 함) 으로 변환을 래핑(wrapping) 하고 MinimumEigensolver 에 대한 호출은 물론 MinimumEigenOptimizer 에서 결과를 다시 OptimizationResult 로 변환한다.
다음에서는 먼저 QuadraticProgram 에서 Operator 로의 변환을 설명하고 MinimumEigenOptimizer 를 이와 유사하지만 다른 MinimumEigensolver 와 함께 사용하여 주어진 QuadraticProgram 을 해결하는 방법을 보일 것이다. 키스킷의 알고리즘은 가능한 경우 주어진 문제를 지원되는 지원되는 문제의 클래스로 자동 변환하려고 시도한다. 예를 들어, MinimumEigenOptimizer 는 정수형 변수를 바이너리형 변수로 자동 변환하거나 목적함수에 대한 2차식 패널티 항으로서 선형 등식 제약조건을 추가한다. 아쿠아는 이차계획법 문제의 정수형 변수에 대한 변환이 시도될 경우 QiskitOptimizationError 를 통해 언급할 것이다.
QAOA 의 회로 깊이(depth) 는 잠재적으로 문제의 크기와 함께 증가해야 하는데, 이는 현재의 양자 디바이스(near-term quantum devices) 에서는 (회로 비용을) 감당할 수 없을지도 모른다. 가능한 해결 방법은 [2] 에 소개된 Recursive QAOA이다. 키스킷은 본 사용 지침서의 마지막 부분에 소개된 RecursiveMinimumEigenOptimizer 에서 이 개념을 다루었다.
참조¶
[1] A. Lucas, Ising formulations of many NP problems, Front. Phys., 12 (2014).
QUBO를 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
다음으로 이 QUBO를 Ising operator로 변환한다. 변환 결과로 Operator 뿐만 아니라 결과 값을 이동(shift) 하기 위해 고려 해야할 상수 오프샛(offset) 이 발생한다.
[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
])
때때로 QuadraticProgram 은 Operator 의 형태로 직접 주어질 수도 있다. 이러한 경우를 위하여, 키스킷은 Operator 에서 다시 QuadraticProgram 으로 변환하는 converter를 제공한다.
[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.
MinimumEigenOptimizer를 사용하여 QUBO를 해결하기¶
MinimumEigensolver 를 초기화하는 것으로 시작한다.
[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()
그런 다음 MinimumEigenOptimizer 를 생성하기 위하여 MinimumEigensolver 를 사용한다.
[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.
[ ]: