<テクニカルレポート>
Another Quantum Turing Machines

作成者
本文言語
出版者
発行日
雑誌名
出版タイプ
アクセス権
概要 The quantum Turing machines by Bernstein & Vazirani are based on vectors and matrices as in quantum mechanics, so that it is difficult to make clear difference between the quantum Turing machines and ...the usual probabilistic Turing machines. This paper gives another formulation which can make difference clear. We consider that the superposition of configurations, a basic concept of the quantum Turing machines, should also be applied to the probabilistic Turing machines. From this viewpoint we first give a new definition of the probabilistic Turing machines. Then we define the quantum Turing machine as an extension of the probabilistic Turing machine. We show the relationship between Bernstein & Vazirani's definition and ours. In both types of the quantum Turing machines there still remains another difficulty that the machines are required to be time-bounded in order for users to get results explicitly from the machines. We overcome this difficulty by modifying our quantum Turing machines, and show that our new machines can solve the satisfiability and the validity problems in polynomial time.続きを見る

本文情報を非表示

rifis-tr-114 pdf 804 KB 61  

詳細

レコードID
査読有無
関連情報
タイプ
登録日 2009.04.22
更新日 2017.01.20