Linear-depth quantum oracles for clique problems from edge colorings and graph states, with linear non-Clifford cost and a provably bounded-error k-clique search

技術要約：クリーク問題のための線形深さ量子オラクル

問題設定
本論文は、ハードワイヤード・回路モデル（hard-wired circuit model）における$k$-クリーク問題（サイズ$k$の完全部分グラフの探索）のための量子オラクルの実装について論じている。クエリモデルでは、グラフが自由なブラックボックス・オラクルを介してアクセスされるのに対し、ハードワイヤード・モデルでは、グラフ構造が量子ゲートとして明示的にコンパイルされる必要がある。既存のクリーク探索用明示的回路（Changら、Metwalliら）は、主に以下の2つの非効率性を抱えている：

1. 二次的な深さ（Quadratic Depth）： 既存の回路（例：Changら、Metwalliら）は、エッジ符号化ゲートが共通のカウンタまたはフラグ・レジスタに対して逐次的に作用するため、深さが$\Theta(m) = \Theta(n^2)$となる。
2. 高い非クリフォード・コスト（High Non-Clifford Cost）： カウントベースのオラクルは、接続性をテストするためにエッジごとに少なくとも1つの非クリフォード・ゲート（例：Toffoliゲート）を必要とする。密なグラフの場合、これは$\Theta(n^2)$個の非クリフォード・ゲートを必要とし、クリフォード・ゲートが安価で非クリフォード・ゲートが蒸留されたマジック状態を消費するフォールトトレラント・アーキテクチャにおいて、これが支配的なコストとなる。

手法
著者らは、グラフ構造を非クリフォード・コストから切り離し、以下の2つの手法によって回路の深さを削減する新しいクラスのオラクルを提案している：

1. 線形深さのためのエッジ彩色（Edge Coloring for Linear Depth）：
   著者らは、グラフ $G$ の適正なエッジ彩色を利用する。ヴィングの定理により、エッジは $\chi'(G) \le \Delta + 1 \le n$ 個のマッチングに分割できる。マッチング内の互いに素なエッジに対応するゲートは可換であり、並列に実行可能である。このスケジューリング手法をエッジ検出およびカウントの両方のオラクルに適用することで、回路の深さを$\Theta(n^2)$から$O(\chi'(G) + \log n)$へと削減する。これは一般のグラフでは$O(n)$、疎なグラフでは$O(\Delta + \log n)$となる。

2. グラフ状態クリーク・テスト（$\Gamma$ オラクル）：
   エッジをカウントする代わりに、著者らは、グラフがクリフォード演算であるグラフ状態の準備（controlled-Z (CZ) ゲートによる）を通じてのみ回路に導入されるオラクルを導入する。

• 構成： オラクル $\Gamma$ は、候補頂点集合 $H$（モジュロ演算の制約を満たすためのダミー頂点を含む）に対して作用する。これは、入力準備器（Input Preparator, $IP$）とその逆操作の間に、グラフ状態ユニタリ $A = \prod_{uv \in E} CZ_{uv}$ を挟み込むものである。
• スペクトル特性： 著者らは、任意の候補集合 $H$ に対して、オーバーラップ $a(H) = \langle 0 | \Gamma | 0 \rangle$ が、$H$ がクリークである場合に正確に $-1$になることを証明している。極めて重要な点として、非クリークに対して$|a(H)| \le 5/8$というタイトなスペクトル・ギャップを証明している（具体的には$K \ge 7$において$1/2 + 2^{-(K-1)/2}$）。この境界は、オーバーラップを$GF(2)$および$\mathbb{Z}_4$ 上の二次形式のガウス和へと帰着させることで導出されている。
• 非クリフォード・コスト： グラフ依存部分（$A$）が純粋にクリフォード演算であるため、すべての非クリフォード・ゲートはグラフに依存しないブロック（$IP$ およびディフューザー $S_0$）に限定される。その結果、エッジ数 $m$ に関わらず、非クリフォード・コストは $n$ に対して線形（$\Theta(n)$）となる。

