Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2606.18201 · Leibniz international proceedings in informatics

On the Complexity of the Circuit Width Problem

Zhengfeng Ji, Yinchen Liu, Zhe'ou Zhou

Published Jan 1, 2026• 0 citations
arXivHTMLPDF

Abstract

Montanaro associated to every quantum circuit over the gate set {H,Z,CZ,CCZ} a degree-three polynomial over 𝔽₂, and showed that the strong simulation cost of the circuit is governed by the minimum number of qubit wires needed to realize that polynomial. We study this minimum-width problem. We prove that deciding whether a degree-three polynomial has width at most k is NP-complete. The reduction is parsimonious enough to imply that, for every α < 49/48, the corresponding gap version is NP-hard. We also prove the same inapproximability threshold for degree-two polynomials by a twin-copy replacement of the cubic constraints. On the positive side, we give a nondeterministic search algorithm using only O(klog(en/k)) nondeterministic bits, and a deterministic fixed-parameter algorithm running in k^{6k+o(k)}n+O(m) time on an input with n symbols and m monomials.

DOI
10.4230/lipics.tqc.2026.7

Related papers

(A Variant of) Clifford Circuit Synthesis is NP-Complete

Luna Lima Keller, Richard Kueng

Optimal circuit synthesis is the problem of finding the shortest-depth circuit representation of a given functionality with respect to a pre-specified elementary gate set. This is a central problem in both quantum and classical hardware design. While the classical version is very well understood -- both in terms of heuristics and rigorous hardness assertions -- much less is known about optimal quantum circuit synthesis. We focus on optimal Clifford circuit synthesis, for which various heuristics are known, e.g. via reduction to 3-SAT. Our main result supplies a matching hardness result: a variant of optimal Clifford synthesis is NP-hard. The proof proceeds in two parts: (i) reduce 3-edge colorability on 3-regular graphs to a circuit synthesis problem that only involves CZ gates, (ii) prove that the availability of additional elementary Clifford gates -- most notably: Hadamard, phase and CNOT -- cannot lead to further improvements of the optimal circuit depth. Our work sharpens the complexity-theoretic understanding of Clifford circuits: simulation and equivalence checking are in P, whereas deciding whether a Clifford unitary admits an implementation within a prescribed depth is NP-complete.

quant-pharXiv:2610.02029•Oct 2, 2026•0 citations

Circuit Design Problems in Binary Polynomial Quantum Optimization

Dylan Laplace Mermoud, Dimitri Watel, Sourour Elloumi +1 more

Solving combinatorial optimization problems on near-term quantum computers mainly relies on their quadratic unconstrained binary formulation. Lately, binary polynomial formulations start to take the center stage, having a better scaling with respect to the number of used qubits. However, while quadratic forms are straightforward to implement on quantum circuits, polynomial forms of degree $d$ incur in circuit depth overheads, due to the lack of $d$-qubit gates, for $d\geq 3$, on current hardware. In this paper, we study the problem of designing the shallowest quantum circuit for a given polynomial form. We formulate it as a classical binary linear problem and we prove the \textsf{NP}-completeness of a variant of it. On the algorithmic side, we offer a scalable and performant heuristic method to tackle it, Tempura, as well as faster binary linear problem formulations, which offer computational feasibility while sacrificing optimality. Our performance evaluation shows that the algorithms yield far shorter circuits than the state-of-the-art approaches, and Tempura is mostly comparable with them in terms of runtime.

quant-pharXiv:2610.13283•Oct 12, 2026•0 citations

Circuit Design Problems in Binary Polynomial Quantum Optimization

Dylan Laplace Mermoud, Dimitri Watel, Sourour Elloumi +1 more

Solving combinatorial optimization problems on near-term quantum computers mainly relies on their quadratic unconstrained binary formulation. Lately, binary polynomial formulations start to take the center stage, having a better scaling with respect to the number of used qubits. However, while quadratic forms are straightforward to implement on quantum circuits, polynomial forms of degree d incur in circuit depth overheads, due to the lack of d-qubit gates, for d≥3, on current hardware. In this paper, we study the problem of designing the shallowest quantum circuit for a given polynomial form. We formulate it as a classical binary linear problem and we prove the NP-completeness of a variant of it. On the algorithmic side, we offer a scalable and performant heuristic method to tackle it, Tempura, as well as faster binary linear problem formulations, which offer computational feasibility while sacrificing optimality. Our performance evaluation shows that the algorithms yield far shorter circuits than the state-of-the-art approaches, and Tempura is mostly comparable with them in terms of runtime

