Good Stabilizer Codes from Shallow Clifford Circuits with Random Matchings

技術要約：ランダム・マッチングを用いた浅いクリフォード回路による良質なスタビライザー符号

問題提起
浅いエンコーディング回路を用いて、強力なパラメータ（高いレートと線形距離）を持つ量子誤訂正符号（QECC）を構築することは、フォールトトレラント量子計算における根本的な課題である。CSS構成や$\mathbb{F}_4$上のスタビライザー符号などの確率的な存在証明は、漸近的に優れた符号の存在を保証しているが、それらは本質的に、エンコーダーの回路深さや制限されたゲートセットを低くすることを保証するものではない。BrownとFawzi [BF13b]による先行研究では、全結合（all-to-all connectivity）と完全な2量子ビット・クリフォード群（$C_2$）を用いたランダム・クリフォード回路が、量子ギルバート・ヴァーシャモ（GV）のレート・距離のトレードオフを達成できることを示したが、それには$O(\log^3 n)$の回路深さが必要であった。重要な未解決問題は、追加のアドバンサ（ancilla）を用いずに、より制限されたハードウェアに優しいゲートセット（具体的には、CNOT、アダマール、およびフェーズゲートといった基本クリフォード生成元）を使用して、この最適なトレードオフを大幅に浅い深さ（$O(\log n)$）で達成できるかどうかであった。

手法
著者らは「ランダム・マッチング回路」アーキテクチャを提案し、分析する。エンコーディング回路は、$T$個の独立したレイヤーで構成される。各レイヤーにおいて：

1. ランダム・マッチング： $n$個の物理量子ビットが、一様にランダムな完全マッチングによってペアにされる。
2. ゲート適用： 各ペアに対して、ランダムな2量子ビット・クリフォードゲートが適用される。
3. ゲート分布： ゲートは、2量子ビット・クリフォード群$C_2$上の分布$p_2$から抽出される。著者らは、$p_2$に対して以下の3つの正則性条件を課している：
   • 双方向不変性（Bi-invariance）： 非恒等な単一量子ビット・パウリ（符号を除いて）に対して推移的に作用する局所クリフォードの部分群による左および右からの乗算に対する不変性。
   • 正のエンタングルメント（Positive Entanglement）： 分布が、少なくとも1つのエンタングルゲートに対して正の確率を割り当てること。
   • 可逆性（Reversibility）： 分布が逆元を取ることに対して不変であること（$U \sim p_2 \implies U^\dagger \sim p_2$）。

主要な例として、「局所的にトウィルされたCNOT（locally twirled CNOT）」分布が挙げられる。これは、CNOTゲートが、独立かつ一様にランダムな単一量子ビット・クリフォード（または特定の巡回部分群$\{I, HS, (HS)^2\}$）によって共役変換されるものである。

分析フレームワーク
符号の特性を証明するために、著者らはランダム回路の二次モーメントのダイナミクスを分析する。

1. 二次モーメント演算子： 同一のパウリストリングのペアに作用する二次モーメント演算子$M_{circ}$を定義する。$p_2$の双方向不変性により、この演算子のダイナミクスは、特定のパウリの種類ではなく、バイナリ・サポート・ストリング（非恒等パウリの場所）のみに依存する。
2. マルコフ連鎖への簡約： サポート・ストリングの進化は、長さ$n$のバイナリ・ストリング上の可逆なマルコフ連鎖$Q_0$としてモデル化される。この連鎖は、さらにハミング重み$w \in [n]$上の「重み連鎖」$P$へと簡約される。
3. 定常分布： 重み連鎖の定常分布は、$\pi(w) = \binom{n}{w} 3^w / (4^n - 1)$であり、これは$w \approx 3n/4$でピークを持つ。
4. ヒットタイム分析： 証明の核心は、重み連鎖が「線形重み」領域に到達し、その後、定常平均$3n/4$の周囲の狭い区間に到達するためのヒットタイムを境界付けることにある。
   • 低重み領域： マルチンゲール集中不等式（アズマ・ヘフディング不等式）とドリフト分析を用いることで、低重みから開始した場合、重みが指数関数的に速く増大し、高確率で$O(\log n)$ステップ以内に線形重み（$O(n)$）に到達することを示す。
   • 定常性への収束： 線形重み領域に入ると、連鎖は定数ステップ以内に$3n/4$の近傍へと急速に収束する。
   • 可逆性： 連鎖の可逆性により、重みが低重み領域に戻る確率（これは低重みの誤り演算子に対応する）を抑えることができ、これにより符号距離が高いことが保証される。

主な貢献と結果

1. 最適な深さ： 著者らは、ランダム・マッチング回路が深さ$O(\log n)$で量子ギルバート・ヴァーシャモのレート・距離のトレードオフを達成することを証明した。これは、BrownとFawzi [BF13b]の$O(\log^3 n)$の深さを改善し、線形距離エンコーダーの理論的なライトコーンの下限と一致する。
2. 制限されたゲートセット： この結果は、3つの正則性条件を満たす広範なゲート分布に対して成立する。決定的なことに、これには、局所的なランダム・クリフォード・トウィルを補完された、唯一のエンタングルゲートがCNOTである場合も含まれる。これは、基本クリフォード生成元の十分性に関する未解決問題に対処している。
3. 形式的な保証： 任意の固定された$\delta > 0$および十分に大きな$n$に対して、レート$k/n$が以下を満たす場合：
   $$\frac{k}{n} < 1 - H\left(\frac{d}{n}\right) - \frac{d}{n}\log_2 3 - \delta$$
   $O(\log n)$の深さを持つランダム・マッチング回路は、確率$1 - n^{-m} - 2^{-\Omega_\delta(n)}$で、距離少なくとも$d+1$の$[n, k]$スタビライザー符号を定義する。
4. ゲート数の最適性： この構成は$O(n \log n)$個の2量子ビット・ゲートを使用する。著者らは、ライトコーンの議論（命題A.2）を通じて、独立なランダム・マッチング・モデル内では、一定の成功確率で線形距離を達成するために$\Omega(n \log n)$個のゲートが必要であることを証明しており、彼らのゲート数はこの特定のアンサンブル・モデルにおいて最適である。

意義
本論文は、全結合アーキテクチャにおいて、基本的でハードウェアに優しいゲート（具体的には、局所的なトウィルを伴うCNOT）のみを用いて、最適な$O(\log n)$の回路深さで量子ギルバート・ヴァーシャモ・バウンドが達成可能であることを示している。これは、確率的な存在証明と実用的なエンコーダーの複雑さの間の溝を埋めるものであり、高度に構造化された浅いランダム回路が、良質な高距離スタビライザー符号を生成するのに十分であることを示している。この研究は、2量子ビット・クリフォード群全体における完全なランダム性は必要ではなく、むしろゲート分布に関する特定の正則性条件（双方向不変性、エンタングルメント、および可逆性）が、良好な符号特性を実現するために必要なパウリの拡散を駆動するのに十分であることを明らかにしている。

限界と未解決問題
著者らは、彼らの結果が、決定的な明示的ファミリではなく、ランダムなアンサンブルの存在証明を提供していることを指摘している。マッチングのシーケンスとトウィル過程の決定論的化（derandomization）は、依然として未解決の方向である。さらに、この構成は高い距離の符号をもたらすが、効率的な復号アルゴリズムを提供するものではない。このアンサンブルに対する効率的な復号器の設計は未解決の問題である。加えて、正則性条件（特に双方向不変性と可逆性）は彼らの証明には十分であるが、良質な符号の存在にとって厳密に必要であるとは限らず、これらの仮定をさらに緩和できる可能性を示唆している。