Almost-Everywhere Superiority for Quantum Computing
Edith Hemaspaandra, Lane A. Hemaspaandra, Marius Zimand · arXiv (Cornell University) · 1999
Simon as extended by Brassard and Høyer shows that there are tasks on which polynomial-time quantum machines are exponentially faster than each classical machine infinitely often. The present paper shows that there are tasks on which polynomial-time quantum machines are exponentially faster than each classical machine almost everywhere.