Resource-Efficient Quantum Optimization via Higher-Order Encoding

本論文は、高次制約なしバイナリ最適化（HUBO）が、組合せ最適化問題において従来のQUBO定式化よりも大幅にリソース効率の高い代替案となることを示し、量子ビット数およびCNOTゲート数の大幅な削減を実現するとともに、近未来の量子デバイスへの採用を促進するためのオープンソースライブラリを提供するものである。

要約

巨大で複雑なパズルを解こうとしている場面を想像してみてください。量子コンピューティングの世界では、このパズルは「組合せ最適化問題」と呼ばれています。これは、飛行機をどの空港のゲートに割り当てるのが最適か、隣接する国が同じ色にならないように地図を塗り分けるにはどうすればよいか、あるいは、最もコストを抑えるために工場の生産ラインをどのようにスケジューリングするか、といった問題を解くようなものです。

長い間、科学者たちは「QUBO（二次無制約バイナリ最適化）」と呼ばれる特定の手法を用いて、これらのパズルを解こうとしてきました。QUBOとは、あなたのパズルを量子コンピュータが理解できる言語へと翻訳するための、非常に厳格で硬直した方法だと考えてください。

旧来の手法（QUBO）の問題点

この論文では、QUBOによる手法を、スーツケースに荷物を詰め込む際、すべてのアイテムを個別の大きすぎる箱に無理やり押し込もうとするようなものだと説明しています。

• 多すぎる箱（量子ビット）： 例えば、ある変数が10通りの値（例えば10種類の異なる空港ゲート）を取れる場合、QU الارQUBOでは、その一つの選択肢を表すためだけに10個もの別々の「箱」（量子ビット）を使用することを強制されます。
• 多すぎる接着剤（ペナルティ項）： コンピュータが一度に2つの箱を選んでしまうこと（これは間違いになります）を防ぐために、「ペナルティ項」と呼ばれる重い「接着剤」を追加しなければなりません。この接着剤のせいで、指示書（量子回路）は非常に長く、複雑になってしまいます。
• 結果： 量子コンピュータは圧倒されてしまいます。問題自体はそれほど大きくなくても、あまりにも多くの部品（量子ビット）を必要とし、あまりにも多くの複雑な動き（ゲート）を行わなければならなくなるのです。

新しい解決策：HUBO

論文の著者たちは、「HUBO（高次無制約バイナリ最適化）」と呼ばれる、よりスマートな方法を紹介しています。

HUBOは、先ほどのスーツケースの詰め方を、圧縮バッグを使って行うようなものです。すべてのアイテムに巨大な箱を与える代わりに、選択肢を表すためのコンパクトなバイナリコード（デジタル圧縮ファイルのようなもの）を使用します。

• より少ない箱： 10通りの選択肢がある場合、HUBOは10個の箱を必要としません。わずか4個程度の箱で済みます（$2^4 = 16$ なので、10をカバーできます）。これは、コンピュータの自然な「バイナリ」言語をより効率的に利用しているからです。
• 余計な接着剤が不要： エンコーディング（符号化）が非常にスマートであるため、コンピュータは自然に一度に一つの値しか選べないことを理解します。間違いを防ぐための、あの重くて高価なペナルティ項を追加する必要はありません。
• 結果： 指示書ははるかに短くなり、量子コンピュータが作業を行うために必要な部品も大幅に少なくなります。

彼らが実際に成し遂げたこと

研究者たちは単に理論を述べただけではありません。彼らは、3つの実世界のパズルの種類を用いてテストを行いました。

1. ゲート割り当て（GAP）： 乗客の歩行時間を最小限にするために、飛行機を空港のゲートに割り当てる問題。
2. グラフ彩色（MkCS）： 隣接する領域が同じ色にならないように地図を塗る問題。
3. 整数計画法（IP）： リソースを最適化するための一般的な数学の問題。

彼らは、有名な量子アルゴリズムである「QAOA」を用いて、従来の「QUBO」手法と、新しい「HUBO」手法を比較しました。

