作者: Harumichi Nishimura
关键词: Quantum circuit 、 Non-deterministic Turing machine 、 Quantum 、 Time complexity 、 Combinatorics 、 Amplitude 、 Promise problem 、 Turing machine 、 Discrete mathematics 、 Quantum computer 、 Mathematics
摘要: 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.