참고

이 페이지는 tutorials/optimization/3_minimum_eigen_optimizer.ipynb 에서 생성되었다.

IBM 퀀텀 랩 에서 대화식으로 실행하시오.

Minimum Eigen Optimizer

소개

양자 컴퓨팅에서 다루어지는 흥미로운 최적화 문제들 중 이차 비한정 이진 최적화 (Quadratic Unconstrained Binary Optimization; QUBO)라는 문제가 있다. QUBO에 대한 솔루션을 찾는 것은 이에 대응하는 이싱 해밀토니안(Ising Hamiltonian)의 기저 상태(ground state)를 찾는 것과 동일한 문제로 취급될 수 있는데, 이는 최적화에서 뿐만 아니라 양자 화학과 물리학에서도 중요하게 여겨진다. 이러한 변환에 대하여, \(\{0, 1\}\) 값을 취하는 바이너리형 변수들은 \(\{-1, +1\}\) 값을 취하는 스핀 변수(spin variable)들에 의하여 대체되며, 이는 결과적으로 스핀 변수들을 Pauli Z 행렬들에 의해 대체될 수 있게 하며, 따라서 Ising Hamiltonian로 대체된다. 매핑에 대한 자세한 사항은 [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).

[2] S. Bravyi, A. Kliesch, R. Koenig, E. Tang, Obstacles to State Preparation and Variational Optimization from Symmetry Protection, arXiv preprint arXiv:1910.08980 (2019).

QUBO를 Operator로 변환하기

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

# 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) 이 발생한다.

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를 제공한다.

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 를 초기화하는 것으로 시작한다.

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 를 사용한다.

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.

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.

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.

rqaoa = RecursiveMinimumEigenOptimizer(min_eigen_optimizer=qaoa, min_num_vars=1, min_num_vars_optimizer=exact)

rqaoa_result = rqaoa.solve(qubo)
print(rqaoa_result)

optimal function value: -2.0
optimal value: [0. 1. 0.]
status: SUCCESS

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.