Factoring Algorithms Based on NMR Quantum Computers (Computer Algebra : Algorithms, Implementations and Applications)
Noboru Kunihiro, Shigeru Yamashita
No polynomial time algorithms have been proposed for the factoring and discrete logarithm problems.However, Shor showed that these problems can be solved by aquantum Turing machine in 1994.Sev- eral devices have been proposed toward the realization of quantum computers.Among them, the NMR quantum computer seems to be the nearest to the target goal.Since the NMR quantum computer has different features from ordinary ones, we cannot directly implement Shor's algorithms.In this paper, we propose new simple algorithms that work on NMR quantum computers to solve the factoring and discrete logarithm problems.
数理解析研究所講究録•Nov 1, 2002•1 citation