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.