Quantum zero-error algorithms cannot be composed

被引：1
作者：
Buhrman, H
de Wolf, R
机构：
[1] CWI, NL-1098 SJ Amsterdam, Netherlands
[2] Univ Amsterdam, NL-1098 SJ Amsterdam, Netherlands
来源：
INFORMATION PROCESSING LETTERS | 2003年 / 87卷 / 02期
关键词：
analysis of algorithms; quantum computing; zero-error computation;
D O I：
10.1016/S0020-0190(03)00254-0
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We exhibit two black-box problems, both of which have an efficient quantum algorithm with zero-error, yet whose composition does not have an efficient quantum algorithm with zero-error. This shows that quantum zero-error algorithms cannot be composed. In oracle terms, we give a relativized world where ZQP(ZQP) not equal ZQP, while classically we always have ZPP(ZPP) = ZPP. (C) 2003 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：79 / 84
页数：6
相关论文
共 12 条
[1]   Quantum computability [J].
Adleman, LM ;
Demarrais, J ;
Huang, MDA .
SIAM JOURNAL ON COMPUTING, 1997, 26 (05) :1524-1540
[2]  
[Anonymous], 2009, Quantum computation and quantum information, DOI DOI 10.1119/1.1463744
[3]   Quantum lower bounds by polynomials [J].
Beals, R ;
Buhrman, H ;
Cleve, R ;
Mosca, M ;
de Wolf, R .
39TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1998, :352-361
[4]   Complexity measures and decision tree complexity: a survey [J].
Buhrman, H ;
de Wolf, R .
THEORETICAL COMPUTER SCIENCE, 2002, 288 (01) :21-43
[5]   Nondeterministic quantum query and communication complexities [J].
De Wolf, R .
SIAM JOURNAL ON COMPUTING, 2003, 32 (03) :681-699
[6]   Characterization of non-deterministic quantum query and quantum communication complexity [J].
de Wolf, R .
15TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, 2000, :271-278
[7]   RAPID SOLUTION OF PROBLEMS BY QUANTUM COMPUTATION [J].
DEUTSCH, D ;
JOZSA, R .
PROCEEDINGS OF THE ROYAL SOCIETY OF LONDON SERIES A-MATHEMATICAL PHYSICAL AND ENGINEERING SCIENCES, 1992, 439 (1907) :553-558
[8]  
FENNER S, 1998, P 6 IT C THEOR COMP, P241
[9]  
HOYER P, 2002, LECT NOTES COMPUTER, V2285, P299
[10]  
Kitaev A. Y., 2002, Classical and quantum computation
12