ON QUANTUM ALGORITHM FOR EXPTIME PROBLEM

Satoshi Iriyama, Makoto Ohya

Satoshi Iriyama, Makoto Ohya

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.

Satoshi Iriyama, Makoto Ohya

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.

Richard Cleve, ARTUR K. EKERT, Leah Henderson +2 more

CleveRichard, EkertArtur, HendersonLea +2 more