•Oct 13, 2026•0 citations

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

Antonio Acuaviva, Arturo Acuaviva, Pablo Acuaviva

Given $A\in\operatorname{GL}(N,2)$ and an integer $K$, we ask whether $A$ can be implemented by at most $K$ CNOT gates on fixed labelled wires with all-to-all connectivity. We prove that this problem is NP-complete. From a finite simple graph $G=(V,E)$, we construct an upper-unitriangular matrix $A_G\in\operatorname{GL}(2|V|+|E|+1,2)$ satisfying $\ell_{\mathrm{CNOT}}(A_G)=2|V|+2|E|+τ(G)$, where $τ(G)$ is the minimum vertex-cover size. Each target matrix has $O(N)$ nonzero entries and row Hamming weight at most four. The lower bound unfolds an arbitrary CNOT circuit into an XOR directed acyclic graph and applies projection--contraction operations, allowing cancellation and unrestricted reuse of intermediate parities. For this family, the optimum is unchanged by any finite number of clean or borrowed ancillary wires that must be restored. A polynomial-time decoder further yields NP-hardness of approximation within every fixed additive constant and, through an L-reduction from Minimum Vertex Cover on cubic graphs, APX-hardness of the associated CNOT-circuit optimisation problem.

quant-pharXiv:2608.03825•Aug 5, 2026•0 citations

Ancilla-Free Parity Network Synthesis is NP-complete

Long Do Duc, An Duc

A parity network is a CNOT circuit in which every parity from a prescribed set S appears on some wire; such networks are the CNOT skeletons of phase-polynomial circuits. Amy, Azimzadeh and Mosca (Quantum Science and Technology, 2018) left open the ancilla-free problem with arbitrary output. We prove that deciding whether S admits such a network with at most K CNOTs is NP-complete, even if every CNOT must produce a new parity, all parities share a variable and have weight at most five, and connectivity is a star. Hence CNOT minimization of phase polynomials is NP-hard even with a free linear part. The reduction is from Hamiltonian cycle in grid graphs: networks meeting the trivial lower bound are path covers with at most one path per wire, and chaining many copies of the instance makes a missing Hamiltonian path cost more paths than there are wires. We also show that unrestricted networks can be shorter than fixed-target ones by a factor linear in the number of qubits. This is a preprint; it has not been peer reviewed.

•Oct 4, 2026•0 citations

Heuristic Time Complexity of NISQ Shortest-Vector-Problem Solvers

Miloš Prokop, Petros Wallden

Finding the shortest non-zero vector on a lattice is a fundamental problem in lattices that is believed to be hard both for classical and quantum computers. Two of the three standardised by NIST post-quantum cryptosystems rely on its hardness. Research on theoretical and practical performance of quantum algorithms to solve the Shortest Vector Problem (SVP) is crucial to establish confidence in those new standards. Exploring the capabilities that Variational Quantum Algorithms (VQA) that can run on Noisy Intermediate Scale Quantum (NISQ) devices have in solving SVP has been an active area of research. The qubit-requirement for doing so has been analysed and demonstrated that it is plausible to encode SVP on the ground state of a Hamiltonian in an efficient way. Due to the heuristic nature of VQAs no analysis of the performance and specifically of the time complexity of those approaches for scales beyond the non-interesting classically simulatable sizes has been performed. In this paper, motivated by Boulebnane and Montanaro [1] work on the k-SAT problem, we propose to use angle pretraining of the Quantum Approximate Optimisation Algorithm (QAOA) for SVP and we demonstrate that QAOA with fixed angles performs well on much larger instances than those used in training. Avoiding the limitations that arise due to the use of optimiser, we are able to extrapolate the observed performance and we observe the probability of success scaling as$2^{-0.695n}$with$n$being dimensionality of the search space for a depth$p=3$pre-trained QAOA algorithm. By repeating the algorithm, we get heuristic time complexity$O(2^{0.695n})$to solve the problem with high probability, a bit worse than the fault-tolerant Grover approach of$O(2^{0.5n})$. On the other hand, both the number of qubits, and most importantly the depth of each quantum computation, are considerably better in our approach – Grover requires exponential depth, while each run of constant$p$fixed-angles QAOA requires polynomial depth. Further, we analyse the performance of QAOA in solving approximate-SVP, a version of the problem that one seeks a multiplicative approximation to the shortest vector. As a side result, we propose a novel method to avoid the zero vector solution to SVP without introducing more logical qubits. This improves upon the previous works as it results in more space efficient encoding of SVP on NISQ architectures without ignoring the zero vector problem.

