Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > FORRELATION:
Reports tagged with Forrelation:
TR19-179 | 7th December 2019
Avishay Tal

Towards Optimal Separations between Quantum and Randomized Query Complexities

Revisions: 1

The query model offers a concrete setting where quantum algorithms are provably superior to randomized algorithms. Beautiful results by Bernstein-Vazirani, Simon, Aaronson, and others presented partial Boolean functions that can be computed by quantum algorithms making much fewer queries compared to their randomized analogs. To date, separations of $O(1)$ vs. ... more >>>




ISSN 1433-8092 | Imprint