Quantum Computing: Readily Applicable Theory for A New Era

Essay by Robin Wilke

Before each year’s Joint Mathematics Meetings, the AMS and MAA each choose the hottest, most relevant topics out there and offer Short Courses on them, bringing in a panel of eight experts to educate the mathematicians in attendance about that topic. For 2009, the AMS chose “Quantum Computation and Quantum Information” (the MAA chose “Data Mining”). When one mathematician asked, “How many qubits are needed before a quantum computer can factor numbers large enough to be a threat to RSA?” Peter Shor responded, “Fifty or sixty.” The other panelists agreed.

D Wave, a private company in British Columbia, has already built a quantum computer using silver atoms as qubits. There are sixteen of them. They have not released information on how they’ve gotten the silver atoms to line up in the desired start states, how they protect the computation from contamination, or what other tests they’ve done to show that the quantum computer works, but they have released the information that this sixteen-qubit machine can solve Sudoku – and of course, can do it measurably faster than a classical computer.

A fifty-qubit machine would change many things. It would destroy the security of all bank accounts and Internet transactions. It would make the secrets of our government and other countries’ vulnerable, making a country’s military and economic strength less relevant in times of war. Forget nuclear bombs – the quantum computer will be the next great equalizer on the global scale.

How would a quantum computer do all of these things? It would use an algorithm for factoring integers called Shor’s Algorithm. It reduces the problem of factoring an integer N to a problem of computing the order of a random integer mod N. Pick a random integer a and find the gcd of N and a using the Euclidean Algorithm. If gcd(N, a) is not 1, then the gcd is a nontrivial factor of N, and we are done, but you’re probably not going to get that lucky. Now for the quantum part. Initialize your qubits in a superposition of Q states, where Q is a number between N ² and 2N ². Apply a quantum Fourier transform (the “faster Fourier transform” I showed in my presentation) to the input register you’ve just prepared. Then do some fun complex analysis to obtain a number r that has a high probability of being the order of a. Check that it is – if it isn’t, run the quantum subroutine again. If r is odd, or a^r/2 = -1 (mod N), then you need to pick a new a. Otherwise, gcd(a^r/2 ± 1, N) is a nontrivial factor of N. This algorithm runs in O((logN)³), which is polynomial time. By contrast, the fastest known classical factoring algorithm runs in O(e^{(logN)1/3(log(logN))2/3}).

Quantum computers can do more than just factor integers extremely fast. Quantum error correction is also far more efficient than classical error correction, because no copy of any information is required to be made (indeed, due to a result in quantum physics called the No-Cloning Theorem, no such copy is possible!). Instead of copying information, the state of one qubit can be encoded into an entangled state with multiple qubits.

The list of schools that recognize the extreme importance of quantum computers to the immediate future of the world as we know it by offering at least one class in quantum computing includes (but is certainly not limited to!) MIT, University of Waterloo, University of Chicago, Oxford, Cambridge, Stanford, Purdue, University of Bristol, University of Queensland, and University of Maryland. UVM computer science students will be totally unprepared for the era of quantum computing.