On Dec 12, 2008, at 1:35 PM, Schroeppel, Richard wrote:
Wrt quantum factoring 15, no further progress. I keep hoping to see 21. The problem with 15 is that it's too easy. It's a Mersenne form, 2^4-1, which makes the modular reduction trivial. There are a lot of other simplifications for this case, including phi(15) = 4, and multiplication by 2 or 4 is accomplished by rotating the bits. I regarded the original Nature paper as a cheat, since the N=15 case avoids most of the problems that come up in factoring "random" numbers. A more charitable interpretation is that they picked an easy example to start with. It must have taken a lot of work to get their 7-qubit molecule working.
The NMR work is definitely a cheat, since it is provably not extensible to significantly larger systems.
Subsequent progress has been lateral: The demo has been repeated with several other underlying quantum systems different from the original NMR approach. But I haven't seen anyone doing complex boolean functions like Majority(X,Y,Z), needed to compute carry bits in any non-trival arithmetic. Any logic system needs a way to carry results through several levels of gates, without the logic levels decaying to indistinguishability. The quantum systems haven't shown this capability yet. It doesn't seem impossible from the theory. Maybe next year.
Actually, this is a major fundamental problem. Errors imply irreversible behavior, and decoherence. You can't clean up quantum signals with good gates, as you can with ordinary logic signals. You can push the errors into places you don't care about, which is what the quantum error correcting codes try to do (with very low efficiency).
I couldn't get through the Akavia-Goldwasser-Safra paper. (Have you ever started skiing down a Green slope, and found it gradually transitioning to Black?) But AGS use RSA and discrete logs as examples of (apparently) hard problems, and I doubt they would overlook any applicability of their results to classical factoring.
Just my thought, but we should check.
<speculation> Maybe some undiscovered physical principle limits our ability to exploit quantum parallelism for computation. My wild guess is that each independent entangled state requires its own kT of energy in the system. This would let us build toy quantum computers to validate the physics, with up to ~2^80 states (a mole), but prevent us from going after the goal problems with 2^1000 states. <end speculation>.
This is consistent with my speculations from quite a while back. I too think it likely that there is a "gotcha" preventing large scale quantum calculation significantly more efficient than classical. A large part of my interest in the factoring question is the apparent contradiction in the (relative) ease of Shor's algorithm and classical solutions.