ORACLE QUANTUM COMPUTING

被引：38

作者：

BERTHIAUME, A

BRASSARD, G

机构：

[1] Departement IRO, Universite de Montreal, Montreal, QC, H3C 3J7, C.P. 6128, succursale centre-ville

来源：

JOURNAL OF MODERN OPTICS | 1994年 / 41卷 / 12期

基金：

加拿大自然科学与工程研究理事会;

关键词：

D O I：

10.1080/09500349414552351

中图分类号：

O43 [光学];

学科分类号：

070207 ; 0803 ;

摘要：

Building on the work of Deutsch and Jozsa, we construct oracles relative to which (1) there is a decision problem that can be solved with certainty in worst-case polynomial time on the quantum computer, yet it cannot be solved classically in probabilistic expected polynomial time if errors are not tolerated, nor even in nondeterministic polynomial time, and (2) there is a decision problem that can be solved in exponential time on the quantum computer, which requires double exponential time on all but finitely many instances on any classical deterministic computer.

引用

页码：2521 / 2535

页数：15