結果：圧倒的な勝利

その結果は劇的なものでした。QUBOからHUBOに切り替えることで：

• 必要な部品が減少： 必要な量子ビット（量子コンピュータの基本構成要素）が大幅に少なくなりました。
• 動きが劇的に減少： 最も重要な発見は、「CNOTゲート」（量子コンピュータが行う特定の種類の動き）の数に関するものでした。HUBO手法は、すべてのテストにおいて、これらの動きの数を少なくとも89.6%削減しました。場合によっては、ほぼ100%の削減となりました。
• より優れた解： HUBOは、実行コストが低いだけでなく、QUBOと同じ時間を与えられた場合でも、パズルに対してより優れた答えを見つけ出しました。

まとめ

この論文は、現在私たちが持っている（そして近い将来登場するであろう）量子コンピュータにとって、従来のQUBO手法は重すぎて無駄が多いと結論付けています。新しいHUBO手法は、現在のハードウェアにより適した「軽量」な代替案です。

他の人々がこれを利用できるように、著者たちは無料のオープンソース・ソフトウェア・ツール（PyHUBOというPythonライブラリ）も公開しました。これにより、これらの複雑な問題を効率的なHUBO形式へと自動的に変換することができ、他の科学者やエンジニアがこのリソース節約型の手法をすぐに使い始めることができます。

要約すると： 彼らは、複雑なパズルを解くための量子的な指示書を圧縮する方法を見つけ出し、それによって、今日の量子コンピュータで現実世界の課題を実際に解決できる可能性を大きく高めたのです。

技術概要

技術要約：高次エンコーディングによるリソース効率の高い量子最適化

問題提起
組合せ最適化問題（COP）は、物流から計算生物学に至るまで幅広い分野で中心的な役割を果たしていますが、多くの場合NP困難であり、問題規模が増大するにつれて古典的なソルバーでは計算量的に実行不可能になります。量子アルゴースリズム、特に量子近似最適化アルゴリズム（QAOA）は、これらの課題に対処するための潜在的な経路を提供します。しかし、現在の量子アプローチは、二次無制約バイナリ最適化（QUBO）定式化によるリソース需要によって頻繁にボトルネックに直面しています。標準的なQUBOエンコーディング（One-Hotエンコーディングなど）は、変数（$n$）と変数あたりの値の数（$m$）の両方に線形な数の量子ビットを必要とするため、$n \times m$ 個の量子ビットを要します。さらに、QUBOにおいて制約を課すには、通常、大きなペナルティ項が必要となり、それが回路の深さと2量子ビットCNOTゲートの数を増加させ、多くの実用的な問題を近未来の量子ハードウェア上で実行不可能にしています。

手法
著者らは、これらのリソース制約を緩和するために、高次無制制約バイナリ最適化（HUBO）を利用した体系的なフレームワークを提案しています。この手法は、主に3つのコンポーネントで構成されています。

1. バイナリエンコーディング vs. One-Hotエンコーディング： 各変数と値のペアを個別の量子ビットとするOne-Hotエンコーディングの代わりに、著者らはバイナリエンコーディングを採用しています。ここでは、各変数 $i$ は $d = \lceil \log_2(m) \rceil$ ビットのコンパクトなバイナリレジスタによって表現されます。これにより、量子ビットの要件が $n \times m$ から $n \times \lceil \log_2(m) \rceil$ へと削減されます。
2. HUBOハミルトニアンの構築： 著者らは、このバイナリエンコーディングが自然に、最大 $2 \times d$ 次の高次相互作用項を含むHUBOハミルトニアンを導くことを示しています。QUBOとは異なり（One-Hot制約を強制するためにペナルティ項を必要とする）、バイナリエンコーディングは単一の値の割り当てを本質的に尊重します。制約（例：$s_i \neq s_j$）は、変数空間を拡張することなく、ハミルトニアンに直接組み込まれるか、あるいはペナルティ項を介して組み込まれます。
3. 回路コンパイル： 高次の項は形式的には多量子ビット相互作用を意味しますが、著者らはこれらがすべて標準的な単一および2量子ビットゲートにコンパイル可能であることを示しています。著者らは、コストユニタリ $e^{-i\gamma \hat{H}_C}$ を実装するために、WelchらによるGrayコードベースの回路合成を利用しています。このアプローチは、ある項のために生成されたパリティ状態を利用して他の項の構築を支援することで、冗長な操作を最小限に抑え、CNOTゲートの漸近的なスケーリングを $O(n^2 m^2)$ とし、QUBOと同等のレベルに抑えつつ、実際には大幅に低い定数因子を実現しています。

