The power of constant-depth quantum circuits of unbounded size

技術要約：非限定的なサイズの定数深さ量子回路の威力

問題提起
本論文は、回路サイズおよび補助空間（ancillary space）への制限を取り除いた場合の量子回路の計算能力を調査している。古典的計算量理論において、$AC^0$ クラス（無制限のファンインを持つAND/ORゲートを備えた定数深さ回路）はパリティを計算できない。しかし、多項式サイズの制限が解除されると、選言標準形（DNF）構成によって、あらゆるブール関数が定数深さで計算可能となる。著者らは、任意の単一量子ビットゲートと一般化されたトフォリ（Toffoli）ゲートからなる量子回路（$QAC^0$）において、同様の現象が成立するかどうかを問うている。具体的には、回路サイズと補助量子ビットの数が制限されない場合、すべてのユニタリ演算を定数深さで厳密に実装できるのだろうか。

著者らは、この問いを、以下の4つの段階的に一般化されたタスクを通じて構成している：

1. 任意の集合 $L \subseteq \{0, 1\}^n$ へのメンバーシップの計算。
2. 計算基底状態の任意の置換の実装。
3. 任意の純粋量子状態の準備。
4. すべての入力状態に対する任意のユニタリ演算の実装。

手法
著者らは、可逆な古典的回路構成、量子領域に適応させた確率的古典手法、および量子テレポーテーション・プロトコルの組み合わせを用いている。

• 可逆な古典的構成: 著者らはまず、任意のビット列の置換が、トフォリゲートとファンアウト（fanout）ゲートを用いて定数深さで実装可能であることを確立する。これは「インジケーター・エンコーディング（indicator encoding）」スキームを通じて達成される。すなわち、入力を $2^n$ 次元のインジケーター・ベクトル（成分のうち一つだけが1であるもの）に写像し、操作を行い、その後、元の文字列へとデコードする。これにより、可能なすべての入力文字列の並列評価が可能となる。
• 確率的から量子への適応: 任意の確率分布および純粋量子状態を準備するために、著者らは古典的な確率的構成を応用している。これには、最初の「1」の位置に基づいて分布をエンコードするために、ビットを独立してサンプリングする手法が含まれる。量子設定においては、重ね合わせを破壊することなく、最初の「1」に続く量子ビットに逆回転を適用することで、これらをコヒーレント（干渉性を保った状態）にする。
• ゲートセットの拡張: 主要なゲートセットには単一量子ビットゲートと一般化されたトフォリゲートが含まれるが、著者らは概念的なツールとしてファンアウトゲートを利用している。著者らは、Grier, Morris, and Wu [GMW26] および Rosenthal [Ros20] の結果を引用し、ファンアウトが主要なゲートセットのみを使用して、回路サイズが二重指数的な増加を伴う可能性があるものの、定数深さで厳密に実装可能であることを示している。
• ユニタリのための簡約（Reductions）: 任意のユニタリの実装に関して、著者らは直接的な構成法は提供していない。代わりに、いくつかの等価な定式化と簡約を提示している。これらには、以下へのユニタリ実装の簡約が含まれる：
  • 指定された正規直交基底のベクトル・クローニング。
  • 基底ベクトルのリストの置換。
  • ラベルのデコード。
  • 行および列の和が1であるユニタリの実装（Idel-Wolf 標準形による）。
  • トレースレスなユニタリ・インボリューションの実装（追加のクリーンな量子ビットを1つ使用）。
• ポートベース・テレポーテーション (PBT): 特定のゲートに依存するユニタリ補正なしに、任意のユニタリの実装に近づくために、著者らはポートベース・テレポーテーションを利用する。彼らは、最大もつれ状態（または対象となるユニタリのChoi状態）と結合測定、それに続くポート選択を用いた、PBTを実行するユニタリ回路を構築する。

主な貢献と結果

