Quantum WalkScore: Benchmarking Quantum Computers on the Graph Nodefinding Problem

技術要約：Quantum WalkScore (QWS)

問題の定義
本論文は、NISQ（Noisy Intermediate-Scale Quantum）および将来の誤り耐性量子コンピュータの成熟度を評価するための、アプリケーション指向のベンチマークの必要性に対処している。既存のベンチマークは物理ゲートの忠実度やランダム回路サンプリングに焦点を当てているが、有望な量子ルーチン、具体的には**離散時間量子ウォーク（DTQW）および量子振幅増幅（AA）**を利用して実用的なグラフ問題を解決するベンチマークは不足している。著者らは、グラフノード探索問題に焦 lượcしている。これは、無向グラフ内の特定の「マークされた」ターゲットノード $v_t$ を、ソースノード $v_0$ から特定する問題である。この問題は、通信ルーティング、データベース検索、複雑なネットワーク解析などの実世界のアプリケーションにおける基本的な構成要素として機能する。

手法：Quantum WalkScore (QWS) プロトコル
著者らは、量子コンピュータが成功裏に解決できる最大の問題サイズを測定するために設計された、スケーラブルなベンチマークプロトコルであるQuantum WalkScore (QWS) を提案している。

• グラフファミリー: ベンチマークでは、単純さ、スケーラビリティ、およびハードウェアへの適用性のバランスをとるために、以下の2つの特定のグラフトポロジーを利用する：
  1. サイクルグラフ: $2^n$ 個のノードを持つ1次元構造で、各ノードは2つの隣接ノードと接続されている。
  2. 2Dトーラスグラフ: $2^n \times 2^n$ 個のノードを持つ2次元構造で、各ノードは4つの隣接ノードと接続されている（周期境界条件）。
• 問題インスタンス: $(n, d)$ によって定義される。ここで、$n$ は量子ビット数、$d$ はソースノードとターゲットノードの間の距離（最短経路エッジ数）である。
• アルゴリズム・ルーチン:
  1. 初期化: システムを状態 $|v_0\rangle$ に初期化する。
  2. 離散時間量子ウォーク (DTQW): ウォーカーは $num\_w$ ステップ進化する。プロトコルでは、到達可能性を確保するために $num\_w \ge d$ かつ $num\_w \equiv d \pmod 2$ であることが要求される。偏りのないウォークのために、アダマール・コインが使用される。
  3. 振幅増幅 (AA): ターゲット状態を観測する確率を高めるために、DTQWルーチンをAAフレームワーク（Brassardら）内に組み込む。これには、ターゲットおよび初期状態に関する反射の $num\_aa$ 回の反復が含まれる。
  4. 測定: 成功確率 $p_{exp}$ は、ターゲットノードの状態が観測される確率として測定される。
• スコアリング基準:
  • 閾値確率 ($p^*$): ランダムな推測よりも有意に高い成功を保証するために、動的な閾値が定義される。距離 $d \le 2$ の場合、$p^* = 1/3$ である。$d > 2$ の場合、$p^* = 1/5 + 1/2^d$ である。
  • メトリック: 成功確率は、複数のバッチ（1000ショットの4バッチ）および複数のターゲットノード・インスタンス（サイクルに対して2つ、トーラスに対して4つ）にわたって平均化される。
  • QWSスコア: スコアは、最初の失敗が発生する前に、測定された成功確率が $p^*$ を超える最大の（$n, d$）である。スコアは、$QWS_{cycle} = 2^{e_n-1} + e_d$ および $QWS_{torus} = 2^{e_n} + e_d$ として計算される（ここで $(e_n, e_d)$ は最後の成功したインスタンスを示す）。

主な貢献

1. プロトコル設計: DTQWとAAという、将来の量子アルゴリズムにおいて極めて重要な2つのルーチンを統合した、完全なアプリケーション指向のベンチマークプロトコルの導入。
2. スケーラビリティと再現性: プロトコルはあらゆるゲート型量子コンピュータに適用可能となるよう設計されており、標準化された実験パラメータ（ショット数、バッチ処理）を備え、柔軟なアルゴリズムパラメータ（$num\_w, num\_aa$）はエンドユーザーによる最適化に委ねられている。
3. 理論的および経験的分析: 理論的なパラメータが存在すれば理論上あらゆる問題サイズを解決できるという保証とともに、アルゴリズムおよびネイティブ・ハードウェア実装の両方に関する詳細なリソース見積もり（回路深さのスケーリング）を提供している。
4. 実験的検証: プロトコルは、3世代のIBM量子プロセッサ（Heron r2, Heron r3, Nighthawk r1）上で実行され、現在のハードウェア能力の概念実証的な評価を提供している。

結果

• 無ノイズ・シミュレーション: 理想的な量子コンピュータ上でのシミュレーションは、このベンチマークが大きな問題サイズに対して解決可能であることを示している。「suff-perf」シナリオ（AAの反復回数を最小化する）では、成功確率は閾値付近に留まる。「best-perf」シナリオでは、成功確率は1に近づくが、これにはより高い回路深さが要求される。
• 回路深さのスケーリング: 理論的なアルゴリズムの深さは $O(nd)$ でスケールする。しかし、IBMのHeronアーキテクチャにトランスパイルされると、ネイティブの深さはサイクルグラフに対して $O(n^{3.45}d)$、2Dトーラスグラフに対して $O(n^{2.2}d)$ となり、ハードウェアのマッピングに伴う重大なオーバーヘッドが浮き彫りになる。
• IBMハードウェア上での実験的性能:
  • ibm_kingston (Heron r2) プロセッサ上での実験では、ノイズとデコヒーレンスにより、問題サイズが増加するにつれて成功確率が急速に低下することが示された。
  • システムは、問題サイズ (3, 1) までのみ閾値を通過することに成功した。それ以降のサイズでは、成功確率が急落し、ランダムな推測と同等の結果となった（ただし、問題サイズ (4, 1) は例外であったが、連続した成功シーケンスとはみなされない）。その結果、「suff-perf」シナリオにおけるサイクルグラフのQuantum WalkScoreは5と決定された。
  • より大きなインスタンス（例：ゲート数 > 700）では、結果はランダムな推測と区別がつかないレベルまで劣化した。
  • Heron r2, Heron r3, Nighthawk r1の比較では、同様の傾向が見られ、Heron r3の方がわずかに精度が高かったが、いずれのアーキテクチャも約1000ゲートを超える回路には苦戦した。

意義と主張
本論文は、QWSが抽象的なハードウェア指標と実用的なアプリケーション・パフォーマンスの間の溝を埋めるための必要なツールであると主張している。グラフのノード探索問題に焦点を当てることで、最適化や探索タスクに必要な不可欠な量子プリミティブ（DTQWおよびAA）を実行するハードウェアの能力を直接評価している。

著者らは、QWSがアルゴリズムのパラメータとハードウェアの制限との相互作用を浮き彫りにすることを強調している。結果は、理論的な枠組みによって大きな問題を解決できる一方で、現在のNISQデバイスは回路の深さとエラーの蓄積によって制限されていることを示している。論文は、QWSがNISQデバイスと将来の誤り耐性量子コンピューティング（FTQC）デバイス間の性能差を区別し、量子コンピュータの成熟度を追跡するための、意味のある解釈可能なスコアを提供すると結論付けている。現在のハードウェアで達成されたスコア5という控えめな数値は、これらのアルゴリズムを大規模な実用的問題に適用する前に、依然として重大な技術的課題が残っていることを強調している。