また、著者らは、Walsh-Hadamard変換を用いてHUBOハミルトニアンの構築と係数の計算を自動化し、数値的な複雑さが問題サイズに対して多項式スケールになることを保証するオープンソースのPythonライブラリである PyHUBO を導入しています。

主な貢献

• 体系的なフレームワーク： One-Hotまたは関連する制約を持つ問題に対して、バイナリエンコーディングを用いてCOPをHUBOハミルトニアンへマッピングする一般的な手法。
• リソースの削減： HUBO定式化が、量子ビット数だけでなく、QAOA実行に必要な総CNOTゲート数を大幅に削減することを実証。
• ソフトウェアツール： 量子コミュニティにおけるHUBOモデルの採用を促進するための、PyHUBOのリリース。
• ベンチマーク： 3つの異なるCOPクラス（ゲート割り当て問題（GAP）、最大k-彩色部分グラフ（MkCS）、整数計画法（IP））にわたる包括的な評価。

結果
著者らは、選択された3つの問題クラスにおいて、QUBOとHUBOの両方のエンコーディングを用いたQAOAのベンチマークを実施しました。結果は、HUBOにおける大幅なリソース節約を示しています。

• 量子ビット効率： HUBOは量子ビット要件を $O(nm)$から$O(n \log m)$ に削減します。
• ゲート数の削減： テストされたすべてのインスタンスにおいて、HUBOは総CNOTゲート数を少なくとも 89.6% 削減しました。整数計画法のベンチマークなどの特定のケースでは、削減率は 97.1% に達しました。
• 解の質： 固定されたQAOAレイヤー数において、HUBO-QAOAはQUBO-QAOAよりも一貫して優れた近似比（最適解に近い値）を達成しました。例えば、GAPベンチマークでは、HUBOは平均目的関数値12.1分に対し、QUBOは15.8分を記録しました。
• 収束性： HUBO-QAOAは、はるかに少ない総ゲート数で目標近似比に到達しました。IPベンチマークにおいて、HUBOは1レイヤーで目標比0.60を達成しましたが、QUBOは10レイヤーを必要とし、その結果、QUBOは31.6倍多くのCNOTゲートと24.5倍多くのRZゲートを消費しました。
• スケーラビリティ： HUBOのリソース優位性は、問題サイズが大きくなるにつれて維持され、しばしば増大しました。HUBOは、QUBO-QAOAが過剰なリソース要件のために計算量的に実行不可能となる問題サイズにおいても、実行可能性を維持しました。

意義
本論文は、HUBO定式化が近未来のデバイスにおける量子最適化のための実用的な代替案を提供すると主張しています。高次の相互作用がハードウェアの要求を高めるという直感に反して、著者らは、ペナルティ項の排除と変数表現の圧縮が、ネットでの回路複雑さの減少につながることを示しています。量子ビット数とCNOT要件を大幅に下げることで、HUBOエンコーディングは、現在量子アルゴリズムの適用を制限しているリソースのボトルネックを緩和するのに役立ちます。著者らは、量子技術が進歩し問題サイズが拡大するにつれ、これらのリソース効率の高い手法がますます重要になり、産業界や研究における実現可能なアプリケーションを可能にすると結論付けています。