Cryptography Watch

Researchers have demonstrated Shor’s Quantum Factoring Algorithm experimentally on a 4bit number[1]. Researchers were able to use the algorithm to determine the factors of the number 15, 3 and 5.

[1] Vandersypen, L. M. K., Steffen, M., Breyta, G., Yannoni, C. S., Sherwood, M. H., Chuang, I. L. Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance, Nature 414, 883-887 (2001).

Abstract
The number of steps any classical computer requires in order to find
the prime factors of an l-digit integer N increases exponentially with l, at
least using algorithms known at present. Factoring large integers is therefore
conjectured to be intractable classically, an observation underlying the security
of widely used cryptographic codes. Quantum computers, however, could factor
integers in only polynomial time, using Shor’s quantum factoring algorithm.
Although important for the study of quantum computers, experimental
demonstration of this algorithm has proved elusive. Here we report an
implementation of the simplest instance of Shor’s algorithm: factorization
of N = 15 (whose prime factors are 3 and 5). We use seven spin-1/2
nuclei in a molecule as quantum bits, which can be manipulated with
room temperature liquid-state nuclear magnetic resonance techniques.
This method of using nuclei to store quantum information is in principle
scalable to systems containing many quantum bits, but such scalability
is not implied by the present work. The significance of our work lies in
the demonstration of experimental and theoretical techniques for precise
control and modeling of complex quantum computers. In particular, we
present a simple, parameter-free but predictive model of decoherence
effects in our system.