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

Technical Summary: CNOT-Distance is NP-complete under all-to-all connectivity

Problem Statement
The paper addresses the computational complexity of the CNOT-Distance problem. Given an explicitly represented invertible binary matrix $A \in GL(N, 2)$ and an integer $K$, the problem asks whether $A$ can be implemented by a circuit of at most $K$ CNOT gates on $N$ fixed, labelled wires with all-to-all connectivity. The model assumes no ancillary wires (though ancillary variants are considered), no cancellation-free constraints, and no prescribed gate ordering. The goal is to determine the minimum gate count (word length in the Cayley graph of $GL(N, 2)$ generated by transvections) required to synthesize $A$.

While Gaussian elimination provides an $O(N^2)$ upper bound and improved algorithms exist for worst-case bounds, the complexity of finding the exact minimum gate count for a specific instance remains unresolved. Previous hardness results have focused on restricted topologies, parity networks with specific input encodings, or gate sets including Clifford+T. The specific hardness of fixed-label, all-to-all CNOT synthesis was an open question.

Methodology
The authors prove NP-completeness via a reduction from the Minimum Vertex Cover problem on finite simple graphs.

1. Construction of Target Matrices:
   For a given graph $G = (V, E)$, the authors construct a specific upper-unitriangular matrix $A_G \in GL(2|V| + |E| + 1, 2)$. The matrix acts on a set of wires including a distinguished wire $z$, pairs of wires $(q_v, x_v)$ for each vertex $v \in V$, and a wire $y_e$ for each edge $e \in E$. The transformation is defined such that:

   • $q'_v = q_v + z$
   • $x'_v = x_v + q_v$
   • $y'_e = y_e + z + x_u + x_v$ (for edge $e=\{u,v\}$)

2. Exact Distance Identity:
   The core of the proof establishes the exact identity:
   $$\ell_{\text{CNOT}}(A_G) = 2|V| + 2|E| + \tau(G)$$
   where $\tau(G)$ is the size of the minimum vertex cover of $G$.

3. Upper Bound Construction:
   The authors demonstrate that any vertex cover $C$ yields a CNOT circuit of length $2|V| + 2|E| + |C|$. In this construction, selected vertex wires temporarily carry the contribution of $z$ to incident edge outputs, effectively implementing the required parities.

4. Lower Bound via Projection-Contraction:
   The lower bound is the novel contribution. The authors show that any arbitrary CNOT circuit implementing $A_G$ (even with cancellations and intermediate reuse) can be "unfolded" into an XOR directed acyclic graph (DAG). By applying projection (setting specific inputs to zero) and contraction (merging nodes with identical projected values), they systematically remove the "reversible bookkeeping" components of the circuit.

   • Projecting vertex inputs forces the deletion of $2|V|$ nodes.
   • Projecting private edge inputs forces the deletion of $|E|$ nodes.
   • The remaining structure is an XOR straight-line program computing the set of forms $F_G = \{z + x_u + x_v \mid \{u,v\} \in E\}$.
   • Using a binary specialization of the Boyar-Matthews-Peralta lemma, the length of this remaining program is shown to be at least $|E| + \tau(G)$.
   • Combining these yields the lower bound $L \ge 2|V| + 2|E| + \tau(G)$.

5. Ancillary Robustness:
   The authors prove that the addition of any finite number of clean or borrowed ancillary wires does not reduce the optimal gate count for this family of matrices. The projection-contraction argument extends to these cases by treating ancillary variables as additional inputs to be projected.

Key Contributions and Results

• NP-Completeness: The CNOT-Distance problem is proven to be NP-complete. This holds even for highly restricted instances where:
  • $A$ is upper-unitriangular.
  • Every row has Hamming weight at most 4.
  • $A$ has exact order 4 (i.e., $(A-I)^3=0$ and $A^4=I$).
  • The gate budget $K < 2N$.
• Hardness of Exact Computation: Computing the exact CNOT distance $\ell_{\text{CNOT}}(A)$ is NP-hard.
• Hardness of Approximation:
  • Additive: It is NP-hard to approximate the distance within any fixed additive constant $c$.
  • Multiplicative: The optimization problem is APX-hard (via an L-reduction from Minimum Vertex Cover on cubic graphs), implying no Polynomial-Time Approximation Scheme (PTAS) exists unless P=NP.
• Ancillary Invariance: For the constructed family $A_G$, the minimum gate count is identical for ancilla-free, clean-ancilla, and borrowed-ancilla models.
• Constructive Decoder: The reduction includes a polynomial-time decoder that, given any CNOT circuit for $A_G$, extracts a vertex cover for $G$ whose size is bounded by the circuit length minus a constant factor. This is crucial for establishing the L-reduction for APX-hardness.

Significance and Claims
The paper resolves the basic question of whether minimum-size CNOT synthesis remains computationally hard when architectural constraints (routing, gate availability) are removed. The authors claim that the hardness arises intrinsically from the minimization of the linear-reversible implementation itself, not from the geometry of a specific device.

The results clarify the boundary between tractable and intractable synthesis:

• The problem remains hard even for sparse, structured matrices (upper-unitriangular with low Hamming weight).
• The hardness persists regardless of the use of ancillary wires (clean or borrowed), provided they must be restored.
• The projection-contraction technique provides a general method for extracting non-reversible kernels (like XOR complexity) from arbitrary reversible implementations, suggesting that cancellations and intermediate reuse do not circumvent the fundamental combinatorial difficulty of the problem.

The authors note that while the result implies NP-hardness for any architecture family that can embed a complete bidirected graph (via the reduction's uniformity property), it does not determine the complexity for specific fixed sparse topologies (e.g., paths or stars), as restricting the generating set changes the distance metric entirely.