Almost-Everywhere Superiority for Quantum Computing

Edith Hemaspaandra, Lane A. Hemaspaandra, Marius Zimand

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.…