[5916] in cryptography@c2.net mail archive
Almost-Everywhere Superiority for Quantum Computing
daemon@ATHENA.MIT.EDU (Julian Assange)
Sun Oct 17 18:01:34 1999
To: cryptography@c2.com
Cc: proff@iq.org
Cc: ben-the-unbeliever@algroup.co.uk
From: Julian Assange <proff@iq.org>
Date: 14 Oct 1999 02:21:25 +1000
Message-ID: <wx670bi64a.fsf@suburbia.net>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Quantum Physics, abstract
quant-ph/9910033
From: "Lane A. Hemaspaandra" <lane@cs.rochester.edu>
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.
