On Quantum Computation with Some Restricted Amplitudes

作者: Harumichi Nishimura

DOI: 10.1007/3-540-45841-7_25

关键词: Quantum circuitNon-deterministic Turing machineQuantumTime complexityCombinatoricsAmplitudePromise problemTuring machineDiscrete mathematicsQuantum computerMathematics

摘要: In this paper we explore the power of quantum computers with restricted amplitudes. Adleman, DeMarrais and Huang showed that Turing machines (QTMs) amplitudes from A = {0, ± 3/5, 4/5, 1} are equivalent to ones polynomial-time computable as implementing bounded-error polynomial time algorithms. We show QTMs is deterministic exact Extending result, it shown rational biased 'quantum coins' classical computers. also viewpoint zero-error algorithms not more useful than B 1/?2, but sufficient for factoring problem set taken by QTMs.

参考文章(29)
Tomoyuki Yamakami, Andrew C Yao, None, NQPC= co-C=P Information Processing Letters. ,vol. 71, pp. 63- 69 ,(1999) , 10.1016/S0020-0190(99)00084-8
Isaac L. Chuang, Michael A. Nielsen, Quantum Computation and Quantum Information ,(2000)
Harumichi Nishimura, Masanao Ozawa, Computational complexity of uniform quantum circuit families and quantum Turing machines Theoretical Computer Science. ,vol. 276, pp. 147- 181 ,(2002) , 10.1016/S0304-3975(01)00111-6
Lance Fortnow, John Rogers, Complexity Limitations on Quantum Computation Journal of Computer and System Sciences. ,vol. 59, pp. 240- 252 ,(1999) , 10.1006/JCSS.1999.1651
John Preskill, RELIABLE QUANTUM COMPUTERS Proceedings of The Royal Society A: Mathematical, Physical and Engineering Sciences. ,vol. 454, pp. 385- 410 ,(1998) , 10.1098/RSPA.1998.0167
Charles H. Bennett, Ethan Bernstein, Gilles Brassard, Umesh Vazirani, Strengths and Weaknesses of Quantum Computing SIAM Journal on Computing. ,vol. 26, pp. 1510- 1523 ,(1997) , 10.1137/S0097539796300933
Ker-I. Ko, Harvey Friedman, Computational complexity of real functions Theoretical Computer Science. ,vol. 20, pp. 323- 352 ,(1982) , 10.1016/S0304-3975(82)80003-0
Ethan Joseph Bernstein, Quantum Complexity Theory SIAM Journal on Computing. ,vol. 26, pp. 1411- 1473 ,(1997) , 10.1137/S0097539796300921
Klaus W. Wagner, The complexity of combinatorial problems with succinct input representation Acta Informatica. ,vol. 23, pp. 325- 356 ,(1986) , 10.1007/BF00289117
L. Adleman, M. Huang, Recognizing primes in random polynomial time symposium on the theory of computing. pp. 462- 469 ,(1987) , 10.1145/28395.28445