First realization of scalable quantum factoring

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.

Based on Shor’s algorithm, a quantum computer can factorize numbers into prime factors notably faster than any classical computer could. However, to calculate the required numbers and operations, many quantum bits are required. And herein lies the crux – as most quantum computers can, for the moment, only work with a few quantum bits. In Innsbruck the physicists thus applied an idea from Alexei Kitaev to reduce the number of quantum bits. “If you want to factorize the number 15, you would usually require 12 quantum bits – with our implementation you only need 5 quantum bits,” states experimental physicist Thomas Monz, „This reduction is based on recycling one quantum bit along the calculation; and further improved as we make use of a quantum cache-bit to temporally store and later retrieve certain quantum information.“ Based on these techniques, the physicists managed to factorize the number 15 in an ion-trap based quantum computer.

The quantum computer starts its search with a randomly chosen number – a notable difference compared to previous realizations, as that number and certain simplifications are not specifically optimized here – and implements a number of gate operations on 4 quantum bits. The results are then stored, forwarded, extracted and recycled via a fifth quantum bit. “Here we had to implement a new cooling method that allows us to re-cool the ion-based quantum register along the computation,” explains Monz, furthermore outlining the advantage of Shor’s algorithm: “As far as we know, classical computers cannot factorize numbers efficiently because they have to do certain steps one after another. With a quantum computer, these steps, in some sense, are all running in parallel and thus notably faster.“

For more details see