CNOT-Distance is NP-complete under all-to-all connectivity

技術要約：全結合アーキテクチャにおけるCNOT距離のNP完全性

問題定義
本論文は、**CNOT距離（CNOT-Distance）問題の計算複雑性を扱う。明示的に表現された可逆なバイナリ行列 $A \in GL(N, 2)$ と整数 $K$ が与えられたとき、固定されたラベル付きの $N$ 本のワイヤを用いた全結合（all-to-all connectivity）**環境において、$A$ が最大 $K$ 個のCNOTゲートによる回路で実装可能であるかどうかを問うものである。このモデルでは、補助ワイヤ（ancillary wires）は存在しないものとし（ただし、補助的なバリアントについても検討される）、ゲートの順序指定やキャンセルフリーの制約も設けない。目的は、ケイリーグラフ（$GL(N, 2)$において転置行列によって生成されるもの）におけるワード長、すなわち、特定のインスタンスに対して$A$ を合成するために必要な最小ゲート数を決定することである。

ガウス消去法は $O(N^2)$ の上界を提供するものであり、最悪の場合の境界に関する改良されたアルゴリズムも存在するが、特定のインスタンスに対して正確な最小ゲート数を求める計算の複雑性は未解決のままである。これまでの困難性の結果は、制限されたトポロジー、特定の入力エンコーディングを持つパリティネットワーク、あるいはClifford+Tを含むゲートセットに焦点を当てたものであった。固定ラベル、全結合CNOT合成の具体的な困難性は、未解決の問いであった。

手法
著者らは、有限単純グラフ上の**最小頂点被覆（Minimum Vertex Cover）**問題からの帰着を通じて、NP完全性を証明している。

1. ターゲット行列の構成:
   与えられたグラフ $G = (V, E)$ に対して、著者らは特定の、上三角単位行列である $A_G \in GL(2|V| + |E| + 1, 2)$ を構成する。この行列は、識別可能なワイヤ $z$、各頂点 $v \in V$ に対するワイヤのペア $(q_v, x_v)$、および各エッジ $e \in E$ に対するワイヤ $y_e$ を含むワイヤ集合に作用する。変換は以下のように定義される：

   • $q'_v = q_v + z$
   • $x'_v = x_v + q_v$
   • $y'_e = y_e + z + x_u + x_v$ （エッジ $e=\{u,v\}$ について）

2. 正確な距離の恒等式:
   証明の核心は、以下の正確な恒等式を確立することにある：
   $$\ell_{\text{CNOT}}(A_G) = 2|V| + 2|E| + \tau(G)$$
   ここで、$\tau(G)$ はグラフ $G$ の最小頂点被覆のサイズである。

3. 上界の構成:
   著者らは、任意の頂点被覆 $C$ が長さ $2|V| + 2|E| + |C|$ のCNOT回路をもたらすことを示す。この構成において、選択された頂点ワイヤは、隣接するエッジの出力に対して $z$ の寄与を一時的に運ぶことで、要求されるパリティを実質的に実装する。

4. 射影・縮退による下界:
   下界の導出が、本研究の新規な貢献である。著者らは、$A_G$ を実装する任意の（キャンセルや中間再利用を含む）CNOT回路が、XOR有向非巡回グラフ（DAG）へと「展開」できることを示す。射影（projection）（特定の入力をゼロに設定する）と縮退（contraction）（同一の射影値を持つノードをマージする）を適用することで、回路の「可逆的な簿記（reversible bookkeeping）」コンポーネoutent を系統的に除去する。

   • 頂点入力を射影することで、$2|V|$ 個のノードが削除される。
   • プライベートなエッジ入力を射解することで、$|E|$ 個のノードが削除される。
   • 残った構造は、形式の集合 $F_G = \{z + x_u + x_v \mid \{u,v\} \in E\}$ を計算するXOR直線プログラムとなる。
   • Boyar-Matthews-Peraltaの補題のバイナリ特殊化を用いることで、この残ったプログラムの長さは少なくとも $|E| + \tau(G)$ であることが示される。
   • これらを組み合わせることで、下界 $L \ge 2|V| + 2|E| + \tau(G)$ が得られる。

5. 補助ワイヤに対する頑健性:
   著者らは、任意の有限数の**クリーン（clean）または借用（borrowed）**補助ワイヤを追加しても、これらの一連の行列における最適ゲート数が減少しないことを証明している。射影・縮退の議論は、補助変数を射影すべき追加の入力として扱うことで、これらのケースにも拡張される。

主な貢献と結果

• NP完全性: CNOT距離問題はNP完全であることが証明された。これは、以下の非常に制限されたインスタンスにおいても成立する：
  • $A$ が上三角単位行列である。
  • すべての行のハミング重みが最大4である。
  • $A$ の正確な位数が4である（すなわち、$(A-I)^3=0$ かつ $A^4=I$）。
  • ゲート予算 $K < 2N$ である。
• 正確な計算の困難性: 正確なCNOT距離 $\ell_{\text{CNOT}}(A)$ を計算することはNP困難である。
• 近似の困難性:
  • 加法的（Additive）: 距離を任意の固定された加法的定数 $c$ 以内で近似することはNP困難である。
  • 乗法的（Multiplicative）: 最適化問題はAPX困難である（3次グラフ上の最小頂点被覆からのL-還元による）。これは、P=NPでない限り、多項式時間近似スキーム（PTAS）が存在しないことを意味する。
• 補助ワイヤの不変性: 構成された $A_G$ の一族に対して、最小ゲート数は、補助ワイヤなし、クリーン補助ワイヤ、および借用補助ワイヤのモデル間で同一である。
• 構成的デコーダ: この還元には多項式時間のデコーダが含まれており、任意の $A_G$ に対するCNOT回路が与えられたとき、回路の長さから定数分を差し引いたサイズを持つ $G$ の頂点被覆を抽出できる。これは、APX困難性を確立するためのL-還別のための極めて重要である。

意義と主張
本論文は、アーキテクチャの制約（ルーティング、利用可能なゲート）が取り除かれた場合でも、最小サイズのCNOT合成が計算量的に困難であり続けるという基本的な問いを解決した。著者らは、困難性は、特定のデバイスの幾何学的な構造からではなく、線形可逆実装自体の最小化から生じていると主張している。

結果は、以下のことを明らかにしている：

• 問題は、疎で構造化された行列（低ハミング重数の上三角単位行列）であっても依然として困難である。
• 困難性は、補助ワイヤ（クリーンまたは借用）の使用に関わらず持続する（ただし、それらは復元されなければならない）。
• 射影・縮程法は、任意の可逆的な実装から非可逆なカーネル（XOR複雑性など）を抽出するための一般的な手法を提供しており、キャンセルや中間再利用が根本的な組合せ論的困難性を回避できないことを示唆している。

著者らは、この結果が、還元による一様性プロパティを通じて、完全二部グラフを埋め込むことができるあらゆるアーキテクチャ・ファミリーに対してNP困難性を意味することを述べているが、特定の固定された疎なトポロジー（パスやスターなど）に対する複雑性は決定していない。なぜなら、生成集合を制限すると距離指標自体が変化するためである。