QUBO 問題とは

メモ

インストールが必要: この機能には、MATLAB Support Package for Quantum Computing が必要です。

QUBO およびイジング問題の定義

2 次制約なしバイナリ最適化 (QUBO) 問題は、バイナリ変数における 2 次最適化問題です。N 個のコンポーネントをもつバイナリ変数 x(i) に対して、最小化する目的関数は次の形式になります。

f(x)=∑i=1N∑j=1NQi,jxixj+∑i=1Ncixi+d.

  • Q は実対称行列にすることができます。Q が対称でない場合、ソフトウェアは内部的に Q を等価な対称行列へ置き換えます。

    Q^=Q+Q′2

    次の式について考えます。

    x'Q⌢x=x'Qx.

  • c は N 個のコンポーネントをもつ数値ベクトルです。

  • d はスカラーです。

qubo 関数を使用して、問題を QUBO 問題へ変換します。

qprob = qubo(Q)
% or
qprob = qubo(Q,c)
% or
qprob = qubo(Q,c,d)

イジング問題は、QUBO の x 変数が 0 または 1 を取る代わりにイジング変数 y(i) が ±1 を取る点を除き、QUBO 問題と同じ定式化をもちます。線形マッピングを使用して、2 つの定式化を相互変換できます。変数 x を使用した QUBO 問題と、変数 y を使用したイジング問題に対するマッピングは次のとおりです。

y=2x−1x=y+12.

2 つの定式化における目的関数値は、容易に計算できる量だけ異なります。

x'Qx+c'x+d=(y+1)'Q(y+1)4+c'(y+12)+d=y'Qy4+(1'Q+c'2)y+d+1'Q14+c'12,

ここで、"1" は y と同じ長さをもつ 1 の列ベクトルを表します。

QUBO 問題の応用

Glover、Kochenberger、および Du [1]で説明されているように、巡回セールスマン問題や 2 次割り当て問題など、多くの組み合わせ最適化問題は QUBO 問題として定式化できます。一般的な組み合わせ最適化問題をこのフレームワークへ定式化する手法群については、Lucas [2]を参照してください。

また、現在および提案されている多くの量子コンピューターは、問題のタイプとして QUBO またはイジングを使用しています。組み合わせ最適化問題に対する量子解を求めようとするには、QUBO 問題を定式化し、解を得るためにその問題を量子ハードウェアに渡します。

解決手法

QUBO 問題を解くには、次の 2 つの手順を実行します。

  1. qubo を呼び出して、問題を QUBO オブジェクトに変換します。

  2. タブー探索アルゴリズムを使用する solve を呼び出して、QUBO を解きます。

たとえば、2 次行列 Q、線形ベクトル c、および定数項 d に対する QUBO 問題を作成します。

Q = [0 -1 2;...
    -1 0 4;...
    2 4 0];
c = [-5 6 -4];
d = 12;
qprob = qubo(Q,c,d)
qprob = 

  qubo with properties:

    QuadraticTerm: [3×3 double]
       LinearTerm: [-5 6 -4]
     ConstantTerm: 12
     NumVariables: 3

タブー探索アルゴリズムを使用して問題を解きます。

result = solve(qprob)
result = 

  quboResult with properties:

                BestX: [3×1 double]
    BestFunctionValue: 7
      AlgorithmResult: [1×1 tabuSearchResult]

あるいは、Optimization Toolbox™ ライセンスを所有しており、問題の変数の数が最大で 100 ～ 200 である場合は、Verify Optimality by Solving QUBO as MILPに示すように QUBO 問題を混合整数線形計画法 (MILP) 問題へ変換し、intlinprog を使用して解きます。

参照

[1] Glover, Fred, Gary Kochenberger, and Yu Du. Quantum Bridge Analytics I: A Tutorial on Formulating and Using QUBO Models. Available at https://arxiv.org/abs/1811.11538.

[2] Lucas, Andrew. Ising formulations of many NP problems. Available at https://arxiv.org/pdf/1302.5843.

[3] Kochenberger, G. A., and F. Glover. A Unified Framework for Modeling and Solving Combinatorial Optimization Problems: A Tutorial. In: Hager, W. W., Huang, S. J., Pardalos, P. M., Prokopyev, O. A. (eds) Multiscale Optimization Methods and Applications. Nonconvex Optimization and Its Applications, vol 82. Springer, Boston, MA. https://doi.org/10.1007/0-387-29550-X_4. Available at https://www.researchgate.net/publication/226808473_A_Unified_Framework_for_Modeling_and_Solving_Combinatorial_Optimization_Problems_A_Tutorial.

参考

関数

オブジェクト

トピック