2026-08-25T11:01:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27304 2026-08-25T07:42:36Z ddc:004 open_access

On the Complexity of the Circuit Width Problem Ji, Zhengfeng Liu, Yinchen Zhou, Zhe'ou IQP circuits circuit width NP-completeness approximation hardness parameterized algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zhengfeng Ji and Yinchen Liu and Zhe'ou Zhou 2026 Is Part Of LIPIcs, Volume 389, 21st Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TQC.2026.7 urn:nbn:de:0030-drops-273045 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2026.7 eng https://creativecommons.org/licenses/by/4.0/legalcode