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

DOI10.1007/s00037-014-0083-2zbMath1314.68133arXiv1206.0717OpenAlexW1992351599MaRDI QIDQ488052

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 algorithmsBoolean functionsquantum computingpolynomial approximations

Mathematics Subject Classification ID

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

Related Items (2)

A quantum query algorithm for computing the degree of a perfect nonlinear Boolean function ⋮ Unnamed Item

Cites Work

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

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