Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR15-108 | 30th June 2015 16:31

A Super-Grover Separation Between Randomized and Quantum Query Complexities

RSS-Feed




TR15-108
Authors: Shalev Ben-David
Publication: 30th June 2015 16:46
Downloads: 1998
Keywords: 


Abstract:

We construct a total Boolean function $f$ satisfying
$R(f)=\tilde{\Omega}(Q(f)^{5/2})$, refuting the long-standing
conjecture that $R(f)=O(Q(f)^2)$ for all total Boolean functions.
Assuming a conjecture of Aaronson and Ambainis about optimal quantum speedups for partial functions,
we improve this to $R(f)=\tilde{\Omega}(Q(f)^3)$.
Our construction is motivated by the Göös-Pitassi-Watson function
but does not use it.



ISSN 1433-8092 | Imprint