Algorisme de Shor: diferència entre les revisions

 

=== Part quàntica: subprograma per trobar el període ===

 

Els circuits quàntics utilitzats per a aquest algorisme estan dissenyats especialment per a cada ''N'' i per a cada ''a'' aleatòria utilitzats a ''f''(''x'') = ''a''^''x'' mod ''N''. Donat un ''N'', trobeu ''Q'' = 2^''q'' tal que <math>N^2 \le Q < 2N^2</math>, cosa que implica <math>Q/r > N</math>. Els registres [[qubit]] d'entrada i sortida han de contenir superposicions dels valors entre 0 i ''Q'' − 1, i per tant tenen ''q'' qubits cadascun. Si s'utilitza el que semblaria que fos el doble de qubits necessaris, es garanteix que hi ha com a mínim ''N'' ''x'' diferents que produeixen la mateixa ''f''(''x''), també quan el període ''r'' s'acosta a ''N''/2.