Efficient Fourier-Based Linear Combination of Unitaries and Applications in Quantum Optimization

本論文は、回路複雑性を多項式サンプリングオーバーヘッドと引き換えることで最適化タスク向けの複雑な量子回路を効率的に分解する、補助量子ビット不要のフーリエに基づくユニタリ線形結合（LCU）枠組みを提案し、これにより厳密な性能保証を維持しつつ、QAOA などのアルゴリズムを近未来の量子デバイス上でハードウェアに優しい形で実装可能にする。

要約

巨大で極めて複雑なパズルを解こうとしていると想像してください。量子コンピューティングの世界において、このパズルはしばしば最適化問題です：最も効率的な配送経路や最良の投資ポートフォリオのように、物事の最良の組み合わせを見つけることです。

Carrera Vazquez、Egger、Woerner による論文は、まだ初期段階の「ノイズ」のある開発段階にある量子コンピュータ、特にそれらを用いてこれらのパズルに取り組むための巧妙な新しい方法を導入しています。

以下に、彼らのアイデアを簡単なアナロジーを用いて解説します。

問題：「全員参加型」の回路

従来、これらのパズルを量子コンピュータで解くためには、パズルのすべてのピースが同時に互いに会話する特定の機械（量子回路）を構築する必要があります。

• アナロジー： 100 人のゲスト全員が、同時に他のすべてのゲストと握手をする必要があるパーティーを組織しようとしていると想像してください。実際の部屋では、これは不可能です。人々は互いにぶつかり、部屋は混雑しすぎ、イベントは失敗します。
• 量子の現実： 量子の観点からすると、これには「すべて同士の接続（all-to-all connectivity）」と非常に深く複雑な回路が必要です。現在の量子コンピュータは小さな部屋のようなもので、そのような多くの同時握手を誤り（ノイズ）なく処理することはできません。

解決策：「レシピブック」アプローチ（LCU）

著者たちは、**ユニタリ演算の線形結合（Linear Combination of Unitaries: LCU）**と呼ばれる新しい戦略を提案しています。不可能な「全員参加型」の機械を構築しようとする代わりに、複雑なタスクを、はるかに単純で小さなタスクのリストに分解します。

• アナロジー： 巨大で複雑なウェディングケーキを一度に焼こうとする（崩れる可能性がある）代わりに、100 個のシンプルで小さなカップケーキを焼きます。
  • いくつかのカップケーキはバニラ、いくつかはチョコレート、いくつかはスプリンクル入りです。
  • 巨大なオーブンが必要ではなく、それらを一つずつ、または少量ずつ焼くことができます。
  • その後、結果を皿の上に混ぜ合わせます。適切な比率で混ぜれば、その皿の「風味」は、あなたが望んでいた巨大なウェディングケーキと全く同じ味になります。

論文において、これらの「カップケーキ」は単一量子ビットゲート（一人が他の一人と握手をする）のみを必要とする単純な量子回路です。「混ぜ合わせ」は、量子部分が完了した後、古典的（通常のコンピュータ上）に行われます。

秘密の調味料：フーリエ変換

どのカップケーキを焼き、それぞれをどのくらい混ぜるべきか、彼らはどのようにして知っているのでしょうか？彼らはフーリエ変換と呼ばれる数学的ツールを使用します。

• アナロジー： 複雑な曲を想像してください。フーリエ変換は、その曲を個々の音符（周波数）に分解します。著者たちはこれを用いて、複雑な量子の「曲」（回路）を、一連の単純で反復的な音符（単一量子ビットの回転）に分解します。
• 結果： 彼らは、非常に困難で複雑な量子操作を、非常に簡単な操作の重み付き和として表現できます。

トレードオフ：品質対数量

落とし穴があります。巨大な機械を直接構築する代わりに、信頼できる答えを得るために「カップケーキ」の実験をより多く行う必要があります。

• アナロジー： 群衆の平均身長を知りたい場合、全員を一度測定する（全員が動いている場合、これは難しい）ことができます。あるいは、10 人のランダムな人を測定し、次に 10 人、さらに 10 人と測定し、平均を取ることができます。同じ結果が得られますが、より多くの測定を行う必要があります。
• 論文の主張： 著者たちは、単純な回路をより多く実行する必要がある（サンプリングオーバーヘッド）一方で、追加の実行回数は管理可能（多項式）であり、不可能ではないことを示しています。このトレードオフにより、彼らはそれ以外では不可能だった問題を現在のハードウェアで実行することを可能にします。

実世界への応用：「最密部分グラフ」

