The polynomial method strikes back: tight quantum query bounds via dual polynomials

DOI10.1145/3188745.3188784zbMath1427.68085arXiv1710.09079OpenAlexW3099921078WikidataQ130920938 ScholiaQ130920938MaRDI QIDQ5230298

Justin Thaler, Robin Kothari, Mark Bun

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

polynomial methodquantum query complexityapproximate degreedual polynomials

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (15)

Approximate Degree in Classical and Quantum Computing ⋮ Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ Unnamed Item ⋮ A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Algorithmic Polynomials ⋮ Quantum Query Algorithms Are Completely Bounded Forms ⋮ Approximate Degree, Secret Sharing, and Concentration Phenomena ⋮ Quantum algorithm for the multicollision problem ⋮ A quantum evolving secret sharing scheme ⋮ Unnamed Item ⋮ Query complexity of generalized Simon's problem ⋮ Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity ⋮ Unnamed Item

This page was built for publication: The polynomial method strikes back: tight quantum query bounds via dual polynomials