Locally Acting Grover Mixers for Constraint-Preserving QAOA

本論文は、GM-QAOAにおけるコストの高いグローバルな多制御位相シフトゲートを、互いに素な量子ビット部分系に対する効率的なローカル操作に置き換える、局所的に作用するグローバーミキサーを提案しており、これにより、エキストラクト・カバーや巡回セールスマン問題のような問題に対して、元の手法と同等の収束性を達成しつつ、回路の深さとゲート数を大幅に削減している。

要約

あなたは、巨大で複雑なパズルを解こうとしていると想像してください。例えば、すべての都市を正確に一度ずつ訪問する完璧なルートを見つける「巡回セールスマン問題」のようなものです。あなたには、一度に何百万もの可能性を試すことができる超スマートなコンピュータ（量子コンピュータ）があります。しかし、このコンピュータは現在、少し「ノイズが多く」脆い状態にあります。まるで繊細なガラスの彫刻のようなものです。もし、あまりに複雑なことを頼むと、壊れてしまったり、間違いを犯したりします。

この論文は、この脆いコンピュータが壊れることなく、より優れたパズルを解けるように導く新しい方法を紹介しています。

問題点：「グローバル」なルールブック

研究者たちは、QAOA（量子近似最適化アルゴリズム）と呼ばれる手法に取り組んでいます。QAOAを、霧の立ち込める谷間の最も低い地点（最良の解）を探そうとしているハイカーだと考えてください。このハイカーがこれを行うには、2つの道具が必要です。

1. 地図（位相分離 / Phase Separation）： ハイカーに「悪い」場所がどこにあるかを示します。
2. コンパス（ミキサー / Mixer）： ハイカーが新しい場所を探索するために移動するのを助けます。

標準的なバージョンのこの手法（GM-QAOAと呼ばれます）では、「コンパス」は**グローバル多制御ゲート（Global Multi-Controlled Gate）**です。

• 比喩： 100人のダンスパーティーを تنظيمしようとしている場面を想像してください。標準的なコンパスは、次のような一つの巨大なルールのようなものです。「もし、全員が 特定の隊列で立っているならば、全員が 一斉に動かなければならない」。
• 問題点： 今日のノイズの多い量子コンピュータ上でこのルールを強制するには、100人全員を一度にチェックする、巨大で複雑な機械が必要です。この機械は非常に大きく、多くのスペースを占有し、エラーを起こす可能性が非常に高いのです。

解決策：「ローカル」な近所監視

著者であるMinjin Choi、Dongkeun Lee、Junghee Ryuは、このコンパスを作るためのよりスマートな方法を提案しています。彼らはこれを**局所的に作用するグローバー・ミキサー（Locally Acting Grover Mixers）**と呼んでいます。

• 比喩： 部屋全体に対する一つの巨大なルールの代わりに、彼らは100人を小さな独立したグループ（例えば、10人ずつの10テーブル）に分割しました。すると、全員をチェックする一つの巨大な機械の代わりに、10個の小さくて単純な機械を持つことになります。
  • テーブル1の機械はこう言います：「もしテーブル1の全員が隊列に並んでいたら、動け」。
  • テーブル2の機械はこう言います：「もしテーブル2の全員が隊列に並んでいたら、動け」。
• 結果： これらの小さな機械は、はるかに作りやすく、スペースも取らず、壊れる可能性もずっと低くなります。決定的なのは、これらのグループは独立しているため、全体の成果は巨大な機械と同じくらい優れているということです。

彼らがどのように行ったか

研究者たちは、多くのパズルにおいて、すべてのルールを初期設定に強制する必要はないということに気づきました。

1. 部分的エンコーディング（Partial Encoding）： コンピュータに、すべてのルールに従う完璧な解からスタートさせるのではなく、一部の ルールに従う解からスタートさせます。これにより、「積構造（product structure）」（前述の独立したグループ）が生まれます。
2. ローカル・ミキシング（Local Mixing）： 次に、この新しい「ローカル・コンパス」を使用して、それらの小さなグループ内での変化を促します。

証明：エグザクト・カバーと巡回セールスマン

彼らはこのアイデアを、2つの有名なパズルでテストしました。

