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

DOI10.1007/S00037-014-0083-2zbMATH Open1314.68133arXiv1206.0717OpenAlexW1992351599MaRDI QIDQ488052FDOQ488052

Authors: Andris Ambainis, Ronald de Wolf 

Publication date: 23 January 2015

Published in: Computational Complexity (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Gaussian Hilbert Spaces
• Quantum Complexity Theory
• On the degree of Boolean functions as real polynomials
• Title not available (Why is that?)
• On the Fourier tails of bounded functions over the discrete cube
• Complexity measures and decision tree complexity: a survey.
• Quantum lower bounds for the collision and the element distinctness problems
• Title not available (Why is that?)
• Quantum lower bounds by polynomials
• Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
• Polynomial degree vs. quantum query complexity
• Optimal quantum query bounds for almost all Boolean functions.
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (4)

• Title not available (Why is that?)
• Quantum Query Complexity of Boolean Functions with Small On-Sets
• A quantum query algorithm for computing the degree of a perfect nonlinear Boolean function
• SOFSEM 2005: Theory and Practice of Computer Science

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)