Vanilla Exact Synthesis of CNOT Circuits is NP-hard

1 Introduction

• Prior hardness results relied on restricted connectivity, encoded inputs, or extra intermediate XOR variables, leaving the vanilla model's complexity unresolved.The paper defines the vanilla formulation as fixed-width synthesis from the identity, without ancillas and with all-to-all connectivity.Source: §1 · p. 2
• Vanilla exact CNOT synthesis is NP-hard, and its bounded decision version is NP-complete via a polynomial-time reduction from Grid-HP.The result concerns synthesis from the identity with no ancillas and all-to-all connectivity.Source: §1 · p. 2
• Recorder qubits encode intermediate hypercube parities in final outputs, while a tight gate budget forces sufficiently short circuits to yield a Hamiltonian path.The reduction embeds the grid graph in a hypercube, with vertices represented by circuit parities and edges by CNOT updates.Source: §1 · p. 3
• The result also yields hardness for shortest word and Cayley-graph distance problems over GL(n,2), and for fixed-width sequential XOR program minimization.These implications extend the result to group theory and linear cryptography.Source: §1 · p. 3
• Exact phase polynomial synthesis is NP-hard when either the target linear transformation or the phase polynomial is trivial, so either component alone suffices for hardness.The paper also adapts the reduction to establish hardness when the final linear transformation is the identity.Source: §1 · p. 3
• The paper presents an independent Grid-HP-based proof complementary to concurrent work that established NP-completeness for the same setting via VertexCover.Its reduction links CNOT parity trajectories with Hamiltonian paths in induced hypercube subgraphs.Source: §1 · p. 3

2.1 CNOT circuits and exact synthesis

• CNOT gates implement reversible linear operations over F2, and a circuit's action on n input variables is represented by an n×n parity matrix in GL(n,2).A CNOT adds the control bit to the target bit modulo 2.Source: §2.1 · p. 4
• Exact CNOT synthesis seeks a smallest circuit for a target linear transformation, while the vanilla decision problem asks whether one exists within a gate bound k.The vanilla instance specifies n, a target parity matrix A in GL(n,2), and a nonnegative integer k, with all-to-all CNOT availability.Source: §2.1 · p. 5

2.2 Grid graphs and induced hypercube graphs

• A grid graph has vertices on the two-dimensional integer grid and edges between vertices at Manhattan distance one.Grid-HP asks whether there is a Hamiltonian path between specified distinct vertices; Grid-HC asks whether the graph has a Hamiltonian cycle.Source: §2.2 · p. 5
• A d-dimensional hypercube joins vertices at Hamming distance one, and its induced subgraph on a vertex set retains the edges between those vertices.The background notes that grid-graph Hamiltonian path and cycle problems are NP-complete.Source: §2.2 · pp. 5–6

• MinCNOTvanilla is NP-complete: a polynomial-time reduction from Grid-HP establishes hardness, and polynomially verifiable CNOT witnesses establish membership in NP.Source: §3 · pp. 6–7
• The construction replicates recorder qubits and imposes a tight gate budget, leaving no room for auxiliary computation; every sufficiently short circuit meeting the requirement visits all required vertex parities, inducing a Hamiltonian path.The budget assigns m−1 gates to Hamiltonian-path steps and m^2 gates to recording.Source: §3 · pp. 7, 10
• A unary encoding embeds the grid graph isometrically into a hypercube, preserving edges and the specified Hamiltonian-path endpoints.Thus the original grid instance has a Hamiltonian path exactly when the induced hypercube subgraph has one.Source: §3 · pp. 7–8
• Each hypercube vertex maps to a circuit parity, and a CNOT using the differing coordinate qubit updates the path qubit to the neighboring vertex’s parity.Source: §3 · p. 9

3 The Main Hardness Result

• The tight budget forces all m parities to appear, with exactly m−1 parity-generating gates targeting the path qubit and m² gates targeting recorder qubits.Each parity gate generates a new non-initial parity; the gate sets leave no surplus parity gates.Source: §3 · pp. 11–12
• The path-qubit parities correspond to adjacent hypercube vertices, so their sequence yields a Hamiltonian path.The sequence starts at 0 and continues through the vertices associated with the generated parities.Source: §3 · p. 12

3.1 Further strengthening of the hardness theorem

• The problem remains intractable for lower-unitriangular target transformations; the same reasoning applies to upper-unitriangular targets, and restricting instances to (A−I)^3 = 0 also suffices for intractability.Source: §3.1 · p. 13
• The reduction retains rank(A−I)=O(√n) and a gate budget k<n+O(√n), placing hardness in the near-linear gate-count regime.The target is a low-rank perturbation of the identity.Source: §3.1 · p. 13

4 Discussion and Complexity Implications

• The simplicity of vanilla MinCNOT extends its complexity implications beyond CNOT synthesis to algebraic, graph-theoretic, cryptographic, and quantum-circuit problems.The section develops implications for shortest words, Cayley-graph distance, sequential XOR programs, and phase-polynomial synthesis.Source: §4 · p. 14