これが機能することを証明するために、彼らは「最密 k-部分グラフ（Densest k-Subgraph）」という特定の問題（巨大なソーシャルネットワーク内で最も結束の強い友人グループを見つけること）でこれをテストしました。

1. 小規模： 数学が完璧に機能することを示すために、12 ノードのグラフ（小さな近所のよう）でシミュレーションを行いました。
2. 大規模： 106 量子ビット（大きな近所のよう）を備えた実際の IBM 量子コンピュータで実行しました。
   • 彼らは高品質な解を正常に見つけました。
   • 彼らは二つの方法を比較しました：一つは「ペナルティ」（ルール違反に対する罰金のようなもの）を使用した方法、もう一つは特別な「ミキサー」（ルールに従うダンス）を使用した方法です。
   • 発見： 「ミキサー」アプローチは、彼らの新しいフーリエ法と組み合わせて、非常にうまく機能し、実際のノイズのあるハードウェア上でも、理論上の最良の解とほぼ同等の解を見つけました。

「ヘルパーなし」のトリック

通常、これらの「カップケーキ」を混ぜ合わせるには、数学を追跡するための追加のヘルパー量子ビット（「アンシラ」）が必要です。

• 革新： 著者たちは、このヘルパーなしで行う方法を開発しました。
• アナロジー： どちらのチームが得点したかを教えてくれる審判が必要になる代わりに、選手たちにランダムにプレーさせ、その後に得点板を見て勝者を特定します。これにより、量子回路から膨大な複雑さが取り除かれ、今日の機械にとってより親しみやすいものになります。

まとめ

この論文は、今日の不完全なハードウェア上で複雑な量子最適化アルゴリズムを実行するための新しい方法を提示しています。すべてをすべてに接続する巨大で壊れやすい機械を構築しようとする代わりに、彼らは問題を多くの小さく単純なピースに分解し、それらのピースを実行し、結果を古典的に組み合わせます。

彼らは、106 量子ビットの量子コンピュータ上で困難なグラフ問題を解くことでこれを証明し、今日「回路の複雑さ」（機械を構築する難しさ）を「サンプリングオーバーヘッド」（テストを実行する回数）と引き換えることで、より大きく複雑な問題を解決できることを示しました。

技術概要

技術的概要：ユニタリ演算子の効率的なフーリエに基づく線形結合と量子最適化への応用

問題提起
量子最適化アルゴリズム、特に量子近似最適化アルゴリズム（QAOA）は、近未来のハードウェアにおいて実装上の大きな障壁に直面している。最適化問題、特に制約（例えば基数制約など）を含む問題の数学的構造は、しばしば高接続性（すべて対すべての相互作用）、深い回路深度、および多数の2量子ビットゲートを必要とする量子回路を要する。これらの要件は、現在の超伝導量子プロセッサの能力を頻繁に超えている。回路切断や回路の近似といった戦略が存在するものの、それらは往々にして解の質と複雑さのトレードオフを強いるか、あるいは厳密な性能保証なしに多大なサンプリングオーバーヘッドを必要とする。

手法
著者らは、複雑な量子回路を、より単純でハードウェアに親和性の高い回路のアンサンブルを用いて近似するために設計された、**フーリエに基づくユニタリ演算子の線形結合（LCU）**フレームワークを提案する。中核となる手法は以下の通りである：

1. サンプリングのためのアンシラ不要 LCU：ユニタリ演算子の線形結合をコヒーレントに実装するためにアンシラ量子ビットを使用し（制御操作を必要とする）標準的な LCU 実装とは異なり、この研究はサンプリングベースの応用に焦点を当てている。準確率分解（QPD）に関連する符号因子を除去し、アンシラを古典的なランダム性で置き換えることで、この手法はアンシラ量子ビットと制御ゲートの必要性を排除する。これにより実装は、より単純な回路の確率的混合へと変換され、そのサンプリングオーバーヘッドは因子 $\Gamma$ によって定量化される。
2. 対角ユニタリのためのフーリエ分解：コスト関数やペナルティ項で一般的に用いられる対角ユニタリに対して、著者らは離散フーリエ変換を利用する。対象とするユニタリ $U_f(\gamma) = \sum_x e^{-i\gamma f(g(x))} |x\rangle\langle x|$ は、しばしば単一量子ビットの $R_Z$ ゲートの層に過ぎない、より単純なユニタリ $V(\theta_j)$ の線形結合へと分解される。係数は、ユニタリを定義する関数のフーリエ変換から導出される。このアプローチは、複雑な多量子ビット相互作用（例えば $O(n^2)$ のゲートを必要とする二次ペナルティなど）を、サンプリングオーバーヘッド $\Gamma \le m+1$ のコストで単一量子ビットの層に置き換える。
3. 非対角の置換不変ユニタリへの拡張：このフレームワークは、ハミング重み制約を保存するために使用される完全接続のXYミキサーのような、非対角ユニタリへと一般化される。シュール・ウェイル双対性と $SU(2)$の表現論を活用し、著者らは置換不変ユニタリを、集団的な単一量子ビット回転$R(g)^{\otimes n}$の連続的な線形結合として表現する。これにより、理論的なサンプリングオーバーヘッドが$O(n^3)$ 以下に抑えられながら、単一量子ビットゲートのみを用いて高度に非局所的なミキサーを実装することが可能となる。
4. ラグランジュ緩和との関連付け：本論文は、フーリエに基づく量子ペナルティと古典的なラグランジュ緩和との間の形式的なリンクを確立する。LCU 分解の単一ブランチの最適化は、ラグランジュ乗数の最適化と等価であることが示され、制約処理に関する統一的な視点を提供する。

