Compiling Shor’s Algorithm to enable arbitrarily large numbers to be factored using constant-sized quantum circuit like factoring a 20000 bit number using two Qubits

Arxiv – Pretending to factor large numbers on a quantum computer – Shor’s algorithm for factoring in polynomial time on a quantum computer gives an enormous advantage over all known classical factoring algorithm. We demonstrate how to factor products of large prime numbers using a compiled version of Shor’s quantum factoring algorithm. Our technique can factor all products of p; q such that p; q are unequal primes greater than two, runs in constant time, and requires only two coherent qubits. This illustrates that the correct measure of difficulty when implementing Shor’s algorithm is not the size of number factored, but the length of the period found.

Regular Shor’s algorithm needs roughly 3 log N qubits.

Qubit Recycling version of Shor’s Algorithm reduces qubits down to exactly 2 + 3/(2 log N qubits). A significant part of the reduction is to replace the first “x” register with a single qubit. This was shown to be possible and uses the fact that the bits of the quantum Fourier transform can be read out one at a time . The use of this semi-classical Fourier transform has become known as qubit recycling.

Compiled version using 2 qubits. The circuit for the fully-compiled Shor’s algorithm. The modular exponentiation is the single controlled-NOT, and the quantum Fourier transform is a Hadamard gate.

The IBM researchers will be performing experiments data using two superconducting transmon qubits.

The second column is the qubit recycling which needs about 1 qubit for every two digits. I believe the authors are saying the compiled version is not fully valid.

This should not be considered a serious demonstration of Shor’s algorithm. It does, however, illustrate the danger in “compiled” demonstrations of Shor’s algorithm. To varying degrees, all previous factorization experiments have benefited from this artifice. While there is no objection to having a classical compiler help design a quantum circuit (indeed, probably all quantum computers will function in this way), it is not legitimate for a compiler to know the answer to the problem being solved. To even call such a procedure compilation is an abuse of language.

As the cases of RSA-768 and N-20000 suggest, very large numbers can be trivially factored if we were to allow this. For this reason we stress that a factorization experiment should be judged not by the size of the number factored but by the size of the period found. Current experiments ought to be viewed instead as technology demonstrations, showing that we can manipulate small numbers of qubits. For instance, it was shown that intentionally added decoherence reduced the contrast in the data, a hallmark of a quantum-coherent process. All the referenced experiments are important tiny steps in the direction of building a quantum computer, but actually running algorithms on such tiny experiments is a somewhat frivolous endeavor.

If you liked this article, please give it a quick review on ycombinator or StumbleUpon. Thanks