Optimal quantum query bounds for almost all Boolean functions

DOI10.4230/LIPICS.STACS.2013.446MaRDI QIDQ2957905zbMATH OpenOpenAlexFDO

Authors Artūrs Bačkurs, J. Smotrovs, Andris Ambainis, Ronald de Wolf

Publication date 30 January 2017

Full work available at URL https://arxiv.org/abs/1208.1122

zbMATH Keywords

lower boundspolynomial methodquantum computingquery complexity

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum computation (81P68)

Abstract: We show that almost all n-bit Boolean functions have bounded-error quantum query complexity at least n/2, up to lower-order terms. This improves over an earlier n/4 lower bound of Ambainis, and shows that van Dam's oracle interrogation is essentially optimal for almost all functions. Our proof uses the fact that the acceptance probability of a T-query algorithm can be written as the sum of squares of degree-T polynomials.

Recommendations

• Quantum query complexity of almost all functions with fixed on-set size
• Quantum Query Complexity of Boolean Functions with Small On-Sets
• SOFSEM 2005: Theory and Practice of Computer Science
• A lower bound on the quantum query complexity of read-once functions
• Quantum lower bounds by polynomials

Cited in

(11)

• A lower bound on the quantum query complexity of read-once functions
• Superlinear advantage for exact quantum algorithms
• Quantum query complexity of almost all functions with fixed on-set size
• Quantum query algorithms for conjunctions
• Quantum Query Complexity of Boolean Functions with Small On-Sets
• Unbounded-Error Quantum Query Complexity
• Optimality proofs of quantum weight decision algorithms
• scientific article; zbMATH DE number 2051219 (Why is no real title available?)
• How low can approximate degree and quantum query complexity be for total Boolean functions?
• SOFSEM 2005: Theory and Practice of Computer Science
• Unbounded-error quantum query complexity

This page was built for publication: Optimal quantum query bounds for almost all Boolean functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2957905)