主要な貢献

• フレームワークの構築：アンシラ不要でフーリエに基づく LCU フレームワークの導入。これにより、広範なクラスの対角および非対角ユニタリが、単一量子ビットゲート層のアンサンブルへと分解される。
• ハードウェア効率性：基数ペナルティや XY ミキサーのような複雑なすべて対すべての接続演算子が、回路深度と接続性をサンプリングオーバーヘッド（多項式オーダー）と引き換えて、著しく単純な回路に置き換えられ得ることを実証。
• 理論的保証：厳密な性能境界の提供。LCU アプローチにおいて高品質なビット列をサンプリングする確率は、$1/\Gamma$ でスケーリングされたコヒーレント確率によって下方から抑えられることを示す。また、条件付きバリューアットリスク（CVaR）最適化とこれらの境界との関連付けも行っている。
• スケーラビリティの検証：このフレームワークを、実機 IBM 量子ハードウェア上で最大106 量子ビットのインスタンスにおける最密 $k$ 部分グラフ問題に成功裏に適用。この規模は、そのような制約の完全コヒーレント実装にとっては以前は処理不可能であった。

実験結果
著者らは、12 ノードのインスタンスにおける正確な状態ベクトルシミュレーションと、106 量子ビットデバイス上での大規模実験を通じてアプローチを検証した：

• 12 ノードシミュレーション：完全コヒーレントな QAOA とフーリエに基づく LCU アプローチとの比較において、LCU 回路の生期待値はサンプリングオーバーヘッドにより低かったが、単一の LCU 基底回路（LCU から導出された変分アンサッツ）を最適化することで、最適解をサンプリングする確率が最も高くなり、特定の指標においてコヒーレントなベースラインを上回った。
• 106 ノードハードウェア実験：106 量子ビットのヘビーハックスグラフ（SWAP 層を介して拡張）上で、ペナルティベースおよび XY ミキサーベースの LCU アプローチが実行された。結果は、実用的なサンプリングオーバーヘッドが最悪ケースの理論的境界（$\Gamma \approx 10^4$）よりも著しく低いことを示した。単一ブランチ LCU アンサッツは、2.7% から 4.8% の実現可能な確率で高品質な解（最密部分グラフにおいて最大 81 本の辺）を成功裏に見つけ出し、大規模問題に対する本手法の実用性を示唆した。
• XY ミキサー対ペナルティ：XY ミキサーベースの LCU アプローチは、特に単一の最適化された基底回路を使用する場合、ペナルティベースのアプローチよりも一般的に優れていた。これは、制約保存型ミキサーがこの分解と組み合わせることでより効果的であることを示唆している。

意義と主張
本論文は、フーリエに基づく LCU フレームワークが、近未来の量子最適化の実用的な範囲を拡張するための体系的な道筋を提供すると主張している。複雑なコヒーレント操作を、より単純な回路の重み付き結合に置き換えることで、この手法は（特にグローバル制約を有する）問題インスタンスの範囲を広げ、現在のハードウェアで実行可能にする。著者らは、このアプローチが目標分布の正確な再現を必要とするのではなく、最適化タスクに適した高品質な解のサンプリングに焦点を当てていることを強調する。この仕事は、回路複雑性とサンプリングオーバーヘッドのトレードオフが実際には有利であることを示唆しており、理論的境界は往々にして実際には緩やかである。また、この手法は、そうでなければハードウェアの能力を超えていたであろうアルゴリズムや問題インスタンスの研究を可能にする。論文は、これが QAOA における制約処理に特に適した、よりハードウェアに互換性のある量子アルゴリズムのための柔軟な設計原理を提供すると結論付けている。