Forrelation
Published in Proceedings of the forty-seventh annual ACM symposium on Theory of Computing • Jun 3, 2015
NobleIDNI0P99W20R37S05
Authors:,
Scott Aaronson
Andris Ambainis
Abstract
We achieve essentially the largest possible separation between quantum and classical query complexities. We do so using a property-testing problem called Forrelation, where one needs to decide whether one Boolean function is highly correlated with the Fourier transform of a second function. This pro...
Finding related papers...
Discussions
(0)No comments yet
Be the first to share your thoughts!