Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with real polynomials:
TR14-155 | 21st November 2014
Scott Aaronson, Andris Ambainis

Forrelation: A Problem that Optimally Separates Quantum from Classical Computing

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 problem can be solved using 1 quantum ... more >>>

ISSN 1433-8092 | Imprint