The search functionality is under construction.
The search functionality is under construction.

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

Hideaki FUKUHARA, Eiji TAKIMOTO

  • Full Text Views

    0

  • Cite this

Summary :

We introduce a complexity measure r for the class F of read-once formulas over the basis {AND,OR,NOT, XOR, MUX} and show that for any Boolean formula F in the class 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 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.

Publication
IEICE TRANSACTIONS on Information Vol.E93-D No.2 pp.280-289
Publication Date
2010/02/01
Publicized
Online ISSN
1745-1361
DOI
10.1587/transinf.E93.D.280
Type of Manuscript
Special Section PAPER (Special Section on Foundations of Computer Science)
Category

Authors

Keyword