Algoritm de factorizare Shor

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

Algoritmul de factorizare Shor este un algoritm conceput de Peter Shor în 1994 pentru a rezolva problema factorizării numerelor întregi în numere prime .

Pe un computer cuantic acest algoritm are o complexitate de calcul polinomială sau, mai corect, BQP ( Bounded error Quantum Polynomial time ): factorii se găsesc cu o marjă de eroare arbitrar mică în lungimea întregului număr de intrare.

Reducerea problemei

Este numărul de factorizat. Problema factorizării sale în factori primi poate fi redusă la un maxim de log (n) probleme de factorizare binară în numere care nu sunt neapărat prime.

Se alege un număr astfel încât o acoperim cu : cel mai mare divizor comun dintre cei doi este deci 1.

Este definită o secvență pe numere întregi pozitive :

astfel încât unul dintre termenii secvenței este egal cu unul și următorii sunt repetați periodic, adică

pentru numere întregi și pentru o perioadă dată .

este cel mai mic întreg pentru care , și se numește ordine multiplicativă a modul . De asemenea, este egal cu perioada succesiunii.

De sine este chiar, cel puțin un factor de se află între cele două numere

intr-adevar

De exemplu, cu n = 143 și alegând a = 21, ordinea este 4 ( ).
Merita .
MCD între cei doi termeni ed factorii principali sunt candidații:

care sunt de fapt factorii , 11 și 13.

Calculul comenzii

Găsirea ordinii este o problemă pentru care nu se cunoaște o soluție deterministă eficientă cu un computer clasic. Introducerea lui Peter Shor este cea a unui algoritm cuantic capabil să ofere ordine în timp polinomial în dimensiunea lui . Algoritmul folosește codificarea și extragerea informațiilor (prin transformarea cuantică Fourier ) din fazele relative dintre stările cuantice ( qubits ), o proprietate care nu are echivalent clasic.

Există mai multe versiuni ale algoritmului. Cel prezentat de Shor în 1994 este următorul:

  1. Să luăm în considerare două registre, de q și m qubit . Primul este inițializat la reprezentarea binară a , sau . Al doilea a , reprezentat pe m cifre ca .
  2. Pe primul registru este operată o poartă cu qubit aq Hadamard . Primul registru se află astfel într-o stare (normalizările sunt omise). Se poate observa că această stare este suprapunerea uniformă a tuturor stărilor care codifică prin numere .
  3. Primul registru controlează acțiunea pe al doilea. Operatorul este definit ca .
    Operatorul este o r-a rădăcină a identității, unde r este ordinea multiplicativă a unui modul n, prin urmare are valori proprii de tip pentru . Se poate arăta că suprapunerea omogenă a statelor proprii este exact starea . Au acțiunea de la starea primului registru, suprapunându-se pe toate se asigură că etapele apar în starea finală.
  4. Transformata cuantică Fourier extrage aceste faze și le face măsurabile pe bază de calcul pe primul registru.

Diferite repetări ale algoritmului oferă diverse estimări ale , din care poate fi recunoscut . The măsurată la fiecare execuție este aleatorie, dintre toate cele mai mici de : de la sine poate fi înșelătoare (de exemplu dacă împarte r).

Eficienţă

Algoritmul prezentat are complexitate de ordine . Partea rămasă a factorizării, exprimată mai sus, este comună algoritmilor clasici și este deja eficientă: accelerarea pe care algoritmul Shor o dă problemei calculării ordinii, prin urmare, face ca întregul algoritm de factorizare să fie eficient.

Cu toate acestea, algoritmul nu este determinist și are o probabilitate de succes mai mică de 1: se poate repeta încă iterația pentru a reduce pragul de eroare.

Implementare

Nu există nicio mașină cuantică scalabilă care să implementeze versiunea descrisă a algoritmului Shor. Versiunile compilate, adică reduse pentru cazuri specifice, au fost deja efectuate: de exemplu pe sisteme optice liniare, unde qubitii sunt codați în polarizarea fotonilor .

Bibliografie

  • ( EN ) Peter Shor, Algorithms for quantum computation: Discrete log and factoring , în Proceedings of the 35th Annual Symposium on the Foundations of Computer Science , Santa Fe, IEEE Computer Society Press, noiembrie 1994, pp. 124-134.
  • ( EN ) Phillip Kaye, Raymond Laflamme, Michele Mosca, Finding-Orders , în An introduction to quantum computing , Oxford, Oxford University Press, 2007, ISBN 978-0-19-857049-3 .

Elemente conexe