We introduce a complexity measure r for the class $\mathcal{F}$ of read-once formulas over the basis {AND, OR, NOT, XOR, MUX} and show that for any Boolean formula F in the class $\mathcal{F}$ , r(F) is a lower bound on the quantum query complexity of the Boolean function that F represents. We also show that for any Boolean function f represented by a formula in $\mathcal{F}$ , the deterministic query complexity of f is only quadratically larger than the quantum query complexity of f. Thus, the paper gives further evidence for the conjecture that there is an only quadratic gap for all functions.We introduce a complexity measure r for the class $\mathcal{F}$ of read-once formulas over the basis {AND, OR, NOT, XOR, MUX} and show that for any Boolean formula F in the class $\mathcal{F}$, r(F) is a lower bound on the quantum query complexity of the Boolean function that F represents. We also show that for any Boolean function f represented by a formula in $\mathcal{F}$, the deterministic query complexity of f is only quadratically larger than the quantum query complexity of f. Thus, the paper gives further evidence for the conjecture that there is an only quadratic gap for all functions.

IEICE Transactions on Information and SystemsJan 1, 20100 citations

On Exact Quantum Query Complexity

Ashley Montanaro, Richard Jozsa, Graeme Mitchison

arXiv:1111.0475AlgorithmicaAug 29, 201334 citations

The Quantum Query Complexity of Algebraic Properties

Sebastian Dörn, Thomas Thierauf

Lecture notes in computer scienceAug 27, 200718 citations

We introduce a complexity measure r for the class

\mathcal{F}

of read-once formulas over the basis {AND, OR, NOT, XOR, MUX} and show that for any Boolean formula F in the class

\mathcal{F}

, r(F) is a lower bound on the quantum query complexity of the Boolean function that F represents. We also show that for any Boolean function f represented by a formula in

\mathcal{F}

, the deterministic query complexity of f is only quadratically larger than the quantum query complexity of f. Thus, the paper gives further evidence for the conjecture that there is an only quadratic gap for all functions.