1. 特定タスクに対する厳密な定数深さ構成:

   • 置換: 任意のビット列の置換は、$O(n2^n)$ のゲートと補助量子ビットを用いて、定数深さ（深さ $\le 20$）で実装可能である。
   • 対角ユニタリ: 任意の対角ユニタリは、インジケーターを計算し、並列に位相を適用し、その後アンコンピュート（uncompute）を行うことで、定数深さ（深さ 7）で実装可能である。
   • 状態準備: 任意の純粋量子状態は、$O(4^n)$ 個の量子ビットと $O(n2^n)$ 個のゲートを用いて、定数深さ（深さ $\le 37$）で準備可能である。すべての補助量子ビットはゼロに戻される。
   • ファンアウトの実装: ファンアウトは、単一量子ビットゲートと一般化されたトフォリゲートのみを使用して、定数深さで厳密に実装可能であるが、これには二重指数的なサイズが必要となる可能性がある。

2. 任意のユニタリのための簡約:
   本論文は、任意のユニタリを定数深さで実装することは、いくつかの特定の操作（例：基底ベクトルのクローニング、ラベルのデコード、またはトレースレス・インボリューションの実装）を実装することと等価であることを示している。これにより、任意のユニタリ実装という未解決の問題を、一連の等価な構造的課題へと再定義している。

3. 適応的測定とゲート・テレポーテーション:
   適応的な中間測定が許容される場合、クリフォード階層のレベル $\ell$ にある任意のゲートは、深さ $O(\ell)$ で実装可能であることを著者らは示している。さらに、適応モデルにおける任意のユニタリ実装は、トレースレス・ユニタリ・インボリューションの実装へと帰着する。

4. ポートベース・テレポーテーションの近似:
   著者らは、入力次元 $d$ および $M \ge d^2 - 1$ 個のポートに対する、ポートベース・テレポーテーション（PBT）のためのユニタリ回路を構築する。

   • 深さ: 回路の深さは $O(\sqrt{d})$ であり、これはポート数 $M$ に依存しない。
   • 忠実度: もつれ忠実度は $F_e \ge (1 - \frac{d^2-1}{2M})^2$ で抑えられる。
   • 精度と深さの関係: 固定された入力次元 $d$ に対しては、$M$ を増やすことで回路の深さを増やすことなく、近似の精度を任意に高めることができる。しかし、$d$ への依存性は依然として残る。$d$ に依存しない深さの境界を達成できるかどうかは、未解決の課題である。
   • 実装: この回路は単一量子ビットゲートと一般化されたトフォリゲートのみを使用し、中間測定を必要としない。

意義と主張
本論文は、サイズおよび補助空間の制限を取り除くことで、定数深さの量子回路が、多項式サイズの定数深さモデルでは一般に不可能なタスク（任意の状態準備や基底の置換など）を実行できることを確立している。これは、量子状態準備を、可逆な古典計算および確率分布の準備に直接結びつけるものである。

しかし、論文は「任意の」ユニタリの実装に関しては慎重な立場をとっている。著者らは、置換、対角ユニタリ、および状態準備については厳密な定数深さの構成を提供しているが、一般的なユニタリの実装については未解決のままである。著者らは、この問題に対するいくつかの等価な特徴付けを提供しているが、これを解決してはいない。

一般的なユニタリに関する主要な貢献は、PBTの構成である。著者らは、固定された入力次元に対して、ポート数を増やすことで回路の深さを増やすことなく、任意の精度で任意のユニタリを近似できることを示している。ただし、この構成の深さは入力次元 $d$ に対して $O(\sqrt{d})$ でスケールする。著者らは、この $d$ への依存性を排除できるか（すなわち、$d$ に依存しない深さの境界を達成できるか）は、依然として未解決の問いであると明示している。本研究は、定数深さのユニタリ実装における根本的な困難は、固定された入力から任意の出力を生成することではなく、ユニタリ性を保ちながら「すべての」入力状態に対して同時に作用を規定することにあるという点を浮き彫りにしている。