DROPS

Document

DOI: 10.4230/LIPIcs.TQC.2026.7

On the Complexity of the Circuit Width Problem

Authors: Zhengfeng Ji, Yinchen Liu, and Zhe'ou Zhou

Published in: LIPIcs, Volume 389, 21st Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2026)

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.

Cite as

Zhengfeng Ji, Yinchen Liu, and Zhe'ou Zhou. On the Complexity of the Circuit Width Problem. In 21st Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 389, pp. 7:1-7:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ji_et_al:LIPIcs.TQC.2026.7,
  author =	{Ji, Zhengfeng and Liu, Yinchen and Zhou, Zhe'ou},
  title =	{{On the Complexity of the Circuit Width Problem}},
  booktitle =	{21st Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2026)},
  pages =	{7:1--7:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-439-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{389},
  editor =	{Arnon, Rotem and Harrow, Aram W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2026.7},
  URN =		{urn:nbn:de:0030-drops-273045},
  doi =		{10.4230/LIPIcs.TQC.2026.7},
  annote =	{Keywords: IQP circuits, circuit width, NP-completeness, approximation hardness, parameterized algorithms}
}

Search Results

Documents authored by Liu, Yinchen

On the Complexity of the Circuit Width Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message