On the Complexity of the Circuit Width Problem (opens in new tab)

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 s...