pith. sign in

arxiv: 2606.18201 · v1 · pith:WBGB5GNLnew · submitted 2026-06-16 · 💻 cs.CC

On the Complexity of the Circuit Width Problem

Zhengfeng Ji , Yinchen Liu , Zhe'ou Zhou This is my paper

Pith reviewed 2026-06-26 21:44 UTC · model grok-4.3

classification 💻 cs.CC
keywords circuit widthNP-completenessdegree-three polynomialsquantum circuitsBQPapproximation hardnessfixed-parameter tractabilityMontanaro representation
0
0 comments X

The pith

Deciding whether a degree-three polynomial has circuit width at most k is NP-complete.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that for degree-three polynomials over F2 with no constant term, deciding if the circuit width w(f) is at most k is NP-complete. This parameter w(f) is the smallest number of qubits in a circuit over the gates H, Z, CZ, and CCZ that realizes the polynomial as the normalized gap in Montanaro's representation of quantum circuit amplitudes. A sympathetic reader would care because an efficient algorithm for minimizing width would open a combinatorial route to approximate counting and thus to a characterization of BQP. The authors also establish NP-hardness of approximation to within any factor 49/48 minus epsilon, extend both exact and approximation hardness to degree-two polynomials via a twin-copy construction, and prove that under the Exponential Time Hypothesis there is no 2 to the o(n) algorithm when k is linear in n. They complement the hardness with a nondeterministic polynomial-time search procedure that uses O(k log(en/k)) witness bits and a fixed-parameter tractable algorithm running in k to the 6k plus o(k) times n plus O(m).

Core claim

For degree-three polynomials with no constant term, deciding whether w(f) ≤ k is NP-complete. The same holds for approximation within any factor 49/48 - ε. Both the exact and approximation hardness carry over to degree-two polynomials by a twin-copy construction. Under the Exponential Time Hypothesis the exact problem admits no 2^{o(n)}-time algorithm when k = Θ(n). There is a nondeterministic polynomial-time search algorithm using 2 log2 binom(n,k) = O(k log(en/k)) witness bits, and a constructive fixed-parameter algorithm parameterized by k that runs in time k^{6k+o(k)} n + O(m).

What carries the argument

The circuit width w(f), defined as the minimum number of qubits in any circuit over H, Z, CZ, CCZ realizing the polynomial f as the normalized gap.

If this is right

  • Approximating circuit width to within any factor better than 49/48 - ε is NP-hard.
  • Under the Exponential Time Hypothesis, no 2^{o(n)}-time algorithm exists for the exact decision problem when k = Θ(n).
  • The minimum width can be searched nondeterministically in polynomial time using only O(k log(en/k)) witness bits.
  • The problem is fixed-parameter tractable in k with running time k^{6k+o(k)} n + O(m).

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The hardness suggests that combinatorial characterizations of BQP via width minimization are unlikely to be efficient.
  • The twin-copy reduction may allow similar width parameters to be studied in other algebraic or combinatorial settings beyond the original gate set.
  • The nondeterministic and FPT algorithms indicate that the problem remains tractable in restricted regimes even though it is NP-complete in general.

Load-bearing premise

Montanaro's representation theorem correctly expresses circuit amplitudes as normalized gaps of degree-three polynomials whose normalization factor is exactly the minimum realizing width w(f).

What would settle it

A deterministic polynomial-time algorithm that decides whether w(f) ≤ k for arbitrary degree-three polynomials with no constant term.

Figures

Figures reproduced from arXiv: 2606.18201 by Yinchen Liu, Zhengfeng Ji, Zhe'ou Zhou.

