A lower bound on the quantum query complexity of read-once functions

Howard Barnum, Michael Saks

We establish a lower bound of $\Omega (\sqrt{n})$ on the bounded-error quantum query complexity of read-once Boolean functions, providing evidence for the conjecture that $Ω(\sqrt{D(f)…