3. 量子位相推定による有界誤差フェーズ・オラクル（Bounded-Error Phase Oracle via Phase Estimation）：
   $\Gamma$ は完全なフェーズ・オラクルではなく反射（reflection）であるため（非クリークはアンシラへ振幅が漏れる）、著者らは2量子ビットの量子位相推定（QPE）フィルタを適用する。これにより、反射を片側有界誤差フェーズ・オラクル $O_t$ へと変換する。

• 保証： クリークは確実にマークされる（固有位相 0）。非クリークは、$t=2$ の推定レジスタを用いた場合、確率 $\epsilon \le 2/27$ でマークされる。
• 探索： このオラクルは、振幅増幅（Høyerら）の枠組み内で使用され、$O(\sqrt{\binom{n}{k}})$ 回のオラクル呼び出しで $k$-クリークを見つける。

主な結果

• 深さ： 提案されたオラクルは、エッジ彩色を通じて線形深さ $O(n)$（または $O(\Delta + \log n)$）を達成しており、従来の $\Theta(n^2)$ のカウント回路に対して大幅な改善を実現している。
• 非クリフォード・コスト： グラフ状態オラクルは、非クリフォード・ゲートの数を $\Theta(m) \approx \Theta(n^2)$ から $\Theta(n)$ へと減少させる。フィルタリングされたオラクル $O_2$ のコストは、未フィルタリングの $\Gamma$ の約7倍であるが、依然として $n$ に対して線形である。
• 厳密なシミュレーション： 著者らは、2つの実世界の脳ネットワーク（マカック脳皮質およびマウス網膜）から抽出された312個の誘導部分グラフを用いて、厳密な状態ベクトルシミュレーションを行った。
  • 未フィルタリングのオラクル $\Gamma$ は、信頼できる振幅増幅として機能せず、低い成功確率（$\sim 0.3$）でピークに達し、振幅の漏れによって崩壊した。
  • フィルタリングされたオラクル $O_2$（$s=2$ のレジスタを使用）は、理想的な反復回数において、中央値 $0.92\text{--}0.99$ の成功確率を達成し、理論的な下限値と一致した。
• リソース比較： $K_n$ ($k=3$) のコンパイル済み回路において、グラフ状態オラクルは、深さの定数倍の増加はあるものの、$n \gtrsim 40$ において並列カウント・オラクルよりも非クリフォード・ゲートの効率において優れている。

意義と主張
本論文は、文献中でしばしば混同される4つの異なる記述を明確に分離していると主張している：

1. スケジューリング： クリーク問題に対しては、特定のオラクル・タイプに関わらず、エッジ彩色を通じて線形深さのオラクルが可能である。
2. コストの分離： カウント・オラクルは本質的に $\Theta(m)$ 個の非クリフォード・ゲートを必要とするが、グラフ状態オラクルはグラフ構造を完全にクリフォード・ゲート内に保持することができ、非クリフォード・コストを $\Theta(n)$ に削減できる。
3. スペクトル・ギャップ： グラフ状態テストは、非クリークに対して一様な境界（$|a(H)| \le 5/8$）を提供し、証明可能な有界誤差探索を可能にする。
4. アルゴリズムの厳密性： グラフ状態オラクルと位相推定の組み合わせにより、$O(\sqrt{\binom{n}{k}})$ のクエリ、線形深さ、およびクエリあたりの線形非クリフォード・コストを持つ、厳密な探索アルゴリズムが得られる。

著者らは、実用的な優位性について謙虚な姿勢を示している。シミュレーション可能なインスタンスサイズ（$n \approx 12$ 程度の高い $k$）においては、古典的ソルバーは瞬時に動作する。本研究の貢献は、古典的アルゴリズムの実行時間を打ち負かすことではなく、従来の明示的量子回路と比較して、回路の深さとフォールトトレラント・リソース・コスト（特にマジック状態の消費量）を削減すること、およびこれまでグラフ状態の手法には欠けていた厳密な誤差保証を提供することにある。本研究は、ランダムアクセス・ハードウェア（QRAM）を持たない、ハードワイヤード・回路モデルに特化したものである。