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