Math
Fourier, un periodo e un fattore
Confronta un picco con il suo vicino, poi misura: il picco suggerisce un denominatore, non un fattore garantito. Modello CPU ideale, 12 qubit, senza rumore né dispositivo reale. Per N=21, Q=128 < N²: precisione ridotta. Basi coprime con N; altrimenti MCD(a,N) dà già un fattore.
Cosa succede
Confronta un picco con il suo vicino, poi misura: il picco suggerisce un denominatore, non un fattore garantito.
Equazioni del modulo
Equazioni Q = 2^t; |ψ⟩ = Q^(-1/2) Σ_(x=0)^(Q−1) |x⟩|a^x mod N⟩ S_z(y) = Σ_(x: a^x mod N=z) exp(2πixy/Q); m_z = count(x nel ramo z) P(y dato z) = |S_z(y)|²/(Q m_z); P(z)=m_z/Q P(y) = Σ_z |S_z(y)|²/Q²; Σ_y P(y)=1 y/Q ≈ p/d, 1 ≤ d < N; verificare a^d mod N = 1 prima di estrarre il fattore d pari: h=a^(d/2) mod N; g−=gcd(h−1,N), g+=gcd(h+1,N) accettare solo 1<g−,g+<N e g−g+=N; h=±1 mod N è banale N=15: t=8, work=4; N=21: t=7, work=5, Q=128<N² (precisione ridotta) vettore di stato numerico ideale, 12 qubit; l'oracolo modulare è una permutazione della base frequenza del campione: frequency=count/n; SE=sqrt(P(1−P)/n), n>0
