multiplicative factor which does not help to change the exponential dependance between the size of the input and the execution time. Such change requires inventing new, better algorithms. Although quantum computation requires new quantum technology its real power lies in new quantum algorithms which allow to exploit quantum superposition that can contain an exponential number of different terms. Quantum computers can be programed in a qualitatively new way. For example, a quantum program can incorporate instructions such as `... and now take a superposition of all numbers from the previous operations...'; this instruction is meaningless for any classical data processing device but makes lots of sense to a quantum computer. As the result we can construct new algorithms for solving problems, some of which can turn difficult mathematical problems, such as factorisation, into easy ones! The story of quantum computation started as early as 1982, when the physicist Richard Feynman considered simulation of quantum-mechanical objects by other quantum systems[1]. However, the unusual power of quantum computation was not really anticipated untill the 1985 when David Deutsch of the University of Oxford published a crucial theoretical paper[2] in which he described a universal quantum computer. After the Deutsch paper, the hunt was on for something interesting for quantum computers to do. At the time all that could be found were a few rather contrived mathematical problems and the whole issue of quantum computation seemed little more than an academic curiosity. It all changed rather suddenly in 1994 when Peter Shor from AT&T's Bell Laboratories in New Jersey devised the first quantum algorithm that, in principle, can perform efficient factorisation[3].This became a `killer application' --- something very useful that only a quantum computer could do. Difficulty of factorisation underpins security of many common methods of encryption; for example, R...
