注釈
このページは tutorials/optimization/3_minimum_eigen_optimizer.ipynb から生成されました。
IBM Quantum lab でインタラクティブに実行します。
最小固有値オプティマイザー (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].
Qiskitは、適切な QuadraticProgram からイジング・ハミルトニアンへの自動変換を提供します。これにより、- VQE 、- QAOA 、または- NumpyMinimumEigensolver （クラシカルな厳密法）などのすべての MinimumEigenSolver を活用できます。
Qiskitは、イジング・ハミルトニアン (Qiskit Aquaでは Operator とも呼ばれます) への翻訳、すなわち MinimumEigensolver への呼び出しと、結果の翻訳とを、ラップして MinimumEigenOptimizer の OptimizationResult に戻します。
以下では、まず、QuadraticProgram から Operator への変換を示します。次に、与えられた QuadraticProgram を解くのに、MinimumEigenOptimizer を異なる``MinimumEigensolver`` にどう使うのかを示します。Qiskitのアルゴリズムは、与えられた問題を、可能であればサポートされている問題クラスに自動的に変換しようとします。例えば、MinimumEigenOptimizer は整数変数をバイナリー変数に自動的に変換したり、線形等価制約を2次ペナルティ項として目的関数に追加したりします。整数変数を持つ二次計画問題を変換しようとすると、Aqua は QiskitOptimizationError を投げることに注意してください。
QAOA の回路の深さは、問題の大きさに応じて必然的に増加する可能性があり、これは近未来の量子デバイスにとっては障害となる可能性があります。考えられる回避策として、 [2] で紹介されている再帰QAOAがあります。このチュートリアルの最後で紹介しますが、Qiskit はこの概念を`RecursiveMinimumEigenOptimizer`` に一般化しています。
参考文献¶
[1] A. Lucas, Ising formulations of many NP problems, Front. Phys., 12 (2014).
QUBOをオペレーターに変換する¶
[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 だけではなく、結果の値をシフトするのに考慮すべき定数オフセットにもなります。
[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 の形でも直接与えられる場合があります。 このような場合、Qiskit は Operator から QuadraticProgram に戻す変換機能を備えています。これについては以下で説明します。
[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
このコンバーターにより、例えば、Operator を QuadraticProgram に変換して、イジング・ハミルトニアン表現に基づいていない他のアルゴリズム（例えば GroverOptimizer ）で問題を解くことができます。
Solving a QUBO with the MinimumEigenOptimizer¶
まず、使用する 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()
次に、MinimumEigensolver を使用して MinimumEigenOptimizer を作成します。
[6]:
qaoa = MinimumEigenOptimizer(qaoa_mes) # using QAOA
exact = MinimumEigenOptimizer(exact_mes) # using the exact classical numpy minimum eigen solver
最初に、古典的で厳密な``NumPyMinimumEigensolver`` に基づいた MinimumEigenOptimizer を使用して、この小さな例に対してベンチマークとなる最適解を求めます。
[7]:
exact_result = exact.solve(qubo)
print(exact_result)
optimal function value: -2.0
optimal value: [0. 1. 0.]
status: SUCCESS
次に、同じ問題に対して、QAOA に基づいた MinimumEigenOptimizer を適用します。
[8]:
qaoa_result = qaoa.solve(qubo)
print(qaoa_result)
optimal function value: -2.0
optimal value: [0. 1. 0.]
status: SUCCESS
RecursiveMinimumEigenOptimizer¶
RecursiveMinimumEigenOptimizer は入力として MinimumEigenOptimizer を取り、再帰的な最適化スキームを適用して、問題のサイズを1変数ずつ小さくしていきます。 生成された中間問題のサイズが与えられたしきい値 (min_num_vars) を下回ると、RecursiveMinimumEigenOptimizer は別のソルバー(min_num_vars_optimizer)、例えば、CPLEX、あるいは``NumPyMinimumEigensolver`` に基づいた``MinimumEigenOptimizer`` のような、厳密な古典的ソルバーを使用します。
以下では、以前に導入した 2 つの MinimumEigenOptimizer を使用して RecursiveMinimumEigenOptimizer を使用する方法を示します。
最初に RecursiveMinimumEigenOptimizer を構築し、問題サイズを3つの変数から1つの変数に縮小し、最後の変数に正確なソルバーを使用します。 次に、検討された問題を最適化するために solve を呼び出します。
[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.
[ ]: