注釈

このページは docs/tutorials/02_converters_for_quadratic_programs.ipynb から生成されました。

二次計画法のコンバーター#

Qiskitの最適化モジュールの最適化問題は、 QuadraticProgram クラスで表されます。これは、最適化問題の一般的で強力な表現です。一般に、最適化アルゴリズムは二次計画法の特定の定式化に対して定義されており、問題を適切なタイプに変換する必要があります。

たとえば、Qiskit optimizationは、 Quadratic Unconstrained Binary Optimization （QUBO）問題を処理できるいくつかの最適化アルゴリズムを提供します。これらは、Qiskit optimizationが qiskit.quantum_info.SparsePauliOp オブジェクトを使用するイジングハミルトニアンにマッピングされ、基底状態が近似されます。この最適化では、VQE や QAOA などの一般的に知られているアルゴリズムを基礎となるルーチンとして使用できます。詳細については、 Minimum Eigen Optimizer に関するチュートリアルを参照してください。 GroverOptimizer など、動作が異なる他のアルゴリズムも存在することに注意してください。

問題を正しい入力形式にマッピングするために、Qiskit optimizationの最適化モジュールはさまざまなコンバーターを提供します。当チュートリアルでは、この機能の概要を説明します。現在、Qiskit optimizationには次のコンバーターが含まれています。

InequalityToEquality ：不等式制約を追加のスラック変数を使用した等式制約に変換します。
IntegerToBinary ：整数変数をバイナリ変数と対応する係数に変換します。
LinearEqualityToPenalty ：等式制約をオブジェクト関数の追加の項に変換します。
LinearEqualityToPenalty ：等式制約をオブジェクト関数の追加の項に変換します。
MaximizeToMinimize: 等価最小化問題に変換します。
MinimizeToMaximize: 等価最大化問題に変換します。
QuadraticProgramToQubo : InequalityToEquality 、 IntegerToBinary 、 LinearEqualityToPenalty 、 LinearInequalityToPenalty 、MaximizeToMinimize などが含まれている。

InequalityToEquality#

InequalityToEqualityConverter は、不等式制約を追加のスラック変数を使用して等式制約に変換し、 QuadraticProgram から不等式制約を削除します。スラック変数の上限と下限は、制約の左側と右側の差から計算されます。スラック変数の符号は、 \(\leq\) や \(\geq\) などの制約内の記号に依存します。

以下は、2つの不等式制約がある最大化問題の例です。変数 \(x\) と \(y\) はバイナリ変数であり、変数 \(z\) は整数変数です。

QuadraticProgram では、問題の最適化モデルを次のように記述します。

[1]:

from qiskit_optimization import QuadraticProgram
from qiskit_optimization.translators.docplex_mp import to_docplex_mp

[2]:

qp = QuadraticProgram()
qp.binary_var("x")
qp.binary_var("y")
qp.integer_var(lowerbound=0, upperbound=7, name="z")

qp.maximize(linear={"x": 3, "y": 2, "z": 1})
qp.linear_constraint(linear={"x": 1, "y": 1, "z": 1}, sense="LE", rhs=5.5, name="xyz_leq")
qp.linear_constraint(linear={"x": 1, "y": 1, "z": 1}, sense="GE", rhs=2.5, name="xyz_geq")
print(qp.prettyprint())

Problem name:

Maximize
  3*x + 2*y + z

Subject to
  Linear constraints (2)
    x + y + z <= 5.5  'xyz_leq'
    x + y + z >= 2.5  'xyz_geq'

  Integer variables (1)
    0 <= z <= 7

  Binary variables (2)
    x y

変換するには IntegerToBinary の convert メソッドを呼び出します。

[3]:

from qiskit_optimization.converters import InequalityToEquality

[4]:

ineq2eq = InequalityToEquality()
qp_eq = ineq2eq.convert(qp)
print(qp_eq.prettyprint())

Problem name:

Maximize
  3*x + 2*y + z

Subject to
  Linear constraints (2)
    x + xyz_leq@int_slack + y + z == 5  'xyz_leq'
    x - xyz_geq@int_slack + y + z == 3  'xyz_geq'

  Integer variables (3)
    0 <= z <= 7
    0 <= xyz_leq@int_slack <= 5
    0 <= xyz_geq@int_slack <= 6

  Binary variables (2)
    x y

変換後、問題の定式化は上記の出力のようになります。ご覧のとおり、不等式制約は、整数のスラック変数 \(xyz\_leg\text{@}int\_slack\) と \(xyz\_geq\text{@}int\_slack\) が追加された等式制約に置き換えられています。

変換がどのように機能するかを説明しましょう。たとえば、最初の制約の左側の下限は \(0\) です。これは、 \(x=0\) 、 \(y=0\) 、および \(z=0\) の場合です。したがって、追加の整数変数の上限は、 \(x=0\) 、 \(y=0\) 、および \(z=0\) の場合でも満たすことができるように \(5\) でなければなりません。元の定式化の最初の制約の左側は整数値のみである可能性があるため、変換された定式化では小数点以下の部分を切り取ることに注意してください。 2番目の制約については、基本的に同じアプローチを適用します。ただし、2番目の制約の記号は \(\geq\) であるため、\(x=1, y=1\) 、 \(z=7\) の場合でも満たすことができるように、 \(xyz\_geq\text{@}int\_slack\) の前にマイナスを追加します。

では、 interpret 法がどのように機能するか見てみましょう。この方法の目的は、変換された問題の解を元の問題の解に戻すことです。この方法を使うには、まず問題を解く必要があります。このチュートリアルではdocplexを使って解きます。まず、2次問題をdocplex.mpモデルに変換します。

[5]:

from qiskit_optimization.algorithms import CplexOptimizer

cplex_optimizer = CplexOptimizer()

[6]:

result_orig = cplex_optimizer.solve(qp)
print(result_orig)

fval=8.0, x=1.0, y=1.0, z=3.0, status=SUCCESS

[7]:

result_eq = cplex_optimizer.solve(qp_eq)
print(result_eq)

fval=8.0, x=1.0, y=1.0, z=3.0, xyz_leq@int_slack=0.0, xyz_geq@int_slack=2.0, status=SUCCESS

qp_eq の結果 result_eq には 5 つの変数値 (x=1.0, y=1.0, z=3.0, xyz_leq@int_slack=0.0, xyz_geq@int_slack=2.0) があり、元の qp の結果 result_orig には 3 つの値 (x=1.0, y=1.0, z=3.0) があります。次のように、qp_eq.variables の値を持つメソッドにリストまたは配列を渡すことで、InequalityToEquality.interpret メソッドを呼び出すことができます。 result_eq.x には、変数リスト qp_eq.variables 内の位置に対応して、各変数が解の中で取る値のリストがあります。

[8]:

print("interpreting values of result_eq:", ineq2eq.interpret(result_eq.x))
print("values of result_orig:", result_orig.x)

interpreting values of result_eq: [1. 1. 3.]
values of result_orig: [1. 1. 3.]

我々は、 \([1., 1., 3.]\) が、変換された問題と元の問題の間の共通変数（変数：\(x\), \(y\), \(z\) ）について、変換された問題の解で取られた値であることに気づきます。解釈法は元の問題の解と同じ値を示します。これは、変換後の問題と元の問題の目的関数が全く同じだからです。スラック変数は、変換後の問題の制約における等式を保証しているだけであり、制約も、元の問題が不等式制約を持っていることを除けば、元の問題と変換後の問題の間で全く同じです。

IntegerToBinary#

IntegerToBinary は、整数変数をバイナリー変数と係数に変換して、 QuadraticProgram から整数変数を削除します。変換には、 arxiv:1706.01945 （式（5））で提案されている有界係数エンコーディングが使用されます。エンコード方法の詳細については、論文を参照してください。

InequalityToEquality の出力を開始点として使用します。変数 \(x\) と \(y\) はバイナリー変数であり、変数 \(z\) とスラック変数 \(xyz\_leq\text{@}int\_slack\) と \(xyz\_geq\text{@}int\_slack\) は整数変数です。参照用に問題を再度表示します。

[9]:

print(qp_eq.prettyprint())

Problem name:

Maximize
  3*x + 2*y + z

Subject to
  Linear constraints (2)
    x + xyz_leq@int_slack + y + z == 5  'xyz_leq'
    x - xyz_geq@int_slack + y + z == 3  'xyz_geq'

  Integer variables (3)
    0 <= z <= 7
    0 <= xyz_leq@int_slack <= 5
    0 <= xyz_geq@int_slack <= 6

  Binary variables (2)
    x y

変換するには IntegerToBinary の convert メソッドを呼び出します。

[10]:

from qiskit_optimization.converters import IntegerToBinary

[11]:

int2bin = IntegerToBinary()
qp_eq_bin = int2bin.convert(qp_eq)
print(qp_eq_bin.prettyprint())

Problem name:

Maximize
  3*x + 2*y + z@0 + 2*z@1 + 4*z@2

Subject to
  Linear constraints (2)
    x + xyz_leq@int_slack@0 + 2*xyz_leq@int_slack@1 + 2*xyz_leq@int_slack@2 + y
    + z@0 + 2*z@1 + 4*z@2 == 5  'xyz_leq'
    x - xyz_geq@int_slack@0 - 2*xyz_geq@int_slack@1 - 3*xyz_geq@int_slack@2 + y
    + z@0 + 2*z@1 + 4*z@2 == 3  'xyz_geq'

  Binary variables (11)
    x y z@0 z@1 z@2 xyz_leq@int_slack@0 xyz_leq@int_slack@1 xyz_leq@int_slack@2
    xyz_geq@int_slack@0 xyz_geq@int_slack@1 xyz_geq@int_slack@2

変換後、整数変数 \(z\) は、上記のように、それぞれ係数1、2、および4の3つのバイナリー変数 \(z\text{@}0\) 、 \(z\text{@}1\) 、および \(z\text{@}2\) に置き換えられます。 InequalityToEquality によって導入されたスラック変数 \(xyz\_leq\text{@}int\_slack\) と \(xyz\_geq\text{@}int\_slack\) も、それぞれ係数1、2、2、および1、2、3の3つのバイナリー変数に置き換えられます。

注記：ここでの係数は、取り得る値 \(\{0, \ldots, 7\}\) 、 \(\{0, \ldots, 5\}\) 、 \(\{0, \ldots, 6\}\) を表現するために、係数をもつ各バイナリー変数の和は、元の整数変数の下界と上界に従うようサブセット \(\{1, 2, 4\}\) 、 \(\{1, 2, 2\}\) 、 \(\{1, 2, 3\}\) の和をとっています。

IntegerToBinary は、与えられたバイナリ結果を元の整数表現に変換する機能である interpret メソッドも提供します。この interpret メソッドがどのように動作するか見てみましょう。

[12]:

result_eq = cplex_optimizer.solve(qp_eq)
print(result_eq)

fval=8.0, x=1.0, y=1.0, z=3.0, xyz_leq@int_slack=0.0, xyz_geq@int_slack=2.0, status=SUCCESS

[13]:

result_eq_bin = cplex_optimizer.solve(qp_eq_bin)
print(result_eq_bin)

fval=8.0, x=1.0, y=1.0, z@0=1.0, z@1=1.0, z@2=0.0, xyz_leq@int_slack@0=0.0, xyz_leq@int_slack@1=0.0, xyz_leq@int_slack@2=0.0, xyz_geq@int_slack@0=0.0, xyz_geq@int_slack@1=1.0, xyz_geq@int_slack@2=0.0, status=SUCCESS

result_eq_bin は IntegerToBinary.convert による変換により、より多くのバイナリ変数を持っています。 IntegerToBinary.interpret は、 qp_eq の元の整数変数に関連付けられたバイナリ変数の値を集約することで、それらを整数値に戻します。

[14]:

print("interpreting values of result_eq_bin:", int2bin.interpret(result_eq_bin.x))
print("values of result_eq:", result_eq.x)

interpreting values of result_eq_bin: [1. 1. 3. 0. 2.]
values of result_eq: [1. 1. 3. 0. 2.]

LinearEqualityToPenalty#

LinearEqualityToPenalty は、 QuadraticProgram を制約なしの形式にマップするために、線形等式制約を目的関数の追加の2次ペナルティ項に変換します。コンバータへの入力は，線形等価制約のみを持つ QuadraticProgram でなければなりません。これらの等価性制約、例えば \(a_i\) と \(b\) は数値、 \(x_i\) は変数であり、 \(M\) はペナルティファクターとしては大きな数である時、 \(x_i\) は \(M(b - \sum_i a_i x_i)^2\) の形式で目的関数に追加されます。デフォルトでは \(M= 1e5\) です。項の符号は、問題の種類が最大化か最小化かに依存します。

IntegerToBinary の出力を開始点として使用します。ここで、すべての変数はバイナリー変数であり、すべての不等式制約は等式制約にマップされています。参照用に問題を再度表示します。

[15]:

print(qp_eq_bin.prettyprint())

Problem name:

Maximize
  3*x + 2*y + z@0 + 2*z@1 + 4*z@2

Subject to
  Linear constraints (2)
    x + xyz_leq@int_slack@0 + 2*xyz_leq@int_slack@1 + 2*xyz_leq@int_slack@2 + y
    + z@0 + 2*z@1 + 4*z@2 == 5  'xyz_leq'
    x - xyz_geq@int_slack@0 - 2*xyz_geq@int_slack@1 - 3*xyz_geq@int_slack@2 + y
    + z@0 + 2*z@1 + 4*z@2 == 3  'xyz_geq'

  Binary variables (11)
    x y z@0 z@1 z@2 xyz_leq@int_slack@0 xyz_leq@int_slack@1 xyz_leq@int_slack@2
    xyz_geq@int_slack@0 xyz_geq@int_slack@1 xyz_geq@int_slack@2

LinearEqualityToPenalty の convert メソッドを呼び出して変換します。

[16]:

from qiskit_optimization.converters import LinearEqualityToPenalty

[17]:

lineq2penalty = LinearEqualityToPenalty()
qubo = lineq2penalty.convert(qp_eq_bin)
print(qubo.prettyprint())

Problem name:

Maximize
  -26*x^2 + 26*x*xyz_geq@int_slack@0 + 52*x*xyz_geq@int_slack@1
  + 78*x*xyz_geq@int_slack@2 - 26*x*xyz_leq@int_slack@0
  - 52*x*xyz_leq@int_slack@1 - 52*x*xyz_leq@int_slack@2 - 52*x*y - 52*x*z@0
  - 104*x*z@1 - 208*x*z@2 - 13*xyz_geq@int_slack@0^2
  - 52*xyz_geq@int_slack@0*xyz_geq@int_slack@1
  - 78*xyz_geq@int_slack@0*xyz_geq@int_slack@2 - 52*xyz_geq@int_slack@1^2
  - 156*xyz_geq@int_slack@1*xyz_geq@int_slack@2 - 117*xyz_geq@int_slack@2^2
  - 13*xyz_leq@int_slack@0^2 - 52*xyz_leq@int_slack@0*xyz_leq@int_slack@1
  - 52*xyz_leq@int_slack@0*xyz_leq@int_slack@2 - 52*xyz_leq@int_slack@1^2
  - 104*xyz_leq@int_slack@1*xyz_leq@int_slack@2 - 52*xyz_leq@int_slack@2^2
  + 26*y*xyz_geq@int_slack@0 + 52*y*xyz_geq@int_slack@1
  + 78*y*xyz_geq@int_slack@2 - 26*y*xyz_leq@int_slack@0
  - 52*y*xyz_leq@int_slack@1 - 52*y*xyz_leq@int_slack@2 - 26*y^2 - 52*y*z@0
  - 104*y*z@1 - 208*y*z@2 + 26*z@0*xyz_geq@int_slack@0
  + 52*z@0*xyz_geq@int_slack@1 + 78*z@0*xyz_geq@int_slack@2
  - 26*z@0*xyz_leq@int_slack@0 - 52*z@0*xyz_leq@int_slack@1
  - 52*z@0*xyz_leq@int_slack@2 - 26*z@0^2 - 104*z@0*z@1 - 208*z@0*z@2
  + 52*z@1*xyz_geq@int_slack@0 + 104*z@1*xyz_geq@int_slack@1
  + 156*z@1*xyz_geq@int_slack@2 - 52*z@1*xyz_leq@int_slack@0
  - 104*z@1*xyz_leq@int_slack@1 - 104*z@1*xyz_leq@int_slack@2 - 104*z@1^2
  - 416*z@1*z@2 + 104*z@2*xyz_geq@int_slack@0 + 208*z@2*xyz_geq@int_slack@1
  + 312*z@2*xyz_geq@int_slack@2 - 104*z@2*xyz_leq@int_slack@0
  - 208*z@2*xyz_leq@int_slack@1 - 208*z@2*xyz_leq@int_slack@2 - 416*z@2^2
  + 211*x - 78*xyz_geq@int_slack@0 - 156*xyz_geq@int_slack@1
  - 234*xyz_geq@int_slack@2 + 130*xyz_leq@int_slack@0 + 260*xyz_leq@int_slack@1
  + 260*xyz_leq@int_slack@2 + 210*y + 209*z@0 + 418*z@1 + 836*z@2 - 442

