On the Complexity of the Circuit Width Problem
2026-06-16 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors study how hard it is to find the smallest number of qubits needed (width) to represent certain quantum circuit functions as polynomials. They prove that deciding if this width is below a given number is NP-complete, meaning it is a very hard problem. They also show it is hard to approximate this width and that similar difficulty holds for simpler polynomials. Additionally, they design some algorithms that work well when the width is small. Their work answers an open question and helps understand the complexity of analyzing quantum circuits.
Quantum circuitsPolynomial representationNP-completenessApproximation hardnessDegree-three polynomialsCircuit widthExponential Time HypothesisFixed-parameter algorithmApproximate countingComputational complexity
Authors
Zhengfeng Ji, Yinchen Liu, Zhe'ou Zhou
Abstract
Montanaro's polynomial representation expresses amplitudes of quantum circuits over the gates $H$, $Z$, $CZ$, and $CCZ$ as normalized gaps of degree-three polynomials over $\mathbb{F}_2$. The normalization is governed by the circuit width $w(f)$, the minimum number of qubits in any circuit realizing a polynomial $f$. Thus, efficient width minimization would give an approximate-counting route toward a combinatorial characterization of $BQP$. We study the computational complexity of this parameter. For degree-three polynomials with no constant term, deciding whether $w(f)\le k$ is $NP$-complete, resolving Montanaro's open question. We also prove $NP$-hardness of approximation within any factor $49/48-ε$, and show via a twin-copy construction that the exact and approximation hardness results also hold for degree-two polynomials. Under the Exponential Time Hypothesis, the exact problem admits no $2^{o(n)}$-time algorithm when $k=Θ(n)$. Complementing these hardness results, we give a nondeterministic polynomial-time search algorithm using $2\log_2\binom{n}{k}=O(k\log(en/k))$ witness bits, and a constructive fixed-parameter algorithm parameterized by $k$ with running time $k^{6k+o(k)}n+O(m)$.