Recursive QAOA¶
QAOA をサブルーチンとして繰り返し実行し、段階的に問題サイズを縮小しながら最適解を特定する量子古典ハイブリッドアルゴリズムです。各ステップで浅い回路による QAOA の測定結果から削減する変数を決定し、問題が十分小さくなった段階で総当たりにより厳密解を求めます。通常の QAOA で課題となる回路の深さの制約を緩和し、より大規模な問題への適用を目指します。
イジング変数で \(N\) 次多項式の目的関数の最適化問題を求解できます。
量子コンピュータを利用するクライアントでアルゴリズムに RQAOA を指定することで利用します。
このページでは RQAOA のパラメータの設定、求解結果の詳細な情報の取得、活用方法について説明します。
アルゴリズムの詳細はRQAOAのアルゴリズムを参照して下さい。
以下は QulacsClient を用いて RQAOA を実行し、求解の実行結果を取得する例です。
from amplify import RQAOA, QulacsClient, VariableGenerator, Model, solve
# 決定変数の配列を生成
gen = VariableGenerator()
q = gen.array("Binary", 5)
# 目的関数を作成
objective = q[0] * q[1] - q[2]
# モデルの定義
model = Model(objective)
client = QulacsClient(RQAOA)
result = solve(model, client)
注釈
RQAOA は制約付きの問題には対応していません。制約がある場合には、ペナルティ項を導入して制約なし問題へと自動変換します。
実行結果の評価¶
量子コンピュータソルバーにおいては、 solve() 関数の実行結果である amplify.Result クラスで取得できる、 amplify.Result.response_time 及び amplify.Result.execution_time はソルバーとの通信・実行時間ではなく、量子コンピュータ実機/シミュレータとの通信時間・回路の実行時間に対応します。
RQAOAではサブルーチンとしてQAOAを複数回呼び出して最適化を行います。
そのため、amplify.Result.response_time及びamplify.Result.execution_timeは対応する時間の全てのQAOAにわたる合計になります。
result = solve(model, client)
result.response_time # QPU との通信時間の合計
result.execution_time # QPU での実行時間の合計
RQAOAにおいて最適解は縮小された問題から総当たりによってただ一つに求められます。
このとき、縮小された問題における最適解を元に復元することで縮小前の問題の解もただ一つ得られます。
そのため、amplify.Result にはこの解一つのみが含まれます。
RQAOA固有の結果¶
amplify.Result.client_result の型はアルゴリズムの型に依存し、アルゴリズム毎に異なる型で実行過程を含む詳細な求解結果を返します。RQAOAではamplify.RQAOA.Resultが対応します。
RQAOA Result 属性一覧¶
属性 |
型 |
説明 |
|---|---|---|
実行時間の内訳 |
||
|
各ステップのQAOAによるコスト関数の総評価回数 (古典最適化のイテレーション数) |
|
|
RQAOAで得られた最良の目的関数値 |
|
|
RQAOAで得られた最良の解 |
|
|
各ステップのQAOAによる変数削減の履歴 |
RQAOADurations (実行時間の内訳)¶
durations は RQAOA の各フェーズにかかった時間の内訳を提供します。
d = result.client_result.durations
result.total_time # amplify.solveにかかった時間
d.total_time # RQAOA 全体の経過時間
d.total_response_time # バックエンド との通信時間の合計
d.total_execution_time # バックエンド での実行時間の合計
d.classical_processing_time # 古典最適化にかかった時間 (= total_time - total_response_time)
history (RQAOA 最適化の履歴)¶
amplify.RQAOA.Result.history は変数削減のための各QAOAステップ (RQAOAHistoryItem) のリストです。
for step in result.client_result.history:
print(step.timestamp) # RQAOAの開始時刻からこのステップの完了までの経過時間
print(step.model) # 変数削減後のこのステップでの目的関数
print(step.qaoa_result) # QAOAResult
print(step.elimination_info) # このステップの結果から選ばれた変数削減情報
パラメータの設定¶
パラメータ |
型 |
デフォルト |
説明 |
|---|---|---|---|
|
|
Ansatz 回路の深さ (層数 \(p\))。大きいほど表現力が増しますが、回路が深くなります |
|
|
|
測定回数。大きいほど統計精度が上がりますが、実行時間が増えます |
|
QAOA の種別。 |
|||
古典最適化手法。デフォルトではscipyのCOBYLAを利用します |
|||
|
|
変数数がこの値になるまで変数削減を試みます |
|
|
|
変数削減を行う対象の項の最大次数を制限します。Noneなら制限しません |
|
|
|
項の期待値の絶対値がこの値を上回る項から変数削減を行います |
変数削減目標サイズ (min_size)¶
min_size は RQAOA で問題に含まれる変数の個数をいくつにまで削減することを目指すかを指定します。詳細はRQAOAのアルゴリズムを参照して下さい。
後述のmax_degree、min_corrの値によっては変数を削減できない場合があり、その場合は変数の削減を中断し総当たりよる最適解の探索に移ります。
一度の変数削減で一つの変数を削減します。元の変数の個数との差がQAOAの実行回数になります。
最適解の特定に総当たりを行うため、
min_sizeが大きいほど最適解の特定にかかる時間が増加します。デフォルト:
2
- 設定例:
client.parameters.min_size = 2
変数削減対象項 (max_degree)¶
max_degree は RQAOA で変数削減の対象とする変数を選ぶ元の項の次数の制限です。詳細はRQAOAのアルゴリズムを参照して下さい。
3以上では変数削減に伴い問題の次数が増加する場合があることに注意が必要です。目的関数に含まれる項が max_degree を下回るものしかない場合は変数削減を中断し、最適解の探索に移ります。
デフォルト:
None
- 設定例:
client.parameters.max_degree = 2
変数削減項期待値閾値 (min_corr)¶
min_corr は RQAOA で変数削減の対象とする項が満たすべき最小の期待値の制限です。詳細はRQAOAのアルゴリズムを参照して下さい。
目的関数に含まれる項の期待値の絶対値が全て min_corr を下回る場合は変数削減を中断し、最適解の探索に移ります。
デフォルト:
0
- 設定例:
client.parameters.min_corr = 0