Vanilla Exact Synthesis of CNOT Circuits is NP-hard

Chenjian Li; Ji Guan

REVIEW

Vanilla Exact Synthesis of CNOT Circuits is NP-hard

Chenjian Li, Ji Guan

Quantum Physics · Submitted 3 Sep 2026

Pith's verdict: The result is likely correct and the reduction is clever, but the written proof of the soundness direction has a genuine gap in the budget counting that must be fixed before publication.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on September 8, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 4 major objections · 6 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2609.04160 (version 3)

Pith ID2GLZ4C5N, Pith's permanent record of this paper and its review

CitationChenjian Li, Ji Guan. "Vanilla Exact Synthesis of CNOT Circuits is NP-hard." arXiv:2609.04160 (2026). https://pith.science/paper/2GLZ4C5N

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

Here's my take on 2609.04160. The headline result—that vanilla exact CNOT synthesis is NP-complete—is already covered by the concurrent work of Acuaviva et al. [2], so the novelty is in the reduction technique and the structural strengthenings in Theorem 5. The Grid-HP reduction via unary hypercube embedding is genuinely new and interesting: it gives a direct connection between parity trajectories and Hamiltonian paths. The parameters in Theorem 5 (unitriangular, (A-I)^3 = 0, rank(A-I) = O(sqrt n), k < n + O(sqrt n)) are nice and complement [2]'s results. The writing is mostly clear and the corollaries are straightforward but useful.

That said, the soundness direction of Proposition 1 has a real exposition gap. The stress-test concern lands: Fact (1) asserts a 2m lower bound assuming each parity must be generated independently, but it does not rule out generating one parity once and then using it as a control to fan it out to m recorder qubits. The budget k = m^2 + m - 1 might still be tight under such sharing, but the counting argument as written does not establish that. The reader's reconstruction fills this with a single-targeting claim, but the manuscript itself does not supply that argument. This is a fixable gap—I suspect the result still holds—but the proof as presented is incomplete at this point.

Expositionally, the paper does a good job explaining the reduction and the role of recorder qubits. The connections to the shortest word problem and s-XOR programs are well articulated. The AI usage statement is refreshingly direct.

Who is this for? Anyone working on exact synthesis of reversible circuits or the complexity of linear transformations over F2. The paper will be cited for the reduction technique and for Theorem 5's parameters, even if the central NP-completeness result is no longer unique.

I recommend engaging with this work. The result is important, the reduction is elegant, and the gap is fixable with a more careful counting argument (or by making the single-targeting lemma explicit). This paper deserves a serious referee—it should go to peer review with the expectation that the exposition in Proposition 1 will be tightened.

Referee report

Major objections (4)

[Proposition 1, Fact (1)] The argument that if a parity χ_v(x) never appears then at least 2m CNOT gates would be needed to realize the target on the m corresponding recorder qubits is insufficiently justified. The analysis assumes that generating and later canceling a parity requires two gates per recorder qubit, but it does not rule out more efficient strategies in which the parity is generated once and then shared (e.g., broadcast using a single generated parity as a control to update multiple recorder qubits) or in which the parity is realized indirectly via sequences that exploit existing parities. Without a rigorous lower bound that eliminates such shortcuts, the claim that all m parities must appear is not proven, and the subsequent tight-budget counting collapses.
[Proposition 1, Fact (3)] The reversibility argument that a G_parity gate cannot target a recorder qubit because 'one recorder qubit would carry χ_v(x) and the m^2 recorder variables would be carried exclusively by the remaining m^2-1 recorder qubits, contradicting the reversibility requirement' is not convincing. Reversibility of the overall linear transformation does not require each individual qubit to carry a particular set of variables at intermediate steps; it only requires the overall mapping to be invertible. The presence of a parity without y-variables on a recorder qubit does not obviously break reversibility. A more rigorous justification is needed for why G_parity gates must be confined to the path qubit.
[Proposition 1, Fact (2) and subsequent counting] The derivation that |G_parity| = m-1 and that each gate in G_parity generates a new parity χ_v≠0 on the path qubit relies on the assumption that non-initial parities must be 'generated from scratch' and that each such generation corresponds to exactly one gate. However, a parity could be produced on a different qubit and later transferred to the path qubit via a sequence of gates, or a parity could be computed and then the path qubit updated using multiple gates. The tight budget may preclude such scenarios, but the reasoning does not fully account for these possibilities. A more detailed combinatorial argument is required to establish the claimed correspondence between G_parity gates and the m-1 distinct non-zero parities.
[Reduction soundness, general structure] The division of gates into G_record and G_parity based solely on 'last recorder-targeting' gates may not capture all relevant dynamics. An optimal circuit could interleave operations on recorder and non-recorder qubits in complex ways, and the claim that the last gate on each recorder qubit is the only one that matters for the final output (and that earlier recorder operations can be ignored) is not justified. The argument should consider the possibility that a recorder qubit is targeted multiple times, with intermediate operations affecting the parity structure.

