⚛️ quantum physics

Optimized QUBO formulation methods for quantum computing

本論文は、非線形制約を持つ組合せ最適化問題の QUBO 定式化における変数数を大幅に削減する「反復 2 次多項式法」と「マスター・サテライト法」という新手法を提案し、実世界の金融問題である「最大利益バランス決済」への適用と D-Wave 量子アニーラーを用いた性能評価を通じて、NISQ デバイスによる効率的な最適解探索の実現可能性を示しています。

原著者： Dario De Santis, Salvatore Tirone, Stefano Marmi, Vittorio Giovannetti

公開日 2026-02-25

📖 1 分で読めます🧠 じっくり読む

CC BY 4.0

原著者： Dario De Santis, Salvatore Tirone, Stefano Marmi, Vittorio Giovannetti

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

この論文は、**「量子コンピュータが抱える『狭い部屋』の問題を、賢い『家具の配置』で解決しよう」**というアイデアを提案した研究です。

少し専門的な用語を噛み砕いて、日常の例え話で説明しましょう。

1. 問題：量子コンピュータは「狭い部屋」に住んでいる

まず、量子コンピュータ（特に今の「NISQ」と呼ばれる世代）は、非常に強力ですが、**「部屋（メモリ）が狭い」**という弱点があります。
問題を解くために必要な「ビット（情報の最小単位）」を「家具」と想像してください。

論理ビット：実際に解きたい問題そのもの（例：「どの商品を売るか？」）。
スラック変数：制約条件（ルール）を守るために必要な「補助的な家具」です。

これまでの一般的な方法では、ルールを守るために**「補助家具（スラック変数）」が大量に必要**でした。
「部屋が狭いのに、家具を詰め込みすぎて、実際に解きたい問題（メインの家具）を入れるスペースがなくなってしまう」というジレンマがありました。そのため、大きな問題を解こうとすると、量子コンピュータの能力が追いつかなくなっていました。

2. 解決策：2 つの新しい「整理術」

この論文の著者たちは、**「スラック変数を劇的に減らす（90% 削減！）」**ための新しい整理術を考案しました。それは 2 つのステップから成り立っています。

① 「IQP 法（インタラクティブな家具配置）」

どんなもの？
制約条件（ルール）を、できるだけ少ない補助家具で表現する「魔法の配置図」を見つける方法です。
例え話：
従来の方法だと、「ルール違反したら罰金」というために、ルールごとに巨大な壁（スラック変数）を建てていました。
しかし、IQP 法では、**「ルール違反の組み合わせだけを見つけて、そこにだけ小さな石を置く」**というように、必要な場所だけに最小限の家具を配置します。
特に、ルールがシンプル（変数が少ない）な場合、この方法が非常に効果的で、補助家具を全く使わずに済むこともあります。

② 「マスター・サテライト法（親と子の連携）」

どんなもの？
複数のルールが同じ変数に関係している場合、**「親（マスター）」と「子（サテライト）」**に分けて管理する方法です。
例え話：
2 つのルール（A と B）があるとき、従来の方法では「A を守るための家具」と「B を守るための家具」をそれぞれ独立して大量に用意していました。
新しい方法では、まず**「親（ルール A）」を厳しく守ります。そして、「子（ルール B）」**は、「親が守られている場合だけ」チェックすればいいとします。
「親がルールを破っているなら、子のことは気にしなくていい（そもそもその状態は許されないから）」という考えです。
これにより、子のルールを守るために必要な家具を大幅に減らすことができます。さらに、親のルールを少し強く（重く）することで、子が勝手にルールを破ろうとしても、親の重みで抑え込むことができます。

3. 実証実験：金融の「お金の清算」問題を解く

この新しい整理術が本当に使えるか、実社会の**「金融取引の清算（MPBS）」**という難しい問題でテストしました。