arXiv:2502.05284•IEEE Transactions on Quantum Engineering•Jan 1, 2025•2 citations
Montanaro associated to every quantum circuit over the gate set {H,Z,CZ,CCZ} a degree-three polynomial over 𝔽₂, and showed that the strong simulation cost of the circuit is governed by the minimum number of qubit wires needed to realize that polynomial. We study this minimum-width problem. We prove that deciding whether a degree-three polynomial has width at most k is NP-complete. The reduction is parsimonious enough to imply that, for every α < 49/48, the corresponding gap version is NP-hard. We also prove the same inapproximability threshold for degree-two polynomials by a twin-copy replacement of the cubic constraints. On the positive side, we give a nondeterministic search algorithm using only O(klog(en/k)) nondeterministic bits, and a deterministic fixed-parameter algorithm running in k^{6k+o(k)}n+O(m) time on an input with n symbols and m monomials.
Optimal circuit synthesis is the problem of finding the shortest-depth circuit representation of a given functionality with respect to a pre-specified elementary gate set. This is a central problem in both quantum and classical hardware design. While the classical version is very well understood -- both in terms of heuristics and rigorous hardness assertions -- much less is known about optimal quantum circuit synthesis. We focus on optimal Clifford circuit synthesis, for which various heuristics are known, e.g. via reduction to 3-SAT. Our main result supplies a matching hardness result: a variant of optimal Clifford synthesis is NP-hard. The proof proceeds in two parts: (i) reduce 3-edge colorability on 3-regular graphs to a circuit synthesis problem that only involves CZ gates, (ii) prove that the availability of additional elementary Clifford gates -- most notably: Hadamard, phase and CNOT -- cannot lead to further improvements of the optimal circuit depth. Our work sharpens the complexity-theoretic understanding of Clifford circuits: simulation and equivalence checking are in P, whereas deciding whether a Clifford unitary admits an implementation within a prescribed depth is NP-complete.
Solving combinatorial optimization problems on near-term quantum computers mainly relies on their quadratic unconstrained binary formulation. Lately, binary polynomial formulations start to take the center stage, having a better scaling with respect to the number of used qubits. However, while quadratic forms are straightforward to implement on quantum circuits, polynomial forms of degree ddd incur in circuit depth overheads, due to the lack of ddd-qubit gates, for d≥3d\geq 3d≥3, on current hardware. In this paper, we study the problem of designing the shallowest quantum circuit for a given polynomial form. We formulate it as a classical binary linear problem and we prove the \textsf{NP}-completeness of a variant of it. On the algorithmic side, we offer a scalable and performant heuristic method to tackle it, Tempura, as well as faster binary linear problem formulations, which offer computational feasibility while sacrificing optimality. Our performance evaluation shows that the algorithms yield far shorter circuits than the state-of-the-art approaches, and Tempura is mostly comparable with them in terms of runtime.
Solving combinatorial optimization problems on near-term quantum computers mainly relies on their quadratic unconstrained binary formulation. Lately, binary polynomial formulations start to take the center stage, having a better scaling with respect to the number of used qubits. However, while quadratic forms are straightforward to implement on quantum circuits, polynomial forms of degree d incur in circuit depth overheads, due to the lack of d-qubit gates, for d≥3, on current hardware. In this paper, we study the problem of designing the shallowest quantum circuit for a given polynomial form. We formulate it as a classical binary linear problem and we prove the NP-completeness of a variant of it. On the algorithmic side, we offer a scalable and performant heuristic method to tackle it, Tempura, as well as faster binary linear problem formulations, which offer computational feasibility while sacrificing optimality. Our performance evaluation shows that the algorithms yield far shorter circuits than the state-of-the-art approaches, and Tempura is mostly comparable with them in terms of runtime
Given A∈GL⁡(N,2)A\in\operatorname{GL}(N,2)A∈GL(N,2) and an integer KKK, we ask whether AAA can be implemented by at most KKK CNOT gates on fixed labelled wires with all-to-all connectivity. We prove that this problem is NP-complete. From a finite simple graph G=(V,E)G=(V,E)G=(V,E), we construct an upper-unitriangular matrix AG∈GL⁡(2∣V∣+∣E∣+1,2)A_G\in\operatorname{GL}(2|V|+|E|+1,2)AG​∈GL(2∣V∣+∣E∣+1,2) satisfying ℓCNOT(AG)=2∣V∣+2∣E∣+τ(G)\ell_{\mathrm{CNOT}}(A_G)=2|V|+2|E|+τ(G)ℓCNOT​(AG​)=2∣V∣+2∣E∣+τ(G), where τ(G)τ(G)τ(G) is the minimum vertex-cover size. Each target matrix has O(N)O(N)O(N) nonzero entries and row Hamming weight at most four. The lower bound unfolds an arbitrary CNOT circuit into an XOR directed acyclic graph and applies projection--contraction operations, allowing cancellation and unrestricted reuse of intermediate parities. For this family, the optimum is unchanged by any finite number of clean or borrowed ancillary wires that must be restored. A polynomial-time decoder further yields NP-hardness of approximation within every fixed additive constant and, through an L-reduction from Minimum Vertex Cover on cubic graphs, APX-hardness of the associated CNOT-circuit optimisation problem.
A parity network is a CNOT circuit in which every parity from a prescribed set S appears on some wire; such networks are the CNOT skeletons of phase-polynomial circuits. Amy, Azimzadeh and Mosca (Quantum Science and Technology, 2018) left open the ancilla-free problem with arbitrary output. We prove that deciding whether S admits such a network with at most K CNOTs is NP-complete, even if every CNOT must produce a new parity, all parities share a variable and have weight at most five, and connectivity is a star. Hence CNOT minimization of phase polynomials is NP-hard even with a free linear part. The reduction is from Hamiltonian cycle in grid graphs: networks meeting the trivial lower bound are path covers with at most one path per wire, and chaining many copies of the instance makes a missing Hamiltonian path cost more paths than there are wires. We also show that unrestricted networks can be shorter than fixed-target ones by a factor linear in the number of qubits. This is a preprint; it has not been peer reviewed.
Finding the shortest non-zero vector on a lattice is a fundamental problem in lattices that is believed to be hard both for classical and quantum computers. Two of the three standardised by NIST post-quantum cryptosystems rely on its hardness. Research on theoretical and practical performance of quantum algorithms to solve the Shortest Vector Problem (SVP) is crucial to establish confidence in those new standards. Exploring the capabilities that Variational Quantum Algorithms (VQA) that can run on Noisy Intermediate Scale Quantum (NISQ) devices have in solving SVP has been an active area of research. The qubit-requirement for doing so has been analysed and demonstrated that it is plausible to encode SVP on the ground state of a Hamiltonian in an efficient way. Due to the heuristic nature of VQAs no analysis of the performance and specifically of the time complexity of those approaches for scales beyond the non-interesting classically simulatable sizes has been performed. In this paper, motivated by Boulebnane and Montanaro [1] work on the k-SAT problem, we propose to use angle pretraining of the Quantum Approximate Optimisation Algorithm (QAOA) for SVP and we demonstrate that QAOA with fixed angles performs well on much larger instances than those used in training. Avoiding the limitations that arise due to the use of optimiser, we are able to extrapolate the observed performance and we observe the probability of success scaling as2−0.695n2^{-0.695n}2−0.695nwithnnnbeing dimensionality of the search space for a depthp=3p=3p=3pre-trained QAOA algorithm. By repeating the algorithm, we get heuristic time complexityO(20.695n)O(2^{0.695n})O(20.695n)to solve the problem with high probability, a bit worse than the fault-tolerant Grover approach ofO(20.5n)O(2^{0.5n})O(20.5n). On the other hand, both the number of qubits, and most importantly the depth of each quantum computation, are considerably better in our approach – Grover requires exponential depth, while each run of constantpppfixed-angles QAOA requires polynomial depth. Further, we analyse the performance of QAOA in solving approximate-SVP, a version of the problem that one seeks a multiplicative approximation to the shortest vector. As a side result, we propose a novel method to avoid the zero vector solution to SVP without introducing more logical qubits. This improves upon the previous works as it results in more space efficient encoding of SVP on NISQ architectures without ignoring the zero vector problem.