Minor objections (6)

[Abstract and Section 1] The phrase 'fixed number of labelled qubits' is used but could be clarified: the reduction uses a specific labeling of qubits (path, coordinate, recorder), but the problem statement allows any labeling. This is fine, but the reader might benefit from an explicit note that the reduction constructs a specific instance, so the qubit identities are part of the instance.
[Section 3, Eq. (23)] The block matrix for A_V is given with a 1 in the top-right corner; it would be helpful to explicitly note the dimensions: the (1,3) block is a row vector of length m^2 (all zeros), the (3,1) block is a column vector of all ones? Actually the bottom-left block is X, which is m^2 x d. The text says '1_X' but the matrix shows '1' in the (3,1) position? In (20) it is '1' then X; in (23) it is '1_X'. This is a bit confusing; the notation should be consistent.
[Section 3, after Eq. (10)] The claim that the encoding is an 'isomorphism' is slightly overstrong: the induced subgraph on the encoded vertices is isomorphic to the original grid graph. The text later clarifies this, but the phrasing at line 'the encoding scheme is an isomorphism' could be misinterpreted as an isomorphism of the entire hypercube, which is false. Rephrase to 'the induced subgraph on the encoded vertices is isomorphic to G'.
[Section 3, Proposition 1 statement] Proposition 1 is stated after the proof sketch but its proof is spread across Facts (1)-(4). This is acceptable but the logical flow would be improved by a clear, numbered lemma with a self-contained proof before the final equivalence.
[Section 5, paragraph on concurrent work] The reference to Acuaviva et al. is missing a full citation; only the arXiv identifier is given. The paper should include the full bibliographic details as per journal style.
[General] There are occasional typographical issues: e.g., 'Minimization' appears as 'Minimization' in the problem description (Section 1), and 'recordor' appears once in the discussion of the recursion (Section 3, likely a typo for 'recorder'). These should be corrected.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

Vanilla exact CNOT synthesis is NP-complete

The reading

This paper resolves the long-standing open problem of whether the most basic exact CNOT synthesis problem is computationally hard. The authors prove that, even with all-to-all connectivity, no ancillas, and fixed labeled qubits, deciding whether an invertible binary matrix can be implemented by at most k CNOT gates is NP-complete. The proof reduces from the Hamiltonian path problem on grid graphs, using a clever encoding into a hypercube and introducing recorder qubits that force any short circuit to traverse a Hamiltonian path. This result closes a gap left by previous hardness results that relied on extra structure such as restricted connectivity or encoded inputs. It also implies hardness for several related problems, including the shortest word problem over GL(n,2) and optimal s-XOR programs.

What carries the argument

The central mechanism is the combination of recorder qubits and a tight budget k = $m^{2}$ + m - 1. For each vertex v of the induced hypercube, m recorder qubits must each end up containing the parity chi_v(x); this requires at least m gates per vertex, giving $m^{2}$ recorder-targeting gates in total. The remaining m-1 gates must be used on the path qubit to generate the m-1 new parities chi_v(x) for v != 0, each transition corresponding to a hypercube edge. The budget leaves no room for shortcuts: any attempt to mix parities across recorder groups or avoid generating a parity would require extra gates, enforcing that the path qubit visits the vertices in a Hamiltonian order.

Extended reading notes

Core claim

The paper establishes that the decision version of vanilla exact CNOT synthesis, MinCNOT_vanilla, is NP-complete. The reduction from the grid-graph Hamiltonian path problem (Grid-HP) proceeds in two stages: first, the grid graph is isometrically embedded into a hypercube via a unary-prefix encoding; second, the hypercube Hamiltonian path instance is encoded into a target parity matrix A_V with a tight gate budget k = $m^{2}$ + m - 1, where m is the number of vertices. Recorder qubits and the tight budget force any circuit of length at most k to realize exactly $m^{2}$ gates targeting recorder qubits (one per vertex per replica) and m-1 gates generating new parities on the path qubit, thereby extracting a Hamiltonian path from the circuit. Thus, Grid-HP reduces to MinCNOT_vanilla, proving NP-completeness.

Load-bearing premise

