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 difﬁculty 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 signiﬁcant part of the reduction is to replace the ﬁrst “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 beneﬁted from this artiﬁce. 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.
Brian Wang is a Futurist Thought Leader and a popular Science blogger with 1 million readers per month. His blog Nextbigfuture.com is ranked #1 Science News Blog. It covers many disruptive technology and trends including Space, Robotics, Artificial Intelligence, Medicine, Anti-aging Biotechnology, and Nanotechnology.
Known for identifying cutting edge technologies, he is currently a Co-Founder of a startup and fundraiser for high potential early-stage companies. He is the Head of Research for Allocations for deep technology investments and an Angel Investor at Space Angels.
A frequent speaker at corporations, he has been a TEDx speaker, a Singularity University speaker and guest at numerous interviews for radio and podcasts. He is open to public speaking and advising engagements.