The cost of simulating classically tractable quantum circuits and dynamics

技術要約：古典的に計算可能な量子回路およびダイナミクスのシミュレーションコスト

問題提起
本研究が取り組む中心的な問題は、理論的に古典シミュレーションが可能である量子進化の、実用的な効率性である。特定の構造化された量子プロセス（例：クリフォード回路、自由フェルミオン力学、低もつれ系）は多項式時間の古典アルゴリズムを持つことが確立されているが、多項式時間複雑度はあくまで漸近的な記述である。これは、古典シミュレーションが直接的な量子ハードウェア上での実行よりも実用的に好ましいかどうかを、必ずしも決定するものではない。

著者らは、重要なギャップを特定している。すなわち、異なる多項式のスケーリングが、特に高価な前処理や量子データの取得が必要な場合に、劇的に異なる計算コストをもたらし得るということである。本論文は次のように問いかける。「もしある量子進化が古典的にシミュレート可能であるならば、それを古典的にシミュレートすることは、量子ハードウェア上で実行することよりも実際にリソース効率が良いと言えるだろうか？」この問いは、古典的なシミュラビリティ（計算可能性）が有限のシステムサイズにおいては成立しない可能性があること、特に未知の入力状態に関する情報を取得するコストを考慮した場合に、その保証が揺らぐことに端を発している。

手法
著者らは、$T$ 個の回路インスタンスにおける期待値 $f_U(\rho, O) = \text{Tr}[U\rho U^\dagger O]$ を推定するための2つの計算経路を比較している。

1. 量子シミュレーション (QS): 量子ハードウェア上での直接実行。量子デバイスが状態を準備し、進化させ、測定を行う。古典コンピュータは結果を処理し、パラメータを更新する。
2. 古典シミュレーション (CS): 量子進化を多項式時間の古典計算（サロゲート）に置き換える「量子に着想を得た」アプローチ。決定的なのは、初期状態 $\rho$ が未知である場合、CSは $\rho$ を特徴付けるための初期の量子データ取得段階（例：古典シャドウやトモグラフィー）を必要とする可能性があることである。このデータは、その後の回路インスタンスに対して再利用される。

比較には3つのリソース指標を用いる：

• 量子サンプル複雑度: $\rho$ のコピー（回路ショット）に必要とされる数。
• 量子時間複雑度: 単一のサンプルに必要とされる回路深さ。
• 古典時間複雑度: 基本的な古典操作の数。

分析は、以下の7つの古典シミュレーション可能な回路ファミリーを対象としている：

1. クリフォード回路
2. 浅い局所回路（ハードウェア効率的アンザッツ）
3. マッチゲート（自由フェルミオン）回路
4. $S_n$-等変回路
5. $U(1)$-等変回路
6. 量子畳み込みニューラルネットワーク (QCNN)
7. ADAPT-VQE 回路

各ファミリーについて、著者らは、一回限りのコスト（例：サロゲートの構築、状態データの取得）とインスタンスごとのコスト（例：新しいパラメータに対するサロゲートの評価）を区別して、リソース複雑度を導出している。これには、Gottesman-Knillシミュレーション、g-sim（リー代数シミュレーション）、Pauli Propagation、およびMajorana Propagationなどのフレームワークを利用している。

主な結果
本論文は、理論的な複雑度の境界を、代表的なハードウェア仕様（IonQ, IBM, Google, Rigetti, Quantinuum）およびクラウド価格モデルを用いた推定ウォールクロック時間と金銭的コストへと変換している。

1. 多項式シミュラビリティ $\neq$ 実用的な優位性: 多項式時間の古典アルゴリズムが存在することは、有限のシステムサイズにおいてCSがQSよりも高速または安価であることを保証しない。相対的な優位性は、回路インスタンスの数 ($T$) と、支配的なコストの具体的な多項式の次数に大きく依存する。
2. 一回限りのコストとインスタンスごとのコストのトレードオフ:
   • QS は、すべてのインスタンスに対してサンプリングおよび回路実行のコストが発生する。
   • CS は、多くの場合、量子データ取得と前処理という大きな一回限りのコストを伴うが、その後のインスタンスごとの古典評価コストは低くなる。
   • 「クロスオーバー」ポイントが存在し、初期のオーバーヘッドを償却できるほど $T$ が十分に大きくなった場合にのみ、CSがより効率的となる。
3. 入力状態の知識の影響:
   • 入力状態が古典的に既知である場合（例：ADAPT-VQEにおけるハートリー・フォック）、CSは量子データ取得を完全に回避できるため、大幅に高速かつ安価になり得る。
   • 入力状態が未知である場合、それを特徴付けるためのコスト（シャドウ経由など）により、CSはたとその後のシミュレーションが多項式であっても、極めて高価になる可能性がある。
4. フェルミオンの局所性とシステムサイズ: マッチゲート回路においては、観測量のフェルミオン局所性 ($\kappa$) がCSのコストを劇的に左右する。$\kappa$ が高い場合（例：$\kappa=6$）、古典的なテンソル縮約コスト ($O(Tn^7)$) およびシャドウのサンプル複雑度が増大し、CSが多項式の漸近的スケーリングを持つにもかかわらず、中規模のシステムサイズではQSの方が高速になるケースが多い。
5. ウォールクロック時間 vs 金銭的コスト: ウォールクロック時間が速いアプローチが、必ずしも最も安価なアプローチとは限らない。
   • CSは繰り返しの量子実行時間を削減できるが、大規模な一回限りの量子データ取得予算を必要とする。
   • $T$ が小さい場合はQSの方が安価であることが多く、$T$ が大きい場合はCSの方が安価になる可能性があるが、そのクロスオーバーポイントはハードウェアプラットフォームや回路ファミリーによって異なる。
6. メモリ制約: 本論文は、メモリ要件（空間複雑度）が時間よりも深刻なボトルネックになり得ることを強調している。例えば、大規模なシステムのために古典シャドウのデータや中間テンソルを保存するにはテラバイト単位のメモリが必要となり、実行時間の推定では捉えきれない物理的な制約を課すことになる。

意義と主張
本論文は、多項式リソースによる古典的シミュラビリティの保証だけでは、好ましい実装方法を決定するには不十分であると結論付けている。

• 異なる効率性の概念: 古典的シミュラビリティ、ウォールクロック時間の優位性、および金銭的優位性は、それぞれ異なる概念である。ある手法は多項式でシミュレート可能であっても、大きな定数因子、高次の多項式、あるいは高価な一回限りのオーバーヘッドのために、実用的に困難な場合がある。
• 文脈依存性: QSとCSの選択は、具体的な問題のパラメータ、すなわち回路インスタンスの数 ($T$)、入力状態の既知性、観測量の局所性、および特定のハードウェアへのアクセス・コストに依存する。
• 実用的な指針: 本研究は、古典的にシミュレート可能な量子計算を、実際にいつ古典的に実行すべきかを評価するための枠組みを提供している。これは、未知の入力状態を持つ問題や、フェルミオンの局所性が高い問題においては、古典アルゴリズムが存在する場合でも、直接的な量子実行の方がリソース効率の高い選択肢であり続けることを示唆している。

著者らは、本解析が決定的なハードウェアのベンチマークではなく、有限のリソース比較であることを強調しており、エラー抑制、フォールトトレランス、および並列化といった要因がこれらの定量的なクロスオーバーを変化させる可能性があることを述べている。しかし、「一回限りのオーバーヘッド vs 繰り返しのサンプリングコスト」が実用的な効率性を決定するという根本的なメカニズムは、依然として強固である。