Абстрактный

COMPARATIVE ANALYSIS ON TURING MACHINE AND QUANTUM TURING MACHINE

Tirtharaj Dash and Tanistha Nayak

Now-a-days every computing device is based on the Turing Machine. It is known that classical physics is sufficient to explain macroscopic phenomena, but is not to explain microscopic phenomena like the interference of electrons. In these days, speed-up and down-sizing of computing devices have been carried out using quantum physical effects; however, principles of computation on these devices are also based on classical physics. This paper tries to analyze mathematically a possibility that the Universal Quantum Turing Machine (UQTM) is able to compute faster than any other classical models of computation. Basically we focused on comparative study on computation power of Universal Turing Machine (UTM) and UQTM. Namely, in the equal, we tried to show that the UQTM can solve any NP-complete problem in polynomial time. The result analysis showed that UQTM is faster for any computation.