Quantum Physics, abstract
quant-ph/9910033
From: "Lane A. Hemaspaandra" <[EMAIL PROTECTED]>
Date (v1): Fri, 8 Oct 1999 03:48:56 GMT (17kb)
Date (revised v2): Mon, 11 Oct 1999 19:03:38 GMT (17kb)
Almost-Everywhere Superiority for Quantum Computing
Authors: Edith Hemaspaandra (RIT), Lane A. Hemaspaandra (University of Rochester),
Marius Zimand (Towson University)
Comments: 11 pages
Report-no: URCS-TR-99-720
Subj-class: Quantum Physics; Computational Complexity
Simon as extended by Brassard and H{\o}yer shows that there are
tasks on which quantum machines are exponentially faster than
each classical machine infinitely often. The present paper shows
that there are tasks on which quantum machines are exponentially
faster than each classical machine almost everywhere.
Julian.
