Almost-Everywhere Superiority for Quantum Computing

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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.
16 pages

Keywords

Quantum Physics, Computational Complexity

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/94265

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/quant-ph/9910033
 http://arxiv.org/abs/quant-ph/9910033

Collections

arXiv