4.1 Shortest Word Problem

• The shortest-word decision problem over GL(n,2) with elementary transvections is NP-complete, because CNOT circuits correspond to words in those generators.Source: §4.1 · p. 14

4.2 Cayley Graph Distance

• Computing Cayley-graph distance under elementary transvections is NP-hard, with group elements as vertices and CNOT gates as edges.Source: §4.2 · p. 15

4.3 Sequential XOR Programs

• Hardness transfers to minimizing fixed-width, in-place s-XOR programs because each such instruction corresponds exactly to a CNOT gate.This addresses the restrictive sequential model, where instructions overwrite existing variables and introduce no additional intermediates.Source: §4.3 · p. 16

4.4 Exact Phase Polynomial Synthesis

• General exact phase-polynomial synthesis is NP-hard even when the phase polynomial is trivial, f(x) = 0.The result removes the fixed-target restriction and places the hardness in the target linear transformation.Source: §4.4 · p. 17
• Exact phase-polynomial synthesis is NP-hard even with an identity target, by reduction from Hamiltonian cycle on grid graphs.The bounded decision problem is also NP-hard, so minimum-CNOT exact synthesis is NP-hard under the same identity-target condition.Source: §4.4 · pp. 18, 20
• The reduction uses only path and coordinate qubits, with specified phase checkpoints making recorder qubits unnecessary.This adapts the main reduction strategy by adjusting the phase polynomial to impose the parity checkpoints.Source: §4.4 · p. 18
• A tight CNOT budget forces every qualifying circuit—not just one stipulated to be fixed-target—to direct all gates to a single path qubit, whose parity sequence yields a Hamiltonian cycle.The proof does not assume a path/coordinate-qubit distinction; the gate budget forces the structure and the cycle extracted from it visits every encoded vertex exactly once.Source: §4.4 · pp. 19–20
• Together with Corollary 5’s f=0 construction, this shows that either the phase-polynomial constraint or the target-matrix constraint alone suffices for hardness.The identity-target result places the hardness in the phase checkpoints, while Corollary 5 places it in the final matrix.Source: §4.4 · p. 20
• Unlike Amy et al. [3], whose proof imposed a fixed-target circuit condition, this reduction derives that structure from its carefully chosen gate count.The result therefore establishes hardness without the fixed-target assumption on circuits.Source: §4.4 · p. 20

• Earlier results establish NP-hardness for general XOR straight-line program minimization and for Clifford+T gate-count or depth minimization [29].The Clifford+T result also covers Toffoli-count minimization in classical reversible circuits.Source: §5 · p. 20
• Exact CNOT synthesis has been encoded as SAT, classical planning, and QBF; the SAT-based method was most effective overall [28], and Qiskit-SAT also uses SAT with Z3.Source: §5 · p. 20
• The Section 4.4 hardness result provides a complexity-theoretic foundation for exact methods even without topology constraints or a nontrivial phase polynomial.Source: §5 · p. 21
• Concurrent work by Acuaviva et al. [2] independently proves NP-completeness for all-to-all, fixed-label CNOT distance via VertexCover, while this paper uses a distinct Grid-HP reduction.Source: §5 · p. 21
• The reductions expose different challenges: Acuaviva et al. [2] extract parity selection and sharing, whereas this proof forces an ordering of intermediate parities through recorder qubits and a rank argument.The construction forces a single trajectory through the required hypercube.Source: §5 · p. 21

6 Conclusion

• Deciding whether an invertible parity matrix can be implemented with at most k CNOT gates is NP-complete, even with all-to-all connectivity, no ancillas, fixed labeled qubits, and identity input.The reduction establishes hardness for the vanilla, unrestricted in-place problem.Source: §6 · p. 21
• The Grid-HP reduction uses an induced hypercube representation, where hypercube moves correspond to CNOT parity updates.The challenge is that Hamiltonian paths constrain intermediate states, while CNOT synthesis constrains only the final parity matrix; recorder qubits, replication, and a tight gate budget force sufficiently short circuits to expose the path.Source: §6 · p. 21
• The result transfers to NP-completeness of shortest-word and Cayley-graph distance problems over GL(n,2), and to NP-hardness of fixed-width s-XOR programs and exact phase-polynomial synthesis.The transfer follows from the vanilla problem's simple algebraic formulation.Source: §6 · p. 21
• For exact phase-polynomial synthesis, either the target linear-transformation constraint or the phase-polynomial constraint alone suffices for NP-hardness.The paper identifies these as complementary, independently sufficient sources of hardness.Source: §6 · p. 21

AI Tool Usage Statement

• The authors report using GPT-5.6 in developing the work.The disclosure names GPT-5.6 as the tool used.Source: AI Tool Usage Statement · p. 21
• The authors state that they reviewed and validated the mathematical proofs, analysis, citations, and final text.They take full responsibility for the final work.Source: AI Tool Usage Statement · p. 21
• The manuscript is marked as submitted to ACM.Source: AI Tool Usage Statement · p. 21