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".