技術要約：ガウス消去法のための量子回路

問題提起

ガウス消去法は、連立一次方程式の解法、行列のランク、行列式、および逆行列の計算のための基礎的なアルゴリズムである。抽象的な量子アルゴリズムはユニタリ演算によって定義されるが、その実用的な実装には、ビット列のマッピングに対する可逆的な古典的構成が必要となることが多い。重大な課題は、ガウス消去法が本質的に非単射的（多くの入力行列が同じ階段行列に写像される）であるため、可逆性を維持するために少なくとも $x-y$ 個のワークスペース（ゴミ）を必要とする点にある（ここで $x$ および $y$ は入力および出力のビット長である）。

これまでのガウス消去法の量子実装は、二進体 $GF(2)$ に限定されていた。これらの既存研究は、主に以下の2つの制限に直面していた：

1. ゴミの蓄積： 理論的な最小ワークスペース要件を満たせないか、あるいはアンコンピューティング（逆計算）できない有意な「ゴミ」（補完的な空間）を生成してしまう。
2. 複雑性の不一致： 特にトフォリ（Toffoli）の深さや量子ビット数に関して、古典的な実装と同じ漸近的複雑性を達成できていないことが多い。

さらに、任意の有限体 $GF(p^l)$ 上のガウス消去法のための汎用的な量子回路は存在しておらず、より広範な暗号学的および代数学的文脈における量子線形代数の適用可能性を制限していた。

手法

著者らは、任意の有限体 $GF(p^l)$ 上で動作するガウス消去法の可逆的な量子回路を提案している。その手法は、以下の3つの核心的な革新に基づいている：

1. 擬似階段形式 (Pseudo Row Echelon Form)

標準的なガウス消去法の非単射性に対処するため、著者らは擬似階段形式を導入している。

• 定義: 行列 $A'$ が擬似階段形式であるとは、その上三角成分が $A$ の標準的な階段形式と一致することを指す。下三角部分および対角部分は形式によって厳密に定義されているわけではなく、情報の格納に利用される。
• メカニズム: この変換により、本質的に非単射的な写像を、一対一（全単射）の変換へと変換する。操作を逆転させるために必要な情報は、下三角および対角成分内に保持されるため、最小限のテンポラリ量子ビットを利用しながら、結果を入力量子ビット上に上書きすることが可能となる。

2. アルゴリズム構造

提案されたアルゴリズム（Algorithm 1）は、行列を変換するために列を反復処理する。これは4つの可逆的なサブルーチンに依存している：

• ラベル付け (Labeling): ピボット指数（現在の列における最初の非ゼロ要素を持つ行）を特定し、それを単項形式（unary format）でエンコードする。著者らは、このプロセスを並列化して深さを減少させるために、再帰的なトーナメント型の構造を利用している。
• ピボット操作 (Pivoting): 最初の行をピボット行と入れ替える。これは、トーナメント型の入れ替えメカニズムを用いて実装され、「借りられた量子ビット（borrowed qubits）」（操作の終了時に初期状態に復元される未知の状態にあるアンシラ量子ビット）を用いて並列化できる。
• 行減算 (Row Reduction): ピボット行の要素をピボット要素で除算し、ピボット行を他の行から減算する。これには、並列化されたフィールド演算（乗算、逆元、加算）が含まれ、深さを最小限にするために借りられた量子ビットが使用される。
• ピボット指数の削除 (Deleting the Pivot Index): ラベル付けおよび部分的なピボット操作を逆転させ、ワーク量子ビットをゼロに戻すことで、補完的な空間に関するゴミが発生しないようにする。

3. 借りられた量子ビットによる並列化

主要な技術的貢献は、操作を並列化するための借りられた量子ビットの体系的な使用である。

• クリーンなアンシラ量子ビットを必要とする代わりに、未知の値を持つ可能性のある量子ビットを利用する。
• 著者らは、共有制御値やオペランドをこれらの借りられた量子ビットに転送し、並列操作を実行した後、借りられた量子ビットを元の状態に復元するための補正ステップを適用するという、Gidneyの手法を適応させている。
• このテクニックは、制御スワップ（ピボット操作における）および算術演算（行減算における）に適用され、回路の深さを大幅に減少させている。

主要な貢献と結果

1. 任意の有限体への一般化

$GF(2)$ に限定されていた従来の研究とは異なり、本設計は任意の有限体 $GF(p^l)$ に一般化されている。これにより、様々な暗号プリミティブや符号理論の問題に関連する、より複雑な代数的構造を扱うことが可能になる。

2. ゴミのない構成 (Garbage-Free Construction)

開発された回路は、補完的な空間に関するゴミのない構成を実現している。

• ガウス消去の結果は、入力量子ビットに直接上書きされる。
• 回路は中間計算のために $m-1$ 個のテンポラリ・ワーク量子ビットを必要とするが、これらは操作の終了までに完全にゼロに復元される。
• 決定的なことに、この回路は、これらのテンポラリ量子ビットおよび入力量子ビットを超えて、補完的な（ゴミとしての）空間を占有しない。これは、補完的な空間が $O(n^2)$ または $O(mn)$ に比例し、ゼロに戻されないことを要した以前の研究（[20]など）とは対照的である。本論文では、補完的空間を「初期状態がゼロであるが、終了時にゼロに戻されないワーク量子ビット」と定義しており、本設計はこのカウントをゼロにすることを保証している。

3. 複雑性の改善

論文内の表1に基づき、$GF(2)$ におけるサイズ $m \times n$（$m \ge n$）の行列の回路複雑性の定量的比較を以下に示す：

指標	従来の研究 ([9], [20], [5])	本研究
Toffoli カウント	$O(n^2m)$ ～ $O(n^2m^2)$	$O(n^2m)$
Toffoli 深さ	$O(nm)$～$O(n^2m \log^3 m)$| **$O(m \log^2 n + n \log^4 m)$**
テンポラリ空間	$0$～$m-2$| **$m-1$**
補完的（ゴミ）空間	$0$～$O(n^2)$| **$0$**

• $GF(2)$ において: 本回路は、対数因子を除いて最良の既知の漸近的Toffoli深さを達成し、かつ古典的な算術複雑性 $O(n^2m)$ と一致している。
• 一般の体において: 複雑性は、体サイズパラメータ $\alpha = l \lceil \log_2 p \rceil$ に従ってスケールし、同様の構造的効率性を維持している。

意義と主張

著者らは、本研究が線形代数の量子実装における重要な最適化を表すと主張している：

1. トレードオフの最適化: 本設計は、時間（深さ）と空間（量子ビット）のトレードオフを成功裏に最適化している。量子ビット数がボトルネックとなる近未来の量子ハードウェアにおいて極めて重要な要素である追加空間の使用を厳密に制限しつつ、古典的な算術複雑性に一致させている。
2. ゴミのない可逆性: 擬似階段形式を導入することで、ガウス消去法が、わずか $m-1$ 個のテンポラリ量子ビットのみを使用して、補完的なゴミ量子ビットを蓄積することなく可逆的に実行できることを実証した。これは、従来の $GF(2)$ 実装では達成されていなかった成果である。
3. 幅広い適用可能性: 任意の有限体への一般化により、非バイナリ体上の線形システム（特定の耐量子計算機暗号解析や符号理論のタスクなど）に関わる問題への量子アルゴリズムの範囲を拡大させた。

結論として、本論文は、さらなる最適化（乗算の深さの削減など）が可能であるとしつつも、現在の設計は、低い量子ビットオーバーヘッドと競争力のある時間複雑性のバランスを取りながら、可逆的なガウス消去法の新たなベンチマークを確立するものであるとしている。