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

preprint2016arXivOpen access

Abstract

We show that any quantum circuit of treewidth tt, built from rr-qubit gates, requires at least Ω(n22O(r⋅t)⋅log⁡4n)Ω(\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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.