A Near-Quadratic Lower Bound for the Size of Quantum Circuits of Constant Treewidth

Abstract

We show that any quantum circuit of treewidth $t$, built from $r$-qubit gates, requires at least $\Omega (\frac{n^2}{2^{O(r\cdot 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 Nečiporuk's 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.