Only rich nerds. They are fun to ride, but I can't understand the $5K+ price. I assumed Kamen was keeping the price high to make luxury-style profit, but a recent magazine profile presents him as a visionary out to change the world. Can it really cost $2K to make the gadget? 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. 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. 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. <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> RWG: For your cube root: Pick a large prime P, maybe 500 or 1000 digits, congruent to -1 (mod 15). This guarantees that cubing and ^5 are 1-1 maps, so cube/fifth roots exist and are unique. Working mod P, compute x as cbrt(stuff), and use the number recognizer to see if x is a rational function of 5^(1/3),2^(1/5),3^(1/5). That's about 150 terms; will NumRec handle that? You need terms for 5^a/3 * 2^b/5 * 3^c/5 and (same)*x. If NumRec balks, you might try using 150 different primes, and directly solving the matrix. Rich ________________________________________ From: math-fun-bounces@mailman.xmission.com [math-fun-bounces@mailman.xmission.com] On Behalf Of rwg@sdf.lonestar.org [rwg@sdf.lonestar.org] Sent: Friday, December 12, 2008 1:27 AM To: math-fun Cc: Tom Knight Subject: Re: [math-fun] Fast factoring ??
The Shor algorithm for quantum computing the factors of a composite number N relies on a physical trick to calculate r, the period of x^a mod N for 0<a<N-1, while doing the exponentiation mod N on a superposition of the possible a's. This step, and the fourier transform of the result are done on the superposition, leading to a fast algorithm for finding the period r, following a magic "collapse."
I attended a talk on Tuesday from Adi Akavia (former student of Shafi Goldwasser) in which she discussed the problem of finding (whp) large fourier coefficients of a function g(a) over a domain of size N while examining only polylog(N) of the values, pointing to her paper (FOCS 03) "Proving Hard-Core Predicates using List Decoding," Akavia, Goldwasser, Safra. In that paper they show a very clever algorithm for finding the set of large fourier coefficients efficiently.
Question of the day: Can these two ideas be put together to find a polynomial factoring algorithm?
Almost certainly I'm overlooking or misunderstanding some very fundamental thing, but I don't see what.
I was about to say that thanks to Berlekamp et seq., polynomial factoring is ridiculously easy compared to integer factoring. (With Kronecker's old algorithm, it used to be pretty much equivalent.) But factoring over algebraic coefficient fields seems another story. I just lost a Mathematica 7.0 that had gone 2.5 days on Factor[x^3-3^(3/5)+2^(1/5), Extension -> {5^(1/3),2^(1/5),3^(1/5)}] Has anybody quantum factored anything > 3*5 yet? rcs>And the codicil [to http://www.tweedledum.com/rwg/pizza.htm] provides a
wonderful segue like nerds play polo on? into series acceleration, and your mysterious irregular convergence of the pi = 4 arctan 1 series.
Good point. I added a warning and the AIM 304 url, http://dspace.mit.edu/handle/1721.1/6088?show=full --rwg Codicil = "little codex". _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Dec 12, 2008, at 1:35 PM, Schroeppel, Richard wrote:
<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>
RWG: For your cube root: Pick a large prime P, maybe 500 or 1000 digits, congruent to -1 (mod 15). This guarantees that cubing and ^5 are 1-1 maps, so cube/fifth roots exist and are unique. Working mod P, compute x as cbrt(stuff), and use the number recognizer to see if x is a rational function of 5^(1/3),2^(1/5),3^(1/5). That's about 150 terms; will NumRec handle that? You need terms for 5^a/3 * 2^b/5 * 3^c/5 and (same)*x. If NumRec balks, you might try using 150 different primes, and directly solving the matrix.
Rich
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.
RWG: For your cube root: Pick a large prime P, maybe 500 or 1000 digits, congruent to -1 (mod 15). This guarantees that cubing and ^5 are 1-1 maps, so cube/fifth roots exist and are unique. Working mod P, compute x as cbrt(stuff), and use the number recognizer to see if x is a rational function of 5^(1/3),2^(1/5),3^(1/5). That's about 150 terms; will NumRec handle that? You need terms for 5^a/3 * 2^b/5 * 3^c/5 and (same)*x. If NumRec balks, you might try using 150 different primes, and directly solving the matrix.
Rich
Rich, note that throwing in a factor of 25 reduces many days to Timing[Factor[x^3-(25*3^(3/5)-25*2^(1/5)),Extension->{2,3}^(1/5)]] {0.297, (2^(2/5) + 3^(1/5) + 2^(3/5) 3^(2/5) - 2^(1/5) 3^(3/5) - x) (5 2^(4/5) - 5 2^(2/5) 3^(1/5) - 5 3^(2/5) + (-2^(2/5) - 3^(1/5) - 2^(3/5) 3^(2/5) + 2^(1/5) 3^(3/5)) x - x^2)} < 1/3 sec. ! ? linrel is fast enough for a few dozen, but has a bug where it gets lost around 15 or so. Mma's LLL can go a few hundred, but I can guess enough structure to In[64]:= Times @@ # & /@ CP[rutset[27/2, 15], rutset[5, 3]] Out[64]:= {1, 5^(1/3), 5^(2/3), 3^(1/5)/2^(1/15), (3^(1/5) 5^(1/3))/2^(1/15), (3^(1/5) 5^(2/3))/2^(1/15), 3^(2/5)/2^(2/15), (3^(2/5) 5^(1/3))/2^(2/15), (3^(2/5) 5^(2/3))/2^(2/15),...} (CP:= CartesianProduct.) Then with LR := linrelized LLL, In[85]:= Block[{L = Prepend[%64, ((27/2)^(1/5) - 1)^(1/3)], M}, M = LR[L, LeafCount[%64]/4]; Print[L.Rest[M[[1]]]]; M][[{1, 2, 3}]] (9*3^(1/5)*5^(1/3))/2^(1/15)+9*2^(8/15)*3^(2/5)*5^(1/3)-9*2^(2/15)*3^(3/5)*5^(1/3) +9*10^(1/3)-45*(-1+3^(3/5)/2^(1/5))^(1/3) Out[85]:= {{-8, -45, 0, 0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0}, {-787, 80, 2599, 1018, 289, 1325, -548, 119, -1386, -77, 2190, -780, -273, -967, -234, -646, 1421, -179, 761, -525, -874, -181, -1059, 151, -657, 1491, -503, 435, 624, -222, 556, -1089, 300, 1512, -2820, 928, 1539, 1864, 217, -737, -1152, -128, -1075, 756, 67, -253, 4},...} alternatively In[89]:=Block[{L = Prepend[Times @@ # & /@ CP[rutset[5, 3], rutset[18, 15]], (1 - 18^(1/5)/3)^(1/3)], M}, M = LR[L, LeafCount[L]/4]; Print[L.Rest[M[[1]]]]; M][[{1, 2, 3}]] 3*5^(1/3)+3*2^(3/5)*3^(1/5)*5^(1/3)-3*2^(1/5)*3^(2/5)*5^(1/3)+2^(2/5)*3^(4/5)*5^(1/3) -15*(1-2^(1/5)/3^(3/5))^(1/3) Out[89]:= {{-1, -15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, -3, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {-3918, -305, 4558, -2943, 2084, 410, -231, 3243, 1724, -1800, 3734, -1203, 973, 3671, -1341, 687, 3825, -2768, -1771, -2741, 438, 1370, -1675, -2849, -177, 2675, 4046, -1408, 1185, 90, -3069, 1280, 1325, 1147, -1339, -2624, -38, -2374, 1633, -1050, 636, -1427, -513, -1876, -395, 25, 0},...} alternatively In[90]:=Block[{L = Prepend[Times @@ # & /@ CP[rutset[5, 3], rutset[2/27, 15]], (1 - 18^(1/5)/3)^(1/3)], M}, M = LR[L, LeafCount[L]/4]; Print[L.Rest[M[[1]]]]; M][[{1, 2, 3}]] -5^(1/3)-(2^(2/5) 5^(1/3))/3^(1/5)-2^(3/5) 3^(1/5) 5^(1/3)+2^(1/5) 3^(2/5) 5^(1/3) +5 (1-2^(1/5)/3^(3/5))^(1/3) Out[90]:= {{1, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 3, 0, 0, -3, 0, 0, -9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {4926, -3156, 1253, 6785, -6444, -576, -7461, 619, 3581, -972, 2114, -2847, 1155, 6019, -6505, 5731, 1870, -9425, 6052, -2433, 7267, -1805, -4650, -1785, 5949, 9199, 2865, 2969, -750, 8537, 5209, -8450, -2160, -209, 7109, -2063, 1370, -11382, -1528, 6248, 3774, 696, 1667, 927, -81, 0, 0},...} so it looks pretty good for roots of binomials, at least. But I have been running a few days of sequential search with zero new discoveries. --Bill PERIDIASTOLE DEPILATORIES
participants (3)
-
rwg＠sdf.lonestar.org -
Schroeppel, Richard -
Tom Knight