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


IEICE TRANSACTIONS on Information and Systems   Vol.E93-D   No.2   pp.280-289
Publication Date: 2010/02/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E93.D.280
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
quantum query complexity,  read-once formulas,  decision trees,  adversary method,  

Full Text: PDF(270.1KB)
>>Buy this Article

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.