QUANTUM COMPUTATION AND SHORS FACTORING ALGORITHM

Current technology is beginning to allow us to manipulate rather than just observe individual quantum phenomena. This opens up the possibili ty of exploiting quantum effects to perform computations beyond the sc ope of any classical computer. Recently Peter Shor discovered an effic ient algorithm for factoring whole numbers, which uses characteristica lly quantum effects. The algorithm illustrates the potential power of quantum computation, as there is no known efficient classical method f or solving this problem. The authors give an exposition of Shor's algo rithm together with an introduction to quantum computation and complex ity theory. They discuss experiments that may contribute to its practi cal implementation.