シチュエーション： 複数の人がお互いに借金をし合っている状況で、「誰が誰にいくら払えば、全員が借金を返せるか？」を最適化する問題です。
結果：
- 家具の削減： 従来の方法に比べて、必要な補助家具（スラック変数）が約 90% 減りました。
- 性能向上： D-Wave という量子コンピュータを使ってテストしたところ、新しい方法を使うと、正解を見つけられる確率が劇的に向上しました。
- 規模の拡大： 従来の方法だと問題が大きくなると正解率が急激に落ちましたが、新しい方法では大きな問題でも高い正解率を維持できました。

4. まとめ：なぜこれが重要なのか？

この研究は、**「量子コンピュータのハードウェア（部屋）を大きくする前に、まずソフトウェア（家具の配置）を賢く整理すれば、今すぐにもっと大きな問題を解ける」**ことを示しました。

従来の方法： 部屋が狭いから、大きな問題は解けない。
この論文の方法： 部屋は狭いままでも、家具をコンパクトに整理すれば、大きな問題も解ける！

これは、量子コンピュータが実社会の複雑な問題（物流、金融、創薬など）を解決する「近未来」への大きな一歩です。新しい整理術を使うことで、今の量子コンピュータでも、より効率的に、より大きな問題を扱えるようになるのです。

1. 背景と問題定義

課題: NISQ デバイス（特に量子アニーラ）は、実行アルゴリズムに必要な量子ビット数に厳しい制限があります。多くの組合せ最適化問題は QUBO 形式に変換して解くことができますが、制約条件を QUBO に組み込むためには通常「スラック変数（slack variables）」が必要です。
既存手法の限界: 従来の標準的な QUBO 定式化手法（例：Glover et al. の手法）では、不等式制約を線形化するために、制約の範囲に応じて大量のスラック変数が必要となります。これにより、論理変数（問題そのものを表す変数）の数に匹敵、あるいはそれ以上のスラック変数が追加され、結果として必要な量子ビット数が爆発的に増加し、実用的な問題サイズを解くことが困難になります。
目的: 制約条件を近似することなく、必要なスラック変数を最小化し、より大規模な最適化問題を NISQ デバイスで解けるようにすること。

2. 提案手法：IQP と MS 法

著者らは、スラック変数を削減するための 2 つの独立した（かつ相乗的な）手法を提案しています。

A. 反復二次多項式法 (Iterative Quadratic Polynomial: IQP)

概念: 特定の制約条件（線形・非線形、等式・不等式を問わない）に対して、制約を満たす変数の組み合わせではペナルティが 0、違反する場合は負の値（-1 以下）となるような「二次多項式」を構築します。
プロセス:
1. スラック変数なしで二次多項式が構築できるか試みます。
2. 不可能な場合、スラック変数を 1 つ追加し、自由パラメータを増やして再試行します。
3. 制約を満たす変数の組み合わせに対する「等式条件」と、違反する組み合わせに対する「不等式条件（-1 以下）」を同時に満たす解が見つかるまで、スラック変数を増やしていきます。
特徴: 標準的な手法ではスラック変数の数が制約の範囲（整数値の最大値など）に依存しますが、IQP 法では変数の組み合わせ数に依存するため、変数が少ない制約ではスラック変数を大幅に削減できます。また、非線形制約や非整数パラメータに対しても近似なしで適用可能です。

B. マスター・サテライト法 (Master-Satellite: MS)

概念: 同じ変数セットに対して複数の制約が存在する場合、それらを「マスター制約」と「サテライト制約」に分類します。
- マスター制約: すべての変数の組み合わせに対して厳密にペナルティを課します。
- サテライト制約: マスター制約を既に満たしている変数の組み合わせに対してのみペナルティを課します。
メカニズム: サテライト制約のペナルティ項は、マスター制約を違反する組み合わせに対しては定義されません（あるいは 0 扱い）。これにより、サテライト制約を定義する際に必要な条件数が減り、結果として必要なスラック変数が減少します。
調整: サテライト制約がマスター制約を違反する組み合わせに対して「偶発的なインセンティブ（正の値）」を与える可能性があるため、マスター制約のペナルティ係数（ $\lambda_{MC}$ ）を適切に増幅（チューニング）することで、全体として制約違反にはペナルティが上回るように調整します。

