Shor’s algorithm is likely the most famous quantum algorithm. He solves a centuries-old problem, namely the factoring of numbers into primes. Physicists led by Rainer Blatt joined forces with scientists at MIT, led by Isaac Chuang, to efficiently implement Shor’s algorithm in an ion-trap based quantum computer. Here their approach can be directly applied to larger numbers.
Every natural number can be factored into prime numbers. For small numbers such a prime number decomposition is a simple brainteaser; for large numbers it is extremely challenging. This problem actually is the basis for many encryption methods such as RSA encoding. As solving such a factoring problem is challenging for classical computers, such encryption schemes to date are considered secure.
In 1994 the American scientist Peter Shor derived an algorithm that, based on a quantum computer, can efficiently deduce the prime factors of very large numbers, and overcome classical limitations. In the last 15 years Shor’s algorithm has been implemented several times in various laboratories – however always based on prior knowledge about the expected results.
Physicists at the Institute for Experimental Physics at the University of Innsbruck, the Institute of Quantum Optics and Quantum Information in Innsbruck, together with physicists at MIT, have now – for the first time – realized Shor’s algorithm without use of any prior knowledge of the expected results. Their particular implementation was based on efficient methods that can be directly extended to larger numbers.