Subject to
  No constraints

  Binary variables (11)
    x y z@0 z@1 z@2 xyz_leq@int_slack@0 xyz_leq@int_slack@1 xyz_leq@int_slack@2
    xyz_geq@int_slack@0 xyz_geq@int_slack@1 xyz_geq@int_slack@2

変換後、等式制約はQiskit optimizationに提供されたデフォルトのペナルティ係数を持つ追加項として目的関数に追加されます。変換後の問題はQUBOとなり、VQE、QAOAなどの多くの量子最適化アルゴリズムと互換性があります。

これは以前と同じ結果を与えます。

他のコンバーターでやったように、interpret メソッドがこのケースでどのように機能するか見てみましょう。

[18]:

result_eq_bin = cplex_optimizer.solve(qp_eq_bin)
print(result_eq_bin)

fval=8.0, x=1.0, y=1.0, z@0=1.0, z@1=1.0, z@2=0.0, xyz_leq@int_slack@0=0.0, xyz_leq@int_slack@1=0.0, xyz_leq@int_slack@2=0.0, xyz_geq@int_slack@0=0.0, xyz_geq@int_slack@1=1.0, xyz_geq@int_slack@2=0.0, status=SUCCESS

[19]:

result_qubo = cplex_optimizer.solve(qubo)
print(result_qubo)

fval=8.0, x=1.0, y=1.0, z@0=1.0, z@1=1.0, z@2=0.0, xyz_leq@int_slack@0=0.0, xyz_leq@int_slack@1=0.0, xyz_leq@int_slack@2=0.0, xyz_geq@int_slack@0=0.0, xyz_geq@int_slack@1=1.0, xyz_geq@int_slack@2=0.0, status=SUCCESS

[20]:

print("interpreting values of result_eq_bin:", lineq2penalty.interpret(result_qubo.x))
print("values of result_eq_bin:", result_eq_bin.x)

interpreting values of result_eq_bin: [1. 1. 1. 1. 0. 0. 0. 0. 0. 1. 0.]
values of result_eq_bin: [1. 1. 1. 1. 0. 0. 0. 0. 0. 1. 0.]

interpret メソッドの結果は、元の問題と変換された問題の両方が全く同じ解を持つことを意味していることがわかります。これは、変換された問題には元の問題と全く同じ変数があり、変換された問題には制約がないように目的が変更されているためです。

最後に、QUBO の結果をどのように解釈して元の問題 qp の解に戻すかを見てみましょう。以下のコードは、解釈された値が元の問題 qp の結果と等価であることを示しています。

[21]:

print("result_orig.x", result_orig.x)

x = result_qubo.x
for conv in [lineq2penalty, int2bin, ineq2eq]:
    x = conv.interpret(x)
print("interpreting result_qubo.x", x)

result_orig.x [1. 1. 3.]
interpreting result_qubo.x [1. 1. 3.]

[22]:

import qiskit.tools.jupyter

%qiskit_version_table
%qiskit_copyright

Version Information

Software	Version
`qiskit`	0.44.1
`qiskit-terra`	0.45.0.dev0+dcec79e
`qiskit_optimization`	0.6.0
`qiskit_algorithms`	0.3.0
System information
Python version	3.10.13
Python compiler	Clang 14.0.3 (clang-1403.0.22.14.1)
Python build	main, Aug 24 2023 22:36:46
OS	Darwin
CPUs	10
Memory (Gb)	64.0
Thu Sep 07 12:33:31 2023 JST

This code is a part of Qiskit

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.

[ ]: