A polynomial-time classical sampler for noisy quantum circuits from statistical mechanics

技術要約：ノイズのある量子回路における多項式時間古典サンプリング

問題提起
本論文は、ノイズが存在する場合における量子優位性の限界を決定するという課題に取り組んでいる。理想的な量子コンピュータは古典的なコンピュータを指数関数的に凌駕できるが、実験的なデバイスはノイズの影響を受け、それが通常、計算能力を低下させる。既存の一般的なノイズのある回路に対する古典的シミュレーション手法では、ノイズが全状態を自明な一様分布へと駆動させるためには、回路の深さ（$d$）がシステムサイズに対して超対数的に成長（$d \sim \omega(\log n)$）する必要がある。ここで、重要な未解決の問いが残されている。すなわち、ノイズの強さがゼロでない場合、ノイズのある幾何学的に局所的な「最悪ケース」の量子回路は、システムサイズに依存しない（定数深さの）深さにおいて、古典的にシミュレート可能になり得るのだろうか？具体的には、著者らは、出力分布が一様性に収束する前に、ノイズのある幾何学的に局所的な量子回路が古典的にシミュレート可能になるかどうかを調査している。

手法
著者らは、統計力学と量子情報理論の技術を組み合わせた新しい古典サンプリングアルゴリズムを開発した。核となる手法は、以下の3つのステップで構成される。

1. ポリマーモデルへの写像:
   著者らは、ノイズのある量子回路の出力分布の周辺確率を、統計力学における抽象的なポリマーモデルの分配関数へと写像する。

   • 格子を、辺の長さが $2d$ の粗視化されたブロックへと分解する。
   • 「ポリマー」を、これらのブロックの連結集合として定義する。
   • ポリマーの重みは、そのポリマーのサポートに制限されたパウリ観測量のハイゼンベルク発展によって定義される。
   • 回路の幾何学的な局所性により、隣接しないブロックは互いに離れた後方ライトコーンを持つため、分配関数は、互いに適合する（重なり合わず、かつ隣接しない）ポリマ一の構成に関する和へと分解できる。

2. 切断されたクラスター展開:
   分配関数（およびしたがって対数周辺確率）を計算するために、著者らはクラスター展開を用いる。この手法では、分配関数の対数を「クラスター」の和として展開する。

   • アルゴリズムは、この展開を、$O(\log n)$ 個のブロックにサポートされるクラスターのみを合計するように切断する。
   • この近似の精度は、「重みの減衰（weight decay）」特性に依存する。すなわち、ポリマーの寄与は、そのサイズ（ブロック数）に対して指数関数的に減衰しなければならない。

3. ハイパーコントラクティビティによる重み減衰の証明:
   中心的な技術的貢献は、回路の深さ $d$ がシステムサイズに依存しない臨界閾値を超えるとき、ポリマーの重みが指数関数的に減衰することを証明することである。

   • 著者らは、**量子ハイパーコントラクティビティ（hypercontractivity）**と、デポラリジング・チャネルに対する $\ell_2$ ノルム収縮の境界を利用する。
   • 彼らは、ノルム変換の経路を構築する。すなわち、$\ell_\infty$ ノルムから出発し、$\ell_{1+(4d)^D}$ および $\ell_2$ ノルムを経由し、最終的に $\ell_1$ へと戻る経路である。
   • ハイパーコントラクティビティを適用してノルム間を遷移させ、デポラリジング・チャネルの収縮性（Fact 5.2）を用いることで、ノイズが局所的に蓄積されることを実証する。系は幾何学的に局所的であるため、ノイズによって導入されるエントロピー（体積に比例）は、生成される速度（境界に比例）よりも速く逃げることができず、結果として指数関数的に相関が減衰する局所的な高温相が導かれる。

主な結果
本論文は、以下の主要な定理（簡略化）を確立している：

• 定理: 各レイヤーの後に強さ $p$ の単一量子ビット・デポラリジング・ノイズが適用される、一元的な演算（unital operations）からなる任意の幾何学的局所量子回路に対して、回路の深さ $d$ が以下を満たす場合、逆多項式の全変動距離（および周辺確率に対する相対誤差）で出力分布からサンプリングできる多項式時間の古典アルゴリズムが存在する：
  $$d > d_{crit} = O(p^{-1} \log p^{-1})$$
• アルゴリズムの能力: 提供されるアルゴリズムは、出力分布の任意の周辺確率に対する完全多項式時間近似スキーム（FPTAS）である。これは、ノイズのない回路や $O(p^{-1})$ の深さ以下のノイズのある回路では古典的に困難であることが知られている「相対誤差サンプリング」を実現する。
• 複雑性の領域: この結果は、ノイズのある回路における複雑性のランドスケープにおける新しい領域を特定している。先行研究では、深さ $O(p^{-1})$ までの困難性と、$\log n$ （または $\omega(\log n)$）のスケーリングを持つ深さでのシミュラビリティが示されていたが、本研究は、深さが $O(p^{-1} \log p^{-1})$ を超えると、システムサイズに依存しない定数深さにおいてシミュラブルであることを証明した。

意義と主張
著者らは、非一元的（non-unital）または非局所的なリソース（中間回路測定とフィードバック、あるいは量子ビットのリセットなど）が、システムサイズに比例する計算の深さを達成するために根本的に必要であると信じるための、より徹底的な根拠を提供していると述べている。

• 量子から古典への転移: 本論文は、この結果を、開いた量子系における「熱（エントロピー）の蓄積」によって駆動される「量子から古典への転移」として解釈している。すなわち、熱を排出するための低温のバス（bath）が存在しない限り（すなわち、非一元的な操作がない限り）、系は自然に、古典的にシミュレート可能な高温相へと移行すると断じている。
• タイトネス（厳密性）: 著者らは、彼らの境界が対数因子を除いてタイトであると指摘している。なぜなら、深さ $O(p^{-1})$ 未満では相対誤差サンプリングが困難であることが証明されているからである。
• 汎用性: この結果は、特定のゲートセットや特定のノイズモデルに限定されていた従来の成果を包含し、任意の幾何学的局所量子回路（一元的な演算とデポラリジング・ノイズを持つもの）に適用される。
• 哲学的背景: 本研究は、開いた量子系の計算複雑性に焦に当てており、ノイズの多い多体系の自然なダイナミクスは、統計力学的なツールを用いて厳密に特徴付けられる「古典性への転移」を示すことを示唆している。

本論文は、特定の実機をシミュレートしたり新しいハードウェアを提案したりすることを目的としているのではなく、広範なクラスのノイズのある量子ダイナミクスに対するシミュラビリティの理論的境界を提供しており、そのような系における「量子優位性」は脆弱であり、特定の非一元的なエラー訂正メカニズムが採用されない限り、浅い深さに限定されることを示唆している。