Quantum group codes for non-Clifford logic: enhanced decoding, addressability and parallelizability

技術要約：非クリフォード論理のための量子群符号

問題提起
現在のフォールトトレラント量子計算スキームは、重大な空間および時間のオーバーヘッドに苦しんでおり、実用的な量子コンピュータの実現を阻害している。横断的（transversal）ゲートをサポートするCSS符号は、フォールトトレラントへの道筋を示す一方で、既存の構成には主に2つの制限が存在する：

1. 復号の複雑性： 非クリフォード横断的ゲート（マジック状態蒸留、すなわちMSDに不可欠）をサポートする最先端の量子代数幾何（AG）符号は、$O(n^3)$ の計算量を持つ復号アルゴリズムに依存している。この高い複雑性はMSDプロトコルへと波及し、その効率を制限している。
2. アドレス指定可能性と並列化可能性： 横断的な非クリフォードゲートを持つ既存の符号は、通常、すべての物理量子ディットに対して同時に作用するグローバルな操作を実行する。このような「アドレス指定可能性（addressability）」の欠如（特定の論理量子ディットのサブセットをターゲットにする能力）は、アルゴリズムの柔軟性を制限する。さらに、アドレス指定可能なゲートを持つ符号の存在は近年の研究で示されているが、それらの構成は非常に特定の推移的なAG符号に依存しており、これらのゲートの並列化には回路深さを削減するためのさらなる最適化が必要である。

手法
著者らは、特定の乗法特性を持つ古典的な準群符号（quasi group codes）に基づく、量子群符号に基づくフレームワークを提案する。この手法は、以下の3つの主要な段階で進行する：

1. フレームワークの定義（量子群符号）：
   著者らは、基礎となる古典符号（$C_0$ および $C_1$）が準$G$符号（群環 $F_q[G]$ の右イデアルと同型）であるような、量子CSS符号のクラスを定義する。商写像に対する$G$加群準同型切断の存在を保証することで、これらの量子符号が並列可能かつアドレス指定可能な横断的多制御Z（$C_{m-1}Z$）ゲートを許容する条件を確立する。

• 鍵となるメカニズム： 群作用により、論理量子ディットの特定の軌道（orbit）に対して、深さ1の物理回路を用いて論理ゲートを実装するための変調関数を構築することが可能になる。

2. リフティングによる符号構成：
   良好なパラメータと効率的な復号を持つ符号を生成するために、著者らは類体論（具体的には[CG26]）に基づくリフティング手順を採用する。

• 著者らは、$m$-乗法特性を満たす良好な古典AG符号 $C$ （$F_q$ 上）から出発する。
• 基底となる関数体の非分岐アーベル拡大を構築し、新しい符号 $\tilde{C}$ （$F_{q^2}$ 上）を作成する。
• このリフティングプロセスは、新しい符号に大きなアーベル置換自己同型群 $G$ を付与し、それを自由 $F_{q^2}[G]$-加群にする。決定的なことに、このリフティングは、横断的ゲートに必要な$m$-乗法特性を保持する。

3. 復号の最適化：
   著者らは、リフトされた符号の加群構造を利用する。標準的なAG符号は$O(n^3)$の時間復号を必要とするが、自由加群構造により、群環上の高速行列乗算を利用した復号アルゴリズムの適応が可能になる。これにより、線形な復号半径を持つ準二次時間復号器（$O(n^2 \cdot \text{polylog}(n))$）が実現される。

主な貢献と結果

• 定理 1.1（符号ファミリー）： 本論文は、2つの$q$次元量子群符号（ここで $q=t^4$）のファミリーを構築する：

  1. 完全アドレス指定可能ファミリー： パラメータ $[[n, \Theta(n/\log n), \Theta(n)]]_q$ を持つ符号。これらは、完全にアドレス指定可能な横断的 $C_{\tilde{m}-1}Z$ ゲートを許容する。$m$ 個の符号ブロックを含む論理回路の深さは、$O(k^{\tilde{m}-1})$ に抑えられる。
  2. 高レート・ファミリー： パラメータ $[[n, \Theta(n), \Theta(n)]]_q$ を持つ符号。これらは、グローバルな横断的 $C_{\tilde{m}}Z$ ゲート、および $\Theta(\log n)$ 個の軌道にわたる軌道ごとのアドレス指定可能な $C_{\tilde{m}-1}Z$ ゲートを許容する。
  • いずれの場合も、これらの符号は、線形な復号半径を持つ $O(n^2 \cdot \text{polylog}(n))$ 時間の復号器をサポートしており、これは従来のAGベースの構成の $O(n^3)$ の複雑さに対する大幅な改善である。

• 系 1.2（マジック状態蒸留）： 高レート・ファミリーをマジック状態蒸留（MSD）プロトコルに適用することにより、著者らは、$O(n^2 \cdot \text{polylog}(n))$ の時間複雑性を持つ、量子ビットCCZマジック状態のための定数オーバーヘッド蒸留プロトコルの存在を実証する。これは、最先端の $O(n^3)$ プロトコルと比較して、時間複雑性のほぼ線形な削減を表している。

• 並列化可能性： 本研究は、論理的な多制御Z回路が高い程度に並列化可能であることを確立している。密な回路において、最小の深さは $O(k^{m-1})$ に制限され、これはそのような回路にとって最適である。

意義
本論文は、以下の通り、フォールトトレラント量子計算における重要なボトルネックに対処することを主張している：

1. 効率性： 復号の複雑性を立方から準二次へと減少させることにより、MSDプロトコルの時間オーバーヘッドを大幅に減少させ、実用的なフォールトトレラント計算の実現をより身近なものにする。
2. 柔軟性： アドレス指定可能かつ並列化可能な非クリフォードゲートの導入は、グローバルな操作を超え、より精密な論理量子ディットの制御を可能にする。これは、グローバルなもつれを必要としない回路コンパイルやアルゴリズムにとって不可欠である。
3. 一般化： この構成は、以前の研究で使用されていた特定の推移的AG符号を超え、大きなアーベル自己同型群を持つ、より広範なリフトされたAG符号のクラスを利用している。これは、横断的な非クリフォードゲートを持つ量子符号を設計するための、より多用途なツールキットを提供する。

著者らは、これらの結果が理論的な構成および既存のリフティング技術から導出されており、これらの変換が横断的な非クリフォードゲートに必要な特性を保持しつつ、復号効率を向上させていることを強調している。