{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreid7lyrngwo4ievy2szcb3jkx2bf75yz5ze4jjfmj24trqxoz4vwqm",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mohupaiuuey2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2606.18201v1",
  "publishedAt": "2026-06-17T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Zhengfeng Ji",
    "Yinchen Liu",
    "Zhe'ou Zhou"
  ],
  "textContent": "**Authors:** Zhengfeng Ji, Yinchen Liu, Zhe'ou Zhou\n\nMontanaro'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)$.",
  "title": "On the Complexity of the Circuit Width Problem"
}