We show that any quantum circuit of treewidth $t$, built from $r$-qubit gates, requires at least $Omega(frac{n^{2}}{2^{O(rcdot t)}cdot log^4 n})$ gates to compute the element distinctness function. Our result generalizes a near-quadratic lower bound for quantum formula size obtained by Roychowdhury and Vatan [SIAM J. on Computing, 2001]. The proof of our lower bound follows by an extension of Nev{c}iporuks method to the context of quantum circuits of constant treewidth. This extension is made via a combination of techniques from structural graph theory, tensor-network theory, and the connected-component counting method, which is a classic tool in algebraic geometry.
Download