The soundness direction assumes that no circuit with at most k = $m^{2}$ + m - 1 gates can satisfy the target matrix A_V without having the path qubit visit each vertex's parity exactly once in a contiguous sequence corresponding to a Hamiltonian path, and without using fewer than $m^{2}$ recorder-targeting gates by reusing parities across vertext groups.

Editorial extensions

If this is right

The shortest word problem over GL(n,2) with respect to the generating set of elementary transvections is NP-complete.
Computing distances in the Cayley graph of GL(n,2) with that generating set is NP-hard.
Minimizing the number of instructions in a sequential XOR (s-XOR) program that computes an invertible linear transformation over F2 is NP-hard.
Exact synthesis of phase polynomial circuits with minimum CNOT count is NP-hard, even when the phase polynomial is trivial.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The tight-budget construction shows a close link between circuit structure and path constraints; similar recorder-based forcing might be applied to prove hardness for other synthesis problems with intermediate state requirements.
Because the reduction uses only a very restricted class of target matrices (unitriangular with (A-I)^3=0 and rank(A-I)=O(sqrt(n))), the hardness is concentrated in a narrow family of instances, suggesting that many practical synthesis instances may still be tractable on average.
The result implies that any exact CNOT optimizer that runs in polynomial time for all inputs is impossible unless P=NP, providing a theoretical justification for the exponential scaling observed in SAT-based and search-based methods.

Original abstract

Exact CNOT synthesis seeks a minimum-size circuit implementing a given invertible binary linear transformation. We study its vanilla formulation: synthesis from the identity on fixed labeled qubits, without ancillas and with all-to-all connectivity. We prove that this problem is NP-hard and that its bounded decision version is NP-complete. Hardness persists even for unitriangular targets that are low-rank perturbations of the identity and under near-linear gate budgets. Our proof gives a polynomial-time reduction from the NP-complete Hamiltonian path problem on grid graphs. A unary hypercube embedding translates graph vertices into circuit parities and edge traversals into CNOT updates. The central challenge is that Hamiltonian paths require intermediate vertex visits, whereas exact synthesis constrains only the final transformation. We bridge this gap with a replicated recorder qubits construction that encodes the required parities in the final outputs, together with a tight gate budget that forces every sufficiently short implementation to trace a Hamiltonian path. Crucially, this path structure is enforced by the construction rather than imposed as a restriction on the circuit. The result directly implies NP-hardness for shortest word problem and Cayley-graph distance computation over $\mathrm{GL}(n,2)$ with elementary transvections as generators, as well as fixed-width sequential XOR program minimization. For CNOT-minimal exact phase polynomial synthesis, it yields NP-hardness with a zero phase polynomial; extending the reduction to grid-graph Hamiltonian cycle problem establishes hardness even when the final linear transformation is the identity. These complementary results show that the linear and phase components each independently suffice for NP-hardness of exact phase polynomial synthesis.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 7,632 input tokens.

What the abstract itself states, as probabilities: claims first 0.21 · states limitation 0.27 · human participants 0.01 · controlled comparison 0.02 · randomized assignment 0.01 · states quantitative result 0.18 · compares with prior results 0.91 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

