Quantum Computing And Shor's Factoring Algorithm

Introduction Information processing (computing) is dynamical evolution of a highly organized physical system produced by technology (computer) or nature (brain). Initial state of this system is (determined by) its input, final state is the output. Physics describes nature in two complementary modes: classical and quantum. Up to the nineties, the basic mathematical models of computing, Turing machines, were classical objects, although the first suggestions to study quantum models date back at least to 1980. Theoretical quantum computing entered its modern stage in 1994, when P. Shor ([Sh]) devised the first quantum algorithm showing that prime factorization can be done on quantum computers in polynomial time, that is, considerably faster than by any known classical algorithm. (P. Shor's work was inspired by the earlier work [Si] of D. Simon). Shor's paper gave a new boost to the subject. Another beautiful result due to L. Grover ([Gro]) is that the quantum search among N<