Math
Fourier, eine Periode und ein Faktor
Vergleichen Sie eine Spitze mit ihrem Nachbarn. Dann messen: Eine Spitze liefert einen Nennerkandidaten, keinen garantierten Faktor. Ideales CPU-Modell, 12 Qubits, ohne Rauschen oder Hardware. Für N=21 gilt Q=128 < N²: geringere Präzision. Nur teilerfremde Basen; sonst liefert ggT(a,N) bereits einen Faktor.
Was passiert
Vergleichen Sie eine Spitze mit ihrem Nachbarn. Dann messen: Eine Spitze liefert einen Nennerkandidaten, keinen garantierten Faktor.
Gleichungen des Moduls
Gleichungen 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 im Zweig z) P(y gegeben 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; vor der Faktorextraktion a^d mod N = 1 prüfen d gerade: h=a^(d/2) mod N; g−=gcd(h−1,N), g+=gcd(h+1,N) nur 1<g−,g+<N und g−g+=N akzeptieren; h=±1 mod N ist trivial N=15: t=8, work=4; N=21: t=7, work=5, Q=128<N² (verringerte Genauigkeit) idealer numerischer Zustandsvektor, 12 Qubits; das modulare Orakel ist eine Basispermutation Stichprobe frequency=count/n; SE=sqrt(P(1−P)/n), n>0