Exact CNOT synthesis asks for a minimum-size CNOT circuit implementing an invertible linear transformation. Although several related synthesis models have been shown to be computationally hard, their hardness proofs rely on additional structure such as restricted qubit connectivity, encoded inputs, or unrestricted intermediate variables. The complexity of the most basic setting---identity input, a fixed number of labelled qubits, no ancillas, and all-to-all CNOT connectivity---had remained unresolved. In this work, we prove that the decision version of this vanilla exact CNOT synthesis problem is NP-complete, and consequently that its optimization version is NP-hard. Our proof gives a polynomial-time reduction from the Hamiltonian-path problem on grid graphs in two steps. First, we isometrically embed the grid graph into a hypercube via a unary encoding map. We then encode this hypercube Hamiltonian path problem into vanilla exact CNOT synthesis. The main challenge is that CNOT synthesis specifies only the final parity matrix and cannot directly enforce the intermediate vertex visits required by a Hamiltonian path. To overcome this difficulty, we introduce extra recorder qubits that encode the required intermediate vertex visits into the final transformation, forcing any CNOT circuit implementation to realize the intended path structure. Beyond CNOT synthesis, our result directly implies hardness for several related problems, including the shortest word problem over $\mathrm{GL}(n,2)$, distance computation on Cayley graphs over $\mathrm{GL}(n,2)$, minimization of sequential XOR programs, and exact synthesis of phase polynomial circuits.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	Exact CNOT synthesis asks for a minimum-size CNOT circuit implementing an invertible linear transformation.	background 1.00	0.06	0.02	asserted 0.99
s1	Although several related synthesis models have been shown to be computationally hard, their hardness proofs rely on additional structure such as restricted qubit connectivity, encoded inputs, or unrestricted intermediate variables.	background 0.89	0.04	0.02	asserted 1.00
s2	The complexity of the most basic setting---identity input, a fixed number of labelled qubits, no ancillas, and all-to-all CNOT connectivity---had remained unresolved.	gap 1.00	0.05	0.02	asserted 0.99
s3	In this work, we prove that the decision version of this vanilla exact CNOT synthesis problem is NP-complete, and consequently that its optimization version is NP-hard.	result 0.88	0.97	0.97	asserted 1.00
s4	Our proof gives a polynomial-time reduction from the Hamiltonian-path problem on grid graphs in two steps.	method 0.91	0.95	0.06	asserted 1.00
s5	First, we isometrically embed the grid graph into a hypercube via a unary encoding map.	method 0.99	0.93	0.02	asserted 1.00
s6	We then encode this hypercube Hamiltonian path problem into vanilla exact CNOT synthesis.	method 0.98	0.94	0.03	asserted 1.00
s7	The main challenge is that CNOT synthesis specifies only the final parity matrix and cannot directly enforce the intermediate vertex visits required by a Hamiltonian path.	method 0.66	0.42	0.02	asserted 1.00
s8	To overcome this difficulty, we introduce extra recorder qubits that encode the required intermediate vertex visits into the final transformation, forcing any CNOT circuit implementation to realize the intended path structure.	method 0.95	0.95	0.03	asserted 1.00
s9	Beyond CNOT synthesis, our result directly implies hardness for several related problems, including the shortest word problem over $\mathrm{GL}(n,2)$, distance computation on Cayley graphs over $\mathrm{GL}(n,2)$, minimization of sequential XOR programs, and exact synthesis of phase polynomial circuits.	interpretation 0.87	0.89	0.06	asserted 1.00

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures

**Figure 1.** Illustration of a grid graph 𝐺 over the 2D grid, together with an illustrative Hamiltonian path. Hypercubes. The 𝑑-dimensional hypercube graph 𝑄𝑑 , or 𝑑-dimensional hypercube for short, is a graph with vertex set F 𝑑 2 . We also denote |𝒖 − 𝒗| for the Manhattan distance between 𝑑-dimensional vectors, which happens to be the Hamming distance between hypercube vertices 𝒖 and 𝒗. Thus two cube vertices are adjacent (and connected) when |𝒖 − 𝒗| = 1. Furthermore, for 𝑉 ⊆ F 𝑑 2 , let 𝑄𝑑 [𝑉 ] denote the subgraph induced by 𝑉 . Definition 3 (Induced hypercube subgraphs). For a vertex set 𝑉

**Figure 2.** Demonstration of the reduction from hypercube Hamiltonian path to

**Figure 3.** The Cayley graph 𝐶𝐺 for 𝐺 = GL(2, 2) generated by 𝑆 = {𝑇1,2,𝑇2,1 }. 𝐶GL(𝑛,2) corresponds to the exact CNOT synthesis of 𝐴1𝐴 −1 2 . The complexity of exact CNOT synthesis therefore directly translates to the complexity of computing distances in 𝐶𝐺 . Corollary 3. Let 𝐺 = GL(𝑛, 2) and let 𝑆 = T𝑛 be the set of elementary transvections. Given 𝐴, 𝐵 ∈ 𝐺 and 𝑘 ∈ N, deciding whether 𝛿𝑆 (𝐴, 𝐵) ≤ 𝑘 (43) is NP-complete. Consequently, computing the exact distance 𝛿𝑆 (𝐴, 𝐵) in 𝐶𝐺 is NP-hard. 4.3 Sequential XOR Programs Another implication of our result concerns XOR-program optimization in linear

Figures reproduced from arXiv:2609.04160 by the authors.

References

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Complexity separations for optimal matchgate-Clifford synthesis
quant-ph 2026-10 conditional novelty 7.0 of 10

Optimal matchgate-Clifford circuit synthesis is solvable in O(n²) time on path and complete connectivity graphs but becomes NP-complete on arbitrary tree connectivity.
(A Variant of) Clifford Circuit Synthesis is NP-Complete
quant-ph 2026-10 accept novelty 6.0 of 10

Optimal depth synthesis of Clifford circuits over a gate set that includes CZ is NP-hard, matching the known NP upper bound and making the decision problem NP-complete.

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.