1. エグザクト・カバー問題（Exact Cover Problem）： アイテムを正確に一度ずつカバーするという論理パズル。
2. 巡回セールスマン問題（TSP）： 複数の都市を訪れる最短ルートを見つける問題。

調査結果：

• 同等の品質： 新しい「ローカル」手法は、古い「グローバル」手法と同等の優れた解を見つけ出しました。
• はるかにシンプル： 新しい手法は、複雑な「もつれ（entanglement）」ゲート（回路の中で最も壊れやすい部分）を87%削減しました。
• トレードオフ： 新しい手法は、設定を調整するために、コンピュータが回路を走らせる回数をわずかに多くする必要があります（調整すべき「つまみ」が増えるため）。しかし、回路自体が非常にシンプルで壊れにくいため、今日のノい多いコンピュータにとって、このトレードオフは大きな勝利となります。

大きな教訓

この論文は、（小さくノイズが多い）現在私たちが持っている 量子コンピュータにとっては、「ローカル」戦略の方が適していると主張しています。

• 古い方法： 巨大で複雑な機械を作り、すべてを完璧にこなそうとするが、簡単に壊れてしまう。
• 新しい方法： 多くの小さくシンプルな機械を作り、それらを連携させる。設定を合わせるために多少の試行回数は必要かもしれないが、その方がはるかに信頼性が高く、今日のハードウェアにも適合する。

要するに、著者たちは、制約のある問題に対する量子アルゴリズムを、見つける答えの質を損なうことなく、より軽く、よりシンプルに、そしてより堅牢にする方法を見つけたのです。

技術概要

技術要約：制約保存型QAOAのための局所作用型グローバーミキサー

問題提起
量子近似最適化アルゴリズム（QAOA）およびその一般化である量子交互作用演算子アンザッツ（QAOA）は、組合せ最適化問題における著名な変分アルゴリズムである。制約付き問題にこれらのアルゴリズムを適用する際の重要な課題は、量子進化が問題の制約によって定義される実行可能部分空間内に留まることを保証することである。Grover Mixer QAOA（GM-QAOA）は、初期状態への射影によって生成される混合演算子を用いることで、これを実現し、実行可能部分空間の保存を数学的に保証する。

しかし、標準的なGM-QAOAミキサーは、$n$個の量子ビットすべてに作用するグローバルな多制御位相シフトゲートを必要とする。近未来のノイズのある中規模量子（NISQ）デバイスは、本質的に1量子ビットおよび2量子ビット操作のみをサポートしているため、このようなグローバルゲートを基本ゲートへと分解すると、大幅な回路オーバーヘッドが生じる。これらの分解による回路の深さとゲート数は量子ビット数とともに急速に増大し、実用的な実装に対する大きな障壁となり、ハードウェアノイズへの感受性を高める。

手法
著者らは、**積構造（product structure）**を持つ初期状態に対して設計された「局所作用型」のグローバーミキサーの変種を提案している。このアプローチは、多くの組合せ問題において、制約の一部を初期状態の準備にエンコードすることで、残りの制約をコストハミルトニアンのペナルティ項で処理できるという観察に基づいている。

1. 積構造を持つ初期状態: 本手法は、初期状態 $|\psi_0\rangle$ が $|\psi_0\rangle = |\psi^{(1)}_0\rangle \otimes |\psi^{(2)}_0\rangle \otimes \dots \otimes |\psi^{(\ell)}_0\rangle$ と因数分解可能であると仮定する。ここで、各 $|\psi^{(j)}_0\rangle$ は互いに素な量子ビットの部分集合上に存在する。この構造は、問題の制約の一部のみを初期状態の準備にエンコードすることによって達成される。
2. 局所混合ユニタリ: 単一のグローバルミキサー $e^{-i\beta |\psi_0\rangle\langle\psi_0|}$ の代わりに、提案手法では混合ユニタリを局所ユニタリのテンソル積として構成する：
   $$U_M(\beta^{(1)}, \dots, \beta^{(\ell)}) = \bigotimes_{j=1}^{\ell} e^{-i\beta^{(j)} |\psi^{(j)}_0\rangle\langle\psi^{(j)}_0|}$$
   各局所ユニタリは、それぞれの部分系に対して、その部分系内に限定された多制御位相シフトゲートを用いて独立に作用する。
