Algoritm cuantic

Un algoritm cuantic  este un algoritm proiectat să ruleze pe un computer cuantic .

Principii de bază

Un algoritm cuantic este un algoritm clasic care specifică o secvență de operații unitare (porți sau porți) cu o indicație a căror qubiți trebuie să fie efectuate. Un algoritm cuantic este specificat fie sub forma unei descrieri verbale a unor astfel de comenzi, fie prin intermediul notării grafice a acestora sub forma unui sistem de porți (matrice de porți cuantice).

Rezultatul algoritmului cuantic este probabilistic [1] . Datorită unei mici creșteri a numărului de operații în algoritm, se poate aduce în mod arbitrar probabilitatea de a obține rezultatul corect la unu.

Seturile de probleme care pot fi rezolvate pe un calculator cuantic și pe unul clasic coincid. Astfel, un computer cuantic nu crește numărul de probleme rezolvabile din punct de vedere algoritmic. Scopul utilizării unui computer cuantic este că poate rezolva unele probleme mult mai rapid decât oricare dintre cele clasice. Pentru a face acest lucru, algoritmul cuantic trebuie să genereze și să folosească stări cuantice încurcate în timpul calculului (a se vedea Suprapunerea cuantică și Entanglementul cuantic ).

Orice problemă rezolvată printr-un algoritm cuantic poate fi rezolvată și de un computer clasic prin calcularea directă a matricilor unitare de dimensiune exponențială, obținându-se o formă explicită de stări cuantice. În special, problemele care sunt de nerezolvat pe computerele clasice (cum ar fi problema opririi ) rămân de nerezolvat și pe computerele cuantice. Dar o astfel de simulare directă necesită timp exponențial și, prin urmare, devine posibil, folosind paralelismul cuantic, accelerarea unor algoritmi clasici pe un computer cuantic [2] .

Accelerația pe un computer cuantic nu este legată de viteza de ceas a procesorului. Se bazează pe paralelismul cuantic. Un pas de calcul cuantic lucrează mult mai mult decât un pas de calcul clasic. Cu toate acestea, ar fi o greșeală să echivalăm calculul cuantic cu calculul clasic paralelizat. De exemplu, un computer cuantic nu poate rezolva problema de enumerare mai repede decât unde  este timpul de rulare al unui algoritm de enumerare clasic determinist (vezi [3] ), în timp ce un algoritm clasic nedeterminist o rezolvă în timp . Dar un algoritm clasic nedeterminist necesită o resursă de memorie exponențială, adică nu este fezabil fizic, în timp ce un algoritm cuantic nu contrazice legile cunoscute ale naturii.

Calculul cuantic este un proces de un tip special. Utilizează o resursă fizică specială: stările încurcate cuantice , care permite în unele cazuri obținerea de câștiguri uimitoare în timp. Astfel de cazuri se numesc accelerație cuantică a calculului clasic.

Cazurile de accelerare cuantică, pe fondul masei generale a algoritmilor clasici, sunt foarte rare (vezi [4] ). Cu toate acestea, acest lucru nu reduce importanța fundamentală a calculului cuantic, deoarece acestea sunt capabile să accelereze în mod fundamental execuția sarcinilor de forță brută.

Scheme de accelerare cuantică de bază

Principalul tip de probleme care sunt accelerate de algoritmii cuantici sunt problemele de forță brută. Ele pot fi împărțite în 2 grupe principale:

  1. Probleme de modelare a dinamicii sistemelor complexe (ideea originală a lui Feynman) și
  2. Sarcini matematice care se rezumă la enumerarea opțiunilor:
    1. Cazul de enumerare generală: schema lui Grover și variantele acesteia, precum și
    2. Probleme de căutare a perioadelor ascunse: schema lui Shor de utilizare a transformării cuantice rapide Fourier și analogii acesteia.

Tipul 1) este reprezentat de algoritmul Zalka-Wiesner pentru modelarea dinamicii unitare a sistemelor cuantice de particule în timp aproape real și cu memorie liniară. Acest algoritm folosește schema Shor a transformării cuantice Fourier.

Tipul 2) prezentat:

Tipul 1) este de cel mai mare interes din punctul de vedere al aplicațiilor ulterioare ale unui computer cuantic.

Clasificare

Clasificarea algoritmilor cuantici poate fi efectuată în funcție de tipul de transformări cuantice utilizate de algoritm. Transformările utilizate în mod obișnuit includ: en:phase kick-back , phase estimation , en:quantum Fourier transform , en:quantum walk , en:amplitude amplification , en:topological quantum field theory . De asemenea, este posibil să grupați algoritmii cuantici în funcție de tipul de probleme pe care le rezolvă. [5]

Algoritmi cunoscuți

Vezi și

Note

  1. ↑ „Randomness as a Computational Resource” Arhivat 29 octombrie 2017 la Computerra Wayback Machine No. 10 din 18 martie 2002 „Quantum algorithms resemble probabilistic ones. În primul rând, incertitudinea rezultatului.
  2. ↑ „Cuantum computers”, PhD L. Fedichkin, FTI RAS. Nizh, 2001 nr. 01 „Introducerea calculatoarelor cuantice nu va duce la rezolvarea unor probleme clasice de nerezolvat algoritmic, ci doar va accelera unele calcule”
  3. ↑ Yuri Ozhigov, Lower Bounds of Quantum Search for Extreme Point, Proc. Roy. Soc. Londra. A455 (1999) 2165-2172 [1]
  4. ↑ Yuri Ozhigov, Calculatoarele cuantice accelerate clasice cu probabilitate zero, Chaos Solitons Fractals 10 (1999) 1707-1714 [2]
  5. ↑ Childs, Andrew M; Wim van Dam. Algoritmi cuantici pentru probleme algebrice  (neopr.)  // 0812.0380. - 2008. - 2 decembrie.

Link -uri

  Accesați articolul Wikidata  Dicționare și enciclopedii
 Algoritmi cuantici