New Generation Computing, 21(2003)329-337
Ohmsha, Ltd. and Springer-Verlag

Efficient Algorithms for NMR Quantum Computers with Small Qubits

Noboru KUNIHIRO
The University of Electro-communications
1-5-1 Chofugaoka, Chofu, Tokyo 182-8585 Japan*
kunihiro@ice.uec.ac.jp

Shigeru YAMASHITA
Nara Institute of Science and Technology
8916-5 Takayama-cho, Ikoma, Nara 631-0101 Japan
ger@is.aist-nara.ac.jp

Received 31 August 2002
Revised manuscript received 30 April 2003

Abstract

The security of the RSA cryptosystems is based on the difficulty of factoring a large composite integer. In 1994, Shor showed that factoring a large composite is executable in polynomial time if we use a quantum Turing machine. Since this algorithm is complicated, straightforward implementations seem impractical judging from current technologies. In this paper, we propose simple and efficient algorithms for factoring and discrete logarithm problem based on NMR quantum computers. Our algorithms are easier to implement if we consider NMR quantum computers with small qubits.

Keywords: Factoring Problem, Discrete Logarithm Problem, NMR Quantum Computers, Counting Problem, Polynomial Time Algorithm.

(Footnote)
* A part of this work was done while both authors were with NTT Communication Science Laboratories

[Back]