Figure 1
Figure 1. Figure 1: A quantum circuit with 3 qubits and 4 internal Hadamard gates. The polynomial [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Clause gadget for the illustrative clause [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Illustration of the nondeterministic algorithm’s progress for f = x1x2+x2x3+y1y2+z1z2+x2y1+ x2y2 + x2y2z1. Given the witness Shead = {x1, y1, z1} (pink) and Stail = {x3, y2, z2} (blue), the algorithm deterministically finds the circuit. At each step, it finds a current head symbol (green) with degree 1 in the graph Gf and extends the wire. The first step detects (for example) x1 and replaces x1 by x2 in th… view at source ↗
Figure 4
Figure 4. Figure 4: Segments labeled X1, X2 on the first qubit and Y1, Y2 on the second qubit with supports supp(X1) = (0, 1 3 ), supp(X2) = ( 1 3 , 1), supp(Y1) = (0, 2 3 ), supp(Y2) = ( 2 3 , 1). Overlapping pairs are (X1, Y1), (X2, Y1), and (X2, Y2), but supp(X1) ∩ supp(Y2) = ∅. To simplify arguments concerning intersections of supports of multiple symbols (which are open intervals on the time axis), we recall a classical … view at source ↗
Figure 5
Figure 5. Figure 5: Variable gadget. Supports: b = (0, 1); tc = (0, 0.25), tˆc = (0.25, 0.75), t˜c = (0.75, 1); xc = (0, 0.3), ˆxc = (0.3, 0.7), ¯xc = (0.7, 1). CCZ columns enforce the cubic terms b tˆc xc, b tˆc xˆc, and b tˆc x¯c. 3.1.4 Clause Gadget A three-literal clause c = (x ∨ y ∨ z) is represented as the nesting of two binary disjunctions pc = x ∨ y, oc = pc ∨ z. Thus pc is the intermediate truth value of the first tw… view at source ↗
Figure 6
Figure 6. Figure 6: OR gadget. Supports: b = (0, 1); tc = (0, 1 4 ), tˆc = ( 1 4 , 3 4 ), t˜c = ( 3 4 , 1); u = (0.1, 0.6); v = (0.3, 0.9); ←−q = (0, 0.2), q = (0.2, 0.8), −→q = (0.8, 1). Columns mark CCZ gates on (b, u, ←−q ), (b, u, q), (b, v, q), and (b, v, −→q ). Full clause gadget. For the clause c = (x ∨ y ∨ z), we concatenate two OR gadgets and add one final synchronizing term: Gc = Gxc∨yc + Gpc∨zc + b tc oc. The last … view at source ↗
Figure 7
Figure 7. Figure 7: Illustration of the check algorithm in Lemma 5.1 for associated polynomial f = x1x2 + x2x3 + y1y2 +z1z2 +x2y1 +x2y2 +x2y2z1. Left: given ordered lists Li with symbols on each wire. Middle: Directed graph GH is constructed, where vertices represent Hadamard gates, black solid edges enforce wire ordering, and red dashed edges represent constraints given by quadratic and cubic monomials (ignoring self-loops o… view at source ↗
Figure 8
Figure 8. Figure 8: Illustration of the nondeterministic algorithm’s progress for f = x1x2+x2x3+y1y2+z1z2+x2y1+ x2y2 + x2y2z1. Given the witness Shead = {x1, y1, z1} (pink) and Stail = {x3, y2, z2} (blue), the algorithm deterministically finds the circuit. At each step, it finds a current head symbol (green) with degree 1 in the graph Gf and extends the wire. The first step detects (for example) x1 and replaces x1 by x2 in th… view at source ↗
Figure 9
Figure 9. Figure 9: Example state (Wx, Ox) at a node x in a tree decomposition. Top: the bag Bx and the vertex set Vx of the subtree rooted at x; gray symbols p, q ∈ Vx \ Bx are forgotten, and the path c−p−q−d illustrates connectivity used by τ = 2. Middle: the wire structure Wx partitions Bx into ordered lists with edge types τ ∈ {0, 1, 2}, where τ = 0 indicates complete disconnection. Bottom: a topological ordering Ox on th… view at source ↗
read the original 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-\epsilon$, 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=\Theta(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)$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 4 minor

Summary. The paper studies the circuit width w(f), defined as the minimum number of qubits realizing a polynomial f via Montanaro's representation of amplitudes for circuits over H, Z, CZ, CCZ gates as normalized gaps of degree-3 polynomials over F_2. It proves that deciding w(f) ≤ k is NP-complete for degree-3 polynomials with no constant term (resolving Montanaro's open question), shows NP-hardness of approximation to within any factor 49/48−ε, extends both results to degree-2 polynomials via a twin-copy construction, establishes an ETH-based lower bound of no 2^{o(n)}-time algorithm for k=Θ(n), and supplies a nondeterministic search algorithm using O(k log n) witness bits together with an FPT algorithm running in k^{6k+o(k)}n + O(m) time.

Significance. If the reductions and algorithms are correct, the results give the first complexity classification of the width parameter central to Montanaro's approach toward a combinatorial view of BQP. The exact NP-completeness, inapproximability threshold, ETH lower bound, and the unusually small witness size O(k log n) are all load-bearing contributions; the FPT runtime, while not practical, is a standard positive counterpart to the hardness side.

minor comments (4)
  1. [§2] §2 (Preliminaries): the precise statement of Montanaro's representation theorem (including the exact normalization factor relating the gap to the amplitude) should be restated verbatim before the complexity results, as it is invoked in every reduction.
  2. [§4] Theorem 1.1 and the twin-copy construction in §4: the degree-2 case is obtained by a product construction; a short paragraph explaining why the width of the product is exactly twice the original width would remove any ambiguity about the reduction preserving the parameter k.
  3. [§5] The FPT algorithm in §5: the exponent 6k appears without an explicit derivation of the polynomial degree or the branching factor; adding a one-sentence reference to the underlying bounded-search-tree analysis would improve readability.
  4. [Abstract / §1] Notation: the symbol m (number of monomials) is used in the FPT runtime but never defined in the abstract or introduction; a parenthetical definition on first use would help.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, recognition of the significance of the results, and recommendation of minor revision. We are pleased that the contributions on NP-completeness, inapproximability, ETH bounds, and the FPT algorithm are viewed as load-bearing.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained via external reductions

full rationale

The paper proves NP-completeness of deciding w(f) ≤ k for degree-3 no-constant-term polynomials by reduction from known NP-complete problems (standard Karp-style reduction) and gives a nondeterministic search algorithm plus FPT algorithm. w(f) is defined externally as min qubits realizing f via Montanaro's representation theorem (cited, not self-cited). No equation reduces to itself by construction, no fitted parameter is relabeled as prediction, and no load-bearing step collapses to a self-citation chain. The abstract and claimed results contain independent content outside any internal definition loop.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Review based solely on abstract; full list of background assumptions cannot be extracted. The central claim rests on Montanaro's representation theorem and standard complexity definitions.

axioms (2)
  • domain assumption Montanaro's theorem that amplitudes equal normalized gaps of degree-3 polynomials over F2 whose normalization is governed by circuit width
    Invoked in the first sentence of the abstract as the foundation for the width parameter.
  • standard math Standard definitions of NP-completeness, approximation hardness, and ETH
    Used to state the complexity results.

pith-pipeline@v0.9.1-grok · 5760 in / 1332 out tokens · 26426 ms · 2026-06-26T21:44:51.035632+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

43 extracted references · 19 canonical work pages

  1. [1]

    Proceedings of the 37th International Conference on Computer Aided Verification , author =

  2. [2]

    Quantum circuit complexity , year =

    Andrew Chi-Chih Yao , booktitle =. Quantum circuit complexity , year =

  3. [3]

    Feynman, R. P. , title =. International Journal of Theoretical Physics , volume =. 1982 , doi =

    1982

  4. [4]

    Journal of Physics A: Mathematical and Theoretical , abstract =

    Montanaro, Ashley , title =. Journal of Physics A: Mathematical and Theoretical , abstract =. 2017 , month =. doi:10.1088/1751-8121/aa565f , url =

    work page doi:10.1088/1751-8121/aa565f 2017

  5. [5]

    , journal =

    Helly, Ed. , journal =

  6. [6]

    Which Problems Have Strongly Exponential Complexity?

    Russell Impagliazzo and Ramamohan Paturi and Francis Zane , abstract =. Which Problems Have Strongly Exponential Complexity? , journal =. 2001 , issn =. doi:https://doi.org/10.1006/jcss.2001.1774 , url =

    work page doi:10.1006/jcss.2001.1774 2001

  7. [7]

    On the Complexity of k-SAT , journal =

    Russell Impagliazzo and Ramamohan Paturi , abstract =. On the Complexity of k-SAT , journal =. 2001 , issn =. doi:https://doi.org/10.1006/jcss.2000.1727 , url =

    work page doi:10.1006/jcss.2000.1727 2001

  8. [8]

    Some optimal inapproximability results,

    H. Some optimal inapproximability results , year =. J. ACM , month = jul, pages =. doi:10.1145/502090.502098 , abstract =

    work page doi:10.1145/502090.502098

  9. [9]

    and Hines, Andrew P

    Dawson, Christopher M. and Hines, Andrew P. and Mortimer, Duncan and Haselgrove, Henry L. and Nielsen, Michael A. and Osborne, Tobias J. , title =. Quantum Info. Comput. , month = mar, pages =. 2005 , issue_date =

    2005

  10. [10]

    Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing , pages =

    Aharonov, Dorit and Jones, Vaughan and Landau, Zeph , title =. Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing , pages =. 2006 , isbn =. doi:10.1145/1132516.1132579 , abstract =

    work page doi:10.1145/1132516.1132579 2006

  11. [11]

    Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences , year =

    Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy , author =. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences , year =

  12. [12]

    52 Jean-Pierre Tillich

    Shor, Peter W. , title =. SIAM Journal on Computing , volume =. 1997 , doi =. https://doi.org/10.1137/S0097539795293172 , abstract =

    work page doi:10.1137/s0097539795293172 1997

  13. [13]

    Aaronson \ and\ author A

    Aaronson, Scott and Arkhipov, Alex , title =. Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing , pages =. 2011 , isbn =. doi:10.1145/1993636.1993682 , abstract =

    work page doi:10.1145/1993636.1993682 2011

  14. [14]

    arXiv preprint , eprint =

    Scott Aaronson , title =. arXiv preprint , eprint =

  15. [15]

    2015 , pages =

    Kuperberg, Greg , title =. 2015 , pages =. doi:10.4086/toc.2015.v011a006 , journal =

    work page doi:10.4086/toc.2015.v011a006 2015

  16. [16]

    New Journal of Physics , abstract =

    Fujii, Keisuke and Morimae, Tomoyuki , title =. New Journal of Physics , abstract =. 2017 , month =. doi:10.1088/1367-2630/aa5fdb , url =

    work page doi:10.1088/1367-2630/aa5fdb 2017

  17. [17]

    Bremner and Richard Jozsa and Dan J

    Michael J. Bremner and Richard Jozsa and Dan J. Shepherd , title =. Proc. R. Soc. A , volume =

  18. [18]

    Shepherd and M

    D. Shepherd and M. J. Bremner , title =. Proc. Roy. Soc. Ser. A , volume =

  19. [19]

    and Shi, Yaoyun , title =

    Markov, Igor L. and Shi, Yaoyun , title =. SIAM Journal on Computing , volume =. 2008 , doi =

    2008

  20. [20]

    Bin Cheng and Ziyuan Wang and Ruixuan Deng and Jianxin Chen and Zhengfeng Ji , title =

  21. [21]

    Quantum Info

    Shi, Yaoyun , title =. Quantum Info. Comput. , month = jan, pages =. 2003 , issue_date =

    2003

  22. [22]

    Power of One Bit of Quantum Information , author =. Phys. Rev. Lett. , volume =. 1998 , month =. doi:10.1103/PhysRevLett.81.5672 , url =

    work page doi:10.1103/physrevlett.81.5672 1998

  23. [23]

    quant-ph/0301040 , archiveprefix =

    Aharonov, Dorit , title =. quant-ph/0301040 , archiveprefix =

    Pith/arXiv arXiv

  24. [24]

    and DeMarrais, Jonathan and Huang, Ming-Deh A

    Adleman, Leonard M. and DeMarrais, Jonathan and Huang, Ming-Deh A. , title =. SIAM Journal on Computing , volume =. 1997 , doi =

    1997

  25. [25]

    Complexity Limitations on Quantum Computation , journal =

    Lance Fortnow and John Rogers , abstract =. Complexity Limitations on Quantum Computation , journal =. 1999 , issn =. doi:https://doi.org/10.1006/jcss.1999.1651 , url =

    work page doi:10.1006/jcss.1999.1651 1999

  26. [26]

    Knill and R

    E. Knill and R. Laflamme , keywords =. Quantum computing and quadratically signed weight enumerators , journal =. 2001 , issn =. doi:https://doi.org/10.1016/S0020-0190(00)00222-2 , url =

    work page doi:10.1016/s0020-0190(00)00222-2 2001

  27. [27]

    Quantum algorithms for spin models and simulable gate sets for quantum computation , author =. Phys. Rev. A , volume =. 2009 , month =. doi:10.1103/PhysRevA.80.052334 , url =

    work page doi:10.1103/physreva.80.052334 2009

  28. [28]

    Theory of Computing , volume =

    Janzing, Dominik and Wocjan, Pawel , title =. Theory of Computing , volume =. 2007 , pages =. doi:10.4086/toc.2007.v003a004 , publisher =

    work page doi:10.4086/toc.2007.v003a004 2007

  29. [29]

    Average-Case Complexity Versus Approximate Simulation of Commuting Quantum Computations , author =. Phys. Rev. Lett. , volume =. 2016 , month =. doi:10.1103/PhysRevLett.117.080501 , url =

    work page doi:10.1103/physrevlett.117.080501 2016

  30. [30]

    doi:10.22331/q-2020-05-11-264 , url =

    How many qubits are needed for quantum computational supremacy? , author =. doi:10.22331/q-2020-05-11-264 , url =

    work page doi:10.22331/q-2020-05-11-264 2020

  31. [31]

    Kahn, A. B. , title =. Communications of the ACM , volume =. 1962 , publisher =

    1962

  32. [32]

    Graph minors. I. Excluding a forest , author =. Journal of Combinatorial Theory, Series B , volume =

  33. [33]

    Acta cybernetica , volume =

    A tourist guide through treewidth , author =. Acta cybernetica , volume =

  34. [34]

    2013 , publisher =

    Fundamentals of Parameterized Complexity , author =. 2013 , publisher =

    2013

  35. [35]

    and Kowalik, ukasz and Lokshtanov, Daniel and Marx, D\'aniel and Pilipczuk, Marcin and Pilipczuk, Micha

    Marek Cygan and Fedor V. Fomin and Lukasz Kowalik and Daniel Lokshtanov and D. Parameterized Algorithms , publisher =. 2015 , url =. doi:10.1007/978-3-319-21275-3 , isbn =

    work page doi:10.1007/978-3-319-21275-3 2015

  36. [36]

    and Drange, P

    Bodlaender, Hans L. and Drange, P. A. SIAM Journal on Computing , volume =. 2016 , doi =

    2016

  37. [37]

    2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages =

    A Single-Exponential Time 2-Approximation Algorithm for Treewidth , author =. 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages =. 2021 , organization =

    2021

  38. [38]

    1994 , publisher =

    Treewidth: computations and approximations , author =. 1994 , publisher =

    1994

  39. [39]

    SIAM Journal on Computing , volume =

    A linear-time algorithm for finding tree-decompositions of small treewidth , author =. SIAM Journal on Computing , volume =. 1996 , publisher =

    1996

  40. [40]

    The monadic second-order logic of graphs. I. Recognizable sets of finite graphs , author =. Information and computation , volume =. 1990 , publisher =

    1990

  41. [41]

    SIAM Journal on Computing , volume =

    Korhonen, Tuukka and Lokshtanov, Daniel , title =. SIAM Journal on Computing , volume =. 2023 , doi =

    2023

  42. [42]

    Lokshtanov, Daniel and Ramanujan, M. S. and Saurabh, Saket , title =. Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018 , series =. 2018 , publisher =. doi:10.1007/978-3-030-00256-5_31 , url =

    work page doi:10.1007/978-3-030-00256-5_31 2018

  43. [43]

    Journal of the ACM , volume =

    Dinur, Irit , title =. Journal of the ACM , volume =. 2007 , publisher =. doi:10.1145/1236457.1236459 , url =

    work page doi:10.1145/1236457.1236459 2007