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
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.
CNOT gates are fundamental to quantum computing, as they facilitate entanglement, a crucial resource for quantum algorithms. Certain classes of quantum circuits are constructed exclusively from CNOT gates. Given their widespread use, it is imperative to minimise the number of CNOT gates employed. This problem, known as CNOT minimization, remains an open challenge, with its computational complexity yet to be fully characterized. In this work, we introduce a novel reinforcement learning approach to address this task. Instead of training multiple reinforcement learning agents for different circuit sizes, we use a single agent up to a fixed size
m. Matrices of sizes different from
mare preprocessed using either embedding or Gaussian striping. To assess the efficacy of our approach we trained an agent with
m=8, and evaluated it on matrices of size
nthat ranges from 3 to 15. The results we obtained show that our method overperforms the state of the art algorithm as the value of
nincreases.
Abstract Photonic graph states are important for measurement- and fusion-based quantum computing, quantum networks, and sensing. They can in principle be generated deterministically by using emitters to create the requisite entanglement. Finding ways to minimize the number of entangling gates between emitters and understanding the overall optimization complexity of such protocols is crucial for practical implementations. Here, we address these issues using graph theory concepts. We develop optimizers that minimize the number of entangling gates, reducing them by up to 75% compared to naive schemes for moderately sized random graphs. While the complexity of optimizing emitter-emitter CNOT counts is likely NP-hard, we are able to develop heuristics based on strong connections between graph transformations and the optimization of stabilizer circuits. These patterns allow us to process large graphs and still achieve a reduction of up to 66% in emitter CNOTs, without relying on subtle metrics such as edge density. We find the optimal emission orderings and circuits to prepare unencoded and encoded repeater graph states of any size, achieving global minimization of emitter and CNOT resources despite the average NP-hardness of both optimization problems. We further study the locally equivalent orbit of graphs. Although enumerating orbits is #P complete for arbitrary graphs, we analytically calculate the size of the orbit of repeater graphs and find a procedure to generate the orbit for any repeater size. Finally, we inspect the entangling gate cost of preparing any graph from a given orbit and show that we can achieve the same optimal CNOT count across the orbit.