A quantum Algorithm for the Moebius Function

We give an efficient quantum algorithm for the Moebius function from the natural numbers to {-1,0,1}. The cost of the algorithm is asymptotically quadratic in log n and does not require the computation of the prime factorization of n as an intermediate step.