Algoritmi cuantici

În calculul cuantic, un algoritm cuantic este un algoritm care rulează pe un model realist de calcul cuantic, cel mai frecvent utilizat model fiind modelul de circuit cuantic de calcul.[1][2] Un algoritm clasic (sau non-cuantic) este o secvență finită de instrucțiuni sau o procedură pas cu pas pentru rezolvarea unei probleme, în care fiecare pas sau instrucțiune poate fi executată pe un computer clasic. În mod similar, un algoritm cuantic este o procedură pas cu pas, în care fiecare dintre pași poate fi executat pe un computer cuantic. Deși toți algoritmii clasici pot fi, de asemenea, executați pe un computer cuantic,[3]: 126  termenul de algoritm cuantic este în general rezervat algoritmilor care par inerent cuantici sau utilizează o caracteristică esențială a calculului cuantic, cum ar fi superpoziția cuantică sau inseparabilitatea cuantică.

Problemele care sunt indecidabile folosind computere clasice rămân indecidabile folosind computere cuantice.[4]: 127  Ceea ce face ca algoritmii cuantici să fie interesanți este faptul că ar putea fi capabili să rezolve unele probleme mai rapid decât algoritmii clasici, deoarece superpoziția cuantică și inseparabilitatea cuantică pe care le exploatează algoritmii cuantici, în general, nu pot fi simulate eficient pe computere clasice.

Cei mai cunoscuți algoritmi sunt algoritmul lui Shor pentru factorizare și algoritmul lui Grover pentru căutarea într-o bază de date nestructurată sau într-o listă neordonată. Algoritmul lui Shor, dacă ar fi implementat, ar rula mult (aproape exponențial) mai repede decât cel mai eficient algoritm clasic cunoscut pentru factorizare, sita generală a câmpului numeric.[5] De asemenea, algoritmul lui Grover ar rula pătratic mai repede decât cel mai bun algoritm clasic posibil pentru aceeași sarcină,[6] o căutare liniară.

Algoritmii cuantici sunt de obicei descriși, în modelul de circuit utilizat în mod obișnuit în calculul cuantic, printr-un circuit cuantic care acționează asupra unor qubiți de intrare și se termină cu o măsurătoare. Un circuit cuantic este alcătuit din porți cuantice simple, fiecare dintre acestea acționând asupra unui număr finit de qubiți. Algoritmii cuantici pot fi enunțați și în alte modele de calcul cuantic, cum ar fi modelul oracolului hamiltonian.[7]

Algoritmii cuantici pot fi clasificați în funcție de principalele tehnici implicate în algoritm. Câteva tehnici/idei utilizate în mod obișnuit în algoritmii cuantici includ faza kick-back, estimarea fazei, transformata cuantică Fourier, traseele cuantice, amplificarea amplitudinii și teoria topologică cuantică a câmpului. Algoritmii cuantici pot fi, de asemenea, grupați în funcție de tipul de problemă rezolvată; vezi, de exemplu, studiul privind algoritmii cuantici pentru probleme algebrice.[8]

Referințe

1. A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman , Exponential algorithmic speedup by quantum walk, Proc. 35th ACM Symposium on Theory of Computing, pp. 59–68, 2003, arXiv:quant-ph/0209131.
2. A. M. Childs, L. J. Schulman, and U. V. Vazirani, Quantum algorithms for hidden nonlinear structures, Proc. 48th IEEE Symposium on Foundations of Computer Science, pp. 395–404, 2007, arXiv:0705.2784.
3. Andris Ambainis, Quantum walk algorithm for element distinctness, SIAM J. Comput. 37 (2007), no. 1, 210–239,arXiv:quant-ph/0311001 , preliminary version in FOCS 2004.
4. F. Magniez, M. Santha, and M. Szegedy, Quantum algorithms for the triangle problem, Proc. 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 1109–1117, 2005, quant-ph/0310134.
5. E. Farhi, J. Goldstone, and S. Gutmann, A quantum algorithm for the Hamiltonian NAND tree, Theory of Computing 4 (2008), no. 1, 169–190, quant-ph/0702144
6. Kempe, J. (1 February 2008). „Quantum random walks – an introductory overview”. Contemporary Physics. 44 (4): 307–327. arXiv:quant-ph/0303081. Bibcode:2003ConPh..44..307K. doi:10.1080/00107151031000110776.
7. Andrew M. Childs, „Universal Computation by Quantum Walk”.
8. Kempe, Julia (1 July 2003). „Quantum random walks – an introductory overview”. Contemporary Physics. 44 (4): 307–327. arXiv:quant-ph/0303081. Bibcode:2003ConPh..44..307K. doi:10.1080/00107151031000110776. ISSN 0010-7514. S2CID 17300331.

(Include texte traduse și adaptate din Wikipedia de Nicolae Sfetcu)