Efficient Quantum Algorithm for NPC and EXPTIME Problems
Satoshi Iriyama, M. Ohya, Andrei Yu. Khrennikov +3 more
We have studied a quantum algorithm for several years, and developed some applications for difficult problems, NPC problems and NP intermidiate problems. In order to discuss the computational complexity of quantum algorithm, we defined a generalized quantum Turing machine using a density operator on a Hilbert space and quantum channels on it. Since the properity of quantum channel, this mathematical model can describe not only unitary process of quantum algorithm but also measurement process and non‐linear dynamical process. Then we can calculate the computational complexity of quantum algorithm more regorously.In this paper, we review our results, and discuss why quantum algorithms are more effective than classical ones. Moreover, we propose a quantum algorotihm for EXPTIME problem.
AIP conference proceedings•Jan 1, 2011•0 citations