Yinchen Liu

We study the circuit width problem introduced by Montanaro in the polynomial representation of quantum circuits over the gate set ({H,Z,\mathrm{CZ},\mathrm{CCZ}}). In this framework, a circuit corresponds to a low‑degree polynomial over (\mathbb{F}_2), and the circuit width (w(f)) is the minimum number of qubits among circuits realizing a given polynomial (f). This parameter governs the precision with which a quantum computer can approximate the gap of (f), motivating the complexity of minimizing (w(f)). We prove that deciding whether (w(f)\le k) is NP‑complete, and that approximating (w(f)) within any factor better than (49/48-\epsilon) is NP‑hard. This inapproximability persists even for degree‑2 polynomials, showing that the hardness is gate‑set independent for common quadratic gate sets. On the algorithmic side, we give a nondeterministic polynomial‑time search algorithm with witness size (O(k\log(n/k))), yielding an XP algorithm by enumeration, and a fixed‑parameter tractable algorithm running in time (k^{O(k)}\cdot n). These results resolve Montanaro’s open question and place circuit width firmly within classical complexity theory while providing efficient algorithms for small width.