How low can approximate degree and quantum query complexity be for total Boolean functions?

DOI10.1007/S00037-014-0083-2MaRDI QIDQ488052zbMATHOpenAlexFDO

Authors Andris Ambainis, Ronald de Wolf

Publication date 23 January 2015

Published in Computational Complexity (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityquantum algorithmsquantum computingBoolean functionspolynomial approximations

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12) Approximation by polynomials (41A10) Boolean functions (06E30)

Abstract: It has long been known that any Boolean function that depends on n input variables has both degree and exact quantum query complexity of Omega(log n), and that this bound is achieved for some functions. In this paper we study the case of approximate degree and bounded-error quantum query complexity. We show that for these measures the correct lower bound is Omega(log n / loglog n), and we exhibit quantum algorithms for two functions where this bound is achieved.

Recommendations

• SOFSEM 2005: Theory and Practice of Computer Science
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• Optimal quantum query bounds for almost all Boolean functions

Cites work

• scientific article; zbMATH DE number 5605137 (Why is no real title available?)
• scientific article; zbMATH DE number 3829252 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 2103524 (Why is no real title available?)
• scientific article; zbMATH DE number 5485570 (Why is no real title available?)
• Complexity measures and decision tree complexity: a survey.
• Gaussian Hilbert Spaces
• On the Fourier tails of bounded functions over the discrete cube
• On the degree of Boolean functions as real polynomials
• Optimal quantum query bounds for almost all Boolean functions
• Polynomial degree vs. quantum query complexity
• Quantum Complexity Theory
• Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
• Quantum lower bounds by polynomials
• Quantum lower bounds for the collision and the element distinctness problems

Cited in

(7)

• SOFSEM 2005: Theory and Practice of Computer Science
• scientific article; zbMATH DE number 7561760 (Why is no real title available?)
• Quantum Query Complexity of Boolean Functions with Small On-Sets
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• A quantum query algorithm for computing the degree of a perfect nonlinear Boolean function
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables

This page was built for publication: How low can approximate degree and quantum query complexity be for total Boolean functions?

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