A de Morgan formula over Boolean variables x1,…,xn is a binary tree whose internal nodes are marked with AND or OR gates and whose leaves are marked with variables or their negation. We define the size of the formula as the number of leaves in it. Proving that some explicit function (in P or NP) requires a large formula is a central open question in computational complexity. While we believe that some explicit functions require exponential formula size, currently the best lower bound for an explicit function is the Ω(n3) lower bound for Andreev's function.A de Morgan formula over Boolean variables x1,…,xn is a binary tree whose internal nodes are marked with AND or OR gates and whose leaves are marked with variables or their negation. We define the size of the formula as the number of leaves in it. Proving that some explicit function (in P or NP) requires a large formula is a central open question in computational complexity. While we believe that some explicit functions require exponential formula size, currently the best lower bound for an explicit function is the Ω(n3) lower bound for Andreev's function.

ACM Symposium on Theory of Computing (STOC)Jun 15, 201717 citations

On Exact Quantum Query Complexity

Ashley Montanaro, Richard Jozsa, Graeme Mitchison

arXiv:1111.0475AlgorithmicaAug 29, 201334 citations

Lower Bounds on Quantum Query Complexity for Read-Once Formulas with XOR and MUX Operators

Hideaki Fukuhara, Eiji Takimoto

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

Quantum query algorithms and lower bounds

Andris Ambainis

Springer eBooksNov 2, 200726 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.