Approximate simulation of complex quantum circuits using sparse tensors

技術要約：疎なテンソルを用いた複雑な量子回路の近似シミュレーション

問題提起
量子回路を古典コンピュータでシミュレートすることは、検証可能な量子優位性の境界を定義し、量子多体系の問題を解決し、ハードウェア開発を導く上で不可欠である。行列積状態（MPS）や密度行列繰り込み群（DMRG）などのテンソルネットワーク法は、複雑な回路をシミュレートするための最先端の手法となっているが、これらは効率性を達成するために、基礎となる対称性や低次元性に依存することが多い。さらに、一般的な古典的シミュレーションは複雑性理論（$P \neq NP$）によって制限されており、ユニバーサルな多項式時間シミュレータの存在を阻んでいる。著者らは、特異値分解（SVD）や基礎となる対称性、あるいは低次元性を必要とせず、従来のテンソルネットワークが苦戦する可能性のある回路を明確にターゲットとした、量子状態を近似的にシミュレートできるツールの必要性を指摘している。

手法：切断された疎テンソルシミュレーション（TruSTS）
本論文では、疎に分布したテンソルを用いて量子回路を近似的にシミュレートする手法であるTruSTSを紹介する。コアとなるアプローチは、$N$量子ビットの量子状態 $|\psi\rangle$ を、$k$ 個の基底状態（$k \le 2^N$）の線形結合である疎な状態 $|\phi\rangle$ として表現することである。

• データ構造: 疎な状態は、以下のサイズ $k$ の2つの固定長配列を使用して格納される：
  1. $x[x_i]$：基底状態のバイナリビット文字列を表す整数の座標配列。
  2. $\alpha[\alpha_i]$：それらの基底状態に対応する複素確率振幅の配列。
  3. 整数のポインタ nnz は、現在格納されている要素の数を追跡する。
• ビット演算縮退アルゴリズム: 量子ゲート（テンソル $\hat{U}$ で表される）を適用するために、アルゴリズムは圧縮疎行列（CSR）形式の行列乗算に着想を得たビットソート戦略を採用する：
  1. ゲートによって結合される量子ビットを選択するためのビットマスクを定義する。
  2. 状態配列を「結合されていない」ビット（マスクの補集合）に基づいてソートする。これにより、ゲートが同一に作用する計算的に独立したサブ配列へと基底状態がグループ化される。
  3. 各サブ配列に対して、独立した $4 \times 4$ 行列縮退を通じてゲートを適用する。
  4. このプロセスにより、非ゼロ項の数（nnz）がゲート適用ごとに最大4倍まで増加する場合がある。
• 切断（Truncation）: nnz の指数関数的な増加を防ぐため、アルゴリズムは各ゲート適用後に状態をサイズ $k$ に切断する。論文では2つの切断戦略を比較している：
  • Top-k: 確率振幅が最大の $k$ 個の項を保持する。
  • Random-k: ランダムに選択された $k$ 個の項を保持する。
  • 切断による確率質量の損失を補うために、$\gamma$ という繰り上げ因子が $|\phi\rangle$ に適用される。

主要な貢献と理論的導出
著者らは、繰り上げパラメータ $\gamma$ とシミュレーション忠実度 $f = |\langle \psi | \phi \rangle|^2$ の間の関係を導出している。

• 忠実度の境界: ランダムな量子回路において、期待される忠実度 $\bar{f}$ は、近似的に $\gamma^2$（保持された確率質量）に等しく、干渉項によるわずかな正の偏差が生じることを確立している。
• 上限と下限:
  • 下限 $\bar{f}_{min} \approx 1/2^N$ は、状態が1つのランダムな基底状態に切断された場合に導出される。
  • 上限 $f_{max}$ は、出力分布がポーター・トーマス分布に従うと仮定して導出される。これは、回路実行の「後」に最も確率の高い $k$ 個のビット文字列を特定して保持できた場合に得られる、最高の忠実度を表している。論文では、$f_{max} \approx d(1 - \ln d)$ （ここで $d = k/2^N$ は切断割合）であると述べている。

結果
著者らは、層状に配置されたHaarランダムな2量子ビットユニタリからなるランダム量子回路を用いて、TruSTSのベンチマークを行った。

• 忠実度 vs 切断: $N=24$ 量子ビットのシミュレーションでは、忠実度は繰り上げ係数の二乗 $\gamma^2$ にほぼ比例してスケールすることが示された。Top-k 切断は、確率を保持する項に集中させることで、Random-k 切断よりも一貫して優れた性能を示した。
• 実行時間のスケーリング:
  • $k$ に対して: 1ゲートあたりの実行時間は、保持される項の数 $k$ に対して線形にスケールする。
  • $N$ に対して: $k \ll 2^N$ の場合、1ゲートあたりの実行時間は量子ビット数 $N$ に関してほぼ一定である（$N=64$ までテスト済み）。これは、状態が疎である限り、アルゴリズムが全ヒルベルト空間のサイズに依存するオーバーヘッドを導入しないことを示している。
  • メモリ: 本手法はフルサイズの $2^N$ メモリを割り当てることを回避し、$k$ 個の項のみを格納する。
• MPSとの比較: qumb ライブラリを用いた $N=24$ 量子ビット（5層）の行列積状態（MPS）との予備的な比較では、テストされたパラメータにおいて、MPSはほとんどのデータ範囲でより良好な実行時間と忠実度のトレードオフを提供し、同等の実行時間でより高い忠実度を維持することが示された。しかし、TruSTSは実行時間の増加に伴う安定した予測可能な忠実度の減衰を示し、$f \sim 10^{-8}$ 付近の低限界に達する。

意義と主張
本論文は、特に以下のようなシナリオにおいて、テンソルネットワークベースのシミュレータの能力を拡張するためのツールとしてTruSTSを位置づけている：

1. 対称性が存在しない場合: 本手法は、基礎となる対称性に依存しない。
2. SVDを回避する場合: 特異値分解（SVD）の計算コストをかけずに切断を実現する。
3. 固有の疎性が存在する場合: 本手法は、量子状態が本質的に疎である場合に魅力的である。

著者らは、TruSTSが高い忠実度を厳密に要求されない回路において、忠実度と実行時間の有用なトレードオフを提供することを主張している。彼らは、この研究が、疎なテンソルネットワークの最適化や、複雑な量子系の古典的シミュレーションの限界をさらに押し広げるためのテンソルネットワーク収縮順序最適化戦略との組み合わせに関する将来の研究の基礎となるものであることを強調している。また、彼らは謙虚な姿勢を保ち、厳密な代替手法との比較や、測定可能な量（クロスエントロピー忠実度など）を用いた調査が重要な今後の課題であることを述べている。