3. パラメータ化: このアンザッツは、各部分系に対して独立した変分パラメータ $\beta^{(j)}$ を導入する。$\ell$ 個の部分系を持つ $p$ 層の回路において、総混合パラメータ数は、元のGM-QAOAの $p$ に対して $p\ell$ となる。これにより、古典的な最適化ランドスケープの次元は増加するが、一つの巨大なグローバルゲートを $\ell$ 個の小さな局所ゲートに置き換えることができる。

主な貢献

• 回路の効率性: 主な貢献は、グローバルな多制御位相シフトゲートを $\ell$ 個の局所操作に置き換えたことである。これにより、混合ステップに必要な絡み合いゲート（具体的にはCNOTゲート）の数と回路の深さを劇的に削減できる。
• 制約エンコーディング戦略: 本論文では、すべての制約を初期状態にエンコードする場合と、一部の制約のみをエンコードする場合のトレードオフを調査している。部分的な制約エンコーディングが、局所ミキサーに必要な積構造を可能にし、たとえ探索空間のサイズを縮小する場合であっても、完全な制約エンコーディングよりもコンパクトな全体回路を実現できることを示している。
• 実行可能性の保持: 本手法は、GM-QAOAの核心的な利点である、ミキシング演算子が初期状態によって定義される探索空間を保持し、非実行可能領域への逸脱を防ぐという性質を維持している。

結果
著者らは、数値シミュレーションを用いて、Exact-Cover問題および巡回セールスマン問題（TSP）において提案手法を評価した。

• Exact-Cover問題: 7量子ビットのインスタンスにおいて、提案手法は元のGM-QAOAと同等の収束挙動を示した。決定的な点として、混合ユニタリを $\{RX, RY, RZ, CNOT\}$ ゲートセットに分解することで、CNOTカウントを218（オリジナル）から28（提案手法）へと、約87%削減できた。
• 巡回セールスマン問題（TSP）: 4都市のTSPインスタンス（9量子ビット）を用いたシミュレーションでは、提案手法が、層の深さ $p$ の変化に関わらず、GM-QAOAと同等の解確率を維持することが示された。
  • ノイズ耐性: デポラリジング・ノイズモデルの下で、提案手法は、回路の深さとゲート数の減少により、元のGM-QAOAと比較してコストハミルトニアンの期待値における相対誤差が著しく低かった。
  • リソースのトレードオフ: 提案手法は、変分パラメータの増加により、古典的最適化中の量子回路実行回数が増加するものの、量子回路の複雑性（CNOTカウントが572から54へ減少）の減少が、ノイズのあるハードウェアにおいてより実行可能なものにしている。
  • 部分的エンコーディング vs 完全なエンコーディング: TSPにおいて、時間ステップの制約（$P_1$）のみを初期状態にエンコード（部分的エンコーディング）し、局所ミキサーを組み合わせた場合、最適性能時（$p=7$）の回路深さは450であった。対照的に、時間ステップと都市訪問の制約（$P_1$ および $P_2$）の両方を初期状態にエンコード（完全なエンコーディング）してグローバルミキサーを使用した場合、$p=1$ の時点で回路深さは4142に達した（高い解確率をより早く達成したにもかかわらず）。著者らは、部分的エンコーディングの方がより好ましい全体的な回路複雑性をもたらすと結論付けている。

意義と主張
本論文は、提案された局所作用型グローバーミキサーが、近未来の量子デバイス上で制約保存型QAOAを実装するための実用的な経路を提供すると主張している。実行可能部分空間の積構造を利用することで、本手法は、アルゴリズムが高い品質の解に収束する能力を維持しながら、実装コスト（ゲート数および深さ）を大幅に低減する。

著者らは、パラメータ数の増加が古典的な最適化オーバーヘッドと潜在的に複雑な最適化ランドスケープをもたらすことを控えめに認めているが、ゲート忠実度が主要な制限要因となるNISQデバイスにおいては、量子回路の複雑性の減少が支配的な要因であるとしている。この研究は、パラメータ数と回路深さのトレードオフが、現在のハードウェアにおいては提案されたアプローチに有利であることを示唆している。なお、本論文は、緩和されたミキシング構造がなぜ同等の収束を達成できるのかという理論的な問いを解決するものではなく、これを将来の研究における未解決の方向性として特定している。