On the Complexity of Finding Cycles in Periodic Functions Using the Quantum Turing Machine

スポンサーリンク

概要

• 論文の詳細を見る

• There are some results indicating that a quantum computer seems to be more powerful than ordinary computers. In fact, P.W. Shor showed that a quantum computer can find discrete logarithms and factor integers in polynomial time with bounded error probability. No polynomial time algorithms to find them using ordinary computers are known. In this paper, we show that the cycles in some kinds of periodic functions, e.g.,functions proposed as pseudo-random generators, can be found in polynomial time with bounded error probability on a quantum Turing machine. In general, it is known that ordinary computers take exponential time to find the cycles in periodic functions.

• 社団法人電子情報通信学会の論文
• 1996-05-25

著者

• MIHARA Takashi

  School of Information Science, Japan Advanced Institute of Science and Technology

• Mihara Takashi

  School Of Information Science Japan Advanced Institute Of Science And Technology

関連論文

• Are Measurements Effective on Quantum Computation?
• On the Complexity of Finding Cycles in Periodic Functions Using the Quantum Turing Machine

スポンサーリンク