David Radcliffe on Nostr: I'm still trying to fully understand Shor's quantum algorithm for factoring integers, ...
I'm still trying to fully understand Shor's quantum algorithm for factoring integers, and why the inverse QFT is needed.
Here's my thinking. If (a,N)=1 then there is a unitary U, defined such that U|x> = |ax> for (x,N)=1 and U|x| = |x> otherwise. The eigenvalues of U are the d-th roots of 1, where d is the multiplicative order of a modulo N. If we could compute a nontrivial eigenvalue of U, then we could use it to compute d, and then factor N.
So, my naive question is this. What are the obstacles to computing the eigenvalues of U directly? (I'm not even sure what "directly" would mean in the context of a quantum algorithm.)
Here's my thinking. If (a,N)=1 then there is a unitary U, defined such that U|x> = |ax> for (x,N)=1 and U|x| = |x> otherwise. The eigenvalues of U are the d-th roots of 1, where d is the multiplicative order of a modulo N. If we could compute a nontrivial eigenvalue of U, then we could use it to compute d, and then factor N.
So, my naive question is this. What are the obstacles to computing the eigenvalues of U directly? (I'm not even sure what "directly" would mean in the context of a quantum algorithm.)