An exponential separation between quantum query complexity and the polynomial degree

DOI10.1007/S00037-025-00277-4MaRDI QIDQ6911409zbMATH OpenFDO

Authors Andris Ambainis, Aleksandrs Belovs

Publication date 24 October 2025

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00037-025-00277-4

zbMATH Keywords

polynomial methodquantum adversary boundquantum lower boundsquery 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)

Cites work

• Adversary lower bound for the k-sum problem
• Complexity measures and decision tree complexity: a survey.
• CREW PRAM<scp>s</scp> and Decision Trees
• Degree vs. approximate degree and Quantum implications of Huang’s sensitivity theorem
• scientific article; zbMATH DE number 5485488 (Why is no real title available?)
• scientific article; zbMATH DE number 7651029 (Why is no real title available?)
• On query-to-communication lifting for adversary bounds
• On the degree of Boolean functions as real polynomials
• On the power of non-adaptive learning graphs
• Quantum lower bound for the collision problem
• Quantum lower bounds by polynomials
• Quantum lower bounds by quantum arguments
• Quantum lower bounds for the collision and the element distinctness problems
• Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems
• Quantum Query Complexity of State Conversion
• Separations in query complexity using cheat sheets
• The polynomial method strikes back: tight quantum query bounds via dual polynomials

This page was built for publication: An exponential separation between quantum query complexity and the polynomial degree

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