On the Complexity of the Circuit Width Problem

Zhengfeng Ji, Yinchen Liu, Zhe'ou Zhou

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…