Almost-Everywhere Superiority for Quantum Computing
<|reference_start|>Almost-Everywhere Superiority for Quantum Computing: Simon as extended by Brassard and H{\o}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.<|reference_end|>
@article{hemaspaandra1999almost-everywhere,
    title={Almost-Everywhere Superiority for Quantum Computing},
    author={Edith Hemaspaandra (RIT), Lane A. Hemaspaandra (University of
  Rochester), Marius Zimand (Towson University)},
    journal={arXiv preprint arXiv:quant-ph/9910033},
    year={1999},
    number={Revised version of URCS-TR-99-720},
    archivePrefix={arXiv},
    eprint={quant-ph/9910033},
    primaryClass={quant-ph cs.CC}
}