C. 連結マスター・サテライト法

3 つ以上の制約が同じ変数に定義される場合、これらを階層的に連結させ、さらにスラック変数を削減する拡張手法も提案されています。

3. 適用事例：Max-Profit Balance Settlement (MPBS)

対象問題: 金融分野の NP 困難問題である「最大利益バランス決済（MPBS）」問題。これは、ユーザー間の未決済債権（レセivable）を、各ユーザーの残高制約（CAP/FLOOR）と入出金バランス制約（IN/OUT）を満たしつつ、最大化して決済する問題です。
定式化:
- IN/OUT 制約: 各ノード（ユーザー）が少なくとも 1 つの流入と 1 つの流出、あるいは全くの非アクティブであることを要求。
- CAP/FLOOR 制約: 各ノードの正味残高が特定の範囲内に収まることを要求。
手法の適用:
- IN/OUT 制約を「マスター」、CAP/FLOOR 制約を「サテライト」として設定。
- 各ノードの接続数（エッジ数）が 5 以下のケースにおいて、IQP/MS 法を適用。
- 結果、標準手法に比べてスラック変数が約 90% 削減されました（特にノード接続数が少ない実世界データセットで顕著）。

4. 実験結果

実験環境: D-Wave 社の 2 種類の量子アニーラを使用。
- Advantage_system4.1 (Adv1): 5627 量子ビット、Pegasus トポロジー（最大結合数 15）。
- Advantage2_prototype1.1 (Adv2): 563 量子ビット（プロトタイプ）、Zephyr トポロジー（最大結合数 20）、より低ノイズ・高結合。
データセット: 実在する金融データ（UniCredit 社）に基づき生成されたランダムな R-マルチグラフ（ノード数 6〜12、エッジ数 10〜18）。
主要な成果:
1. スラック変数の削減: 提案手法（IQPMS）は、標準手法に比べて必要な QUBO 変数（論理変数＋スラック変数）を大幅に削減しました。エッジ 1 つあたりの必要変数数は、標準法で約 4.88 に対し、提案法では約 1.30 でした。
2. 埋め込み効率: 量子アニーラへの埋め込みに必要な量子ビット数も、標準法でエッジあたり約 10.5 に対し、提案法では約 2 まで削減されました。
3. 解の成功率:
  - 最適解または 95% 以上の解を得る成功率において、提案手法は標準手法を大幅に上回りました。
  - 成功回数の倍率は、最小のインスタンスで約 7 倍、最大のインスタンス（Adv2 使用）で約 184 倍に達しました。
  - 入力サイズが増大しても、提案手法の成功率の低下は標準手法に比べて緩やかでした。
4. 次世代アニーラの性能: 結合数が高くノイズの少ない Advantage2 プロトタイプは、より大きな問題サイズに対して高い性能を示しました。

5. 結論と意義

技術的意義:
- 制約条件を QUBO に変換する際の「スラック変数」のボトルネックを、近似なしで解決する新しいパラダイムを提供しました。
- 特に、局所的な制約（ノードごとの制約）を持つ疎なグラフ構造の問題に対して極めて有効です。
- 非線形制約や非整数パラメータに対しても、追加の近似なしで適用可能である点も重要です。
実用性:
- 現在の NISQ デバイス（量子ビット数・結合数の制限）の制約下でも、実用的な規模の金融最適化問題などを解ける可能性を拓きました。
- 量子アニーラの実行成功率を劇的に向上させるため、量子コンピューティングの実用化（特に金融や物流などの組み合わせ最適化）に向けた重要なステップとなります。
今後の展望:
- 多目的ナップサック問題や部分和問題など、他の組合せ最適化問題への適用。
- 量子近似最適化アルゴリズム（QAOA）など、ゲート型量子コンピュータへの適用。
- ハイブリッド古典 - 量子ソルバーとの組み合わせによるさらなる性能向上。

この論文は、量子アニーリングを用いた実問題解決において、問題定式化の段階での最適化（スラック変数の削減）が、最終的な解の品質とスケーラビリティに決定的な影響を与えることを示す重要な研究です。