Algoritmul Bernstein-Wazirani

Algoritmul Bernstein-Vazirani este un algoritm cuantic care rezolvă problema găsirii unui număr -bit (termenul șir ascuns [1] este folosit și în literatura străină ) ascuns într-o cutie neagră . Propus de Ethan Bernstein și Umesh Wazirani în 1993 . Acest algoritm rezolvă problema mult mai rapid decât este posibil în formularea non-cuantică . Algoritmul poate fi utilizat în baze de date , atacuri asupra cifrurilor bloc , teste de performanță pentru calculatoare cuantice , a fost implementat pe calculatoare cuantice IBM de 5 și 16 qubiți . $n$

Istorie

Algoritmul a fost propus de profesorul Berkeley Vazirani și studentul său Ethan Bernstein Când descriu algoritmul, sursele moderne, de regulă, se referă la discursul lui Bernstein și Vazirani [2] la un simpozion despre teoria calculului în 1993 [3] . Algoritmul Bernstein-Vazirani este o versiune extinsă a algoritmului Deutsch-Yozhi , deoarece în loc să se determine dacă o funcție aparține unei anumite clase - echilibrată sau constantă (adică, ia fie valoarea 0, fie 1 pentru orice argument) - algoritmul găsește un vector „ascuns” care vă permite să determinați în mod unic funcțiile valorice în orice punct [4] .

Algoritmul Bernstein-Vazirani demonstrează în problemă că rezolvă decalajul dintre algoritmii clasici și cei cuantici în ceea ce privește cel mai mic număr necesar de cereri către oracol (cutie neagră). Chiar dacă permiteți folosirea algoritmilor probabilistici (cu o probabilitate de eroare prelimitată), rezolvarea problemei clasice va necesita apeluri la oracol, în timp ce în algoritmul cuantic este suficient să-l numiți [5] . $Pe)$ $O(1)$

Declarația problemei Bernstein-Vazirani

Problema clasică

Luați în considerare un oracol care convertește un număr -bit într-un bit, adică . $n$ $f:\{0,1\}^{n}\rightarrow \{0,1\}$

Mai mult , unde este produsul scalar al formei: . Considerăm că un apel de funcție este efectuat în timp constant. $f(x)=a\cdot x$ $\cdot$ $x\cdot y=x_{1}y_{1}\oplus x_{2}y_{2}\oplus ...\oplus x_{n}y_{n)$ $f$

Este necesar să se găsească [1] . $A$

Problema cuantică

Enunțul problemei din modelul cuantic este similar, dar accesul la oracolul din acesta se realizează nu direct prin intermediul funcției , ci printr-un operator liniar care acționează asupra unui sistem de qubiți : $f$ $U_{f}$ $n+1$

U_{f}=\sum _{x\in \{0,1\}^{n},y\in \{0,1\}}|x\rangle \langle x|\otimes |y \oplus f(x)\rangle \langle y|

unde este vectorul ket corespunzător stării cuantice , este vectorul bra corespunzător stării cuantice , este produsul Kronecker și este adiția modulo 2 . $|x\rangle$ $X$ $\langle x|$ $X$ $uneori$ $\oplus$

Stările cuantice și corespund vectorilor și . Vectorul pentru starea de îmbinare poate fi reprezentat ca produs [6] . $0$ $unu$ ${\textstyle |0\rangle ={\binom {1}{0))}$ ${\textstyle |1\rangle ={\binom {0}{1))}$ $x_{1}x_{2}\dots x_{n)$ $|x_{1}x_{2}\dots x_{n}\rangle =|x_{1}\rangle \otimes |x_{2}\rangle \otimes \dots \otimes |x_{n}\rangle$

La fel ca în cazul clasic, se presupune că apelul la oracol, care calculează rezultatul aplicării operatorului la sistemul de intrare din qubit , este efectuat în timp constant. $U_{f}$ $n+1$

În cazul cuantic, ca și în cazul clasic, se presupune că , și se cere să se găsească [1] . $f(x)=a\cdot x$ $A$

Algoritm

Problema clasică

În cazul clasic, fiecare apel oracol returnează un bit al numărului , așa că pentru a găsi numărul -bit , trebuie să apelați oracolul . Mai jos este o variantă de apeluri către oracol, permițându-vă să restaurați complet [1] : $A$ $n$ $A$ $n$ $n$ $A$

$f(1000...0_{n})=a_{1}$

$f(0100...0_{n})=a_{2}$

$\vdots$

$f(0000...1_{n})=a_{n}$

Numărul de apeluri către oracol în cazul clasic este , unde este numărul de biți ai numărului . Simplul raționament teoretic informațional poate arăta că această limită nu poate fi îmbunătățită nici măcar în cadrul clasei BPP [1] . $Pe)$ $n$ $A$

Algoritmul cuantic

Algoritmul se bazează pe operatorul Hadamard n-qubit :

{\textstyle H^{\otimes n}={\frac {1}{\sqrt {2^{n}}))\sum \limits _{x,y\in \{0,1\}^{n }}{{(-1)}^{x\cdot y}|y\rangle \langle x|}}

Și, de asemenea, faptul că aplicarea unui operator la o stare de forma , unde rezultă valoarea [1] . ${\textstyle U_{f))$ ${\textstyle |x\rangle |-\rangle =|x\rangle \otimes |-\rangle }$ ${\textstyle |-\rangle ={\frac {|0\rangle -|1\rangle }{\sqrt {2))))$ ${\textstyle U_{f}(|x\rangle |-\rangle )=(-1)^{f(x)}|x\rangle |-\rangle }$

Pas cu pas, funcționarea algoritmului poate fi reprezentată astfel [1] :

În primul pas, operatorul Hadamard este aplicat unei stări -qubit constând dintr-o stare de bază și un bit auxiliar : $H^{\otimes {(n+1)))$ $(n+1)$ $|0\rangle ^{n}|1\rangle$ $|0\rangle ^{n}$ $|1\gamă$ ${\textstyle |0\rangle ^{n}|1\rangle {\xrightarrow {H^{\otimes {(n+1))}}}} {\frac {1}{\sqrt {2^{n)} }}\sum \limits _{x\in \{0,1\}^{n}}|x\rangle |-\rangle }$ ;
Apoi operatorul este aplicat rezultatului pasului anterior : $U_{f}$ ${\textstyle {\frac {1}{\sqrt {2^{n}}))\sum \limits _{x\in \{0,1\}^{n}}|x\rangle |-\rangle {\xrightarrow {~U_{f}~}}{\frac {1}{\sqrt {2^{n))))\sum \limits _{x\in \{0,1\}^{n} }{(-1)}^{f(x)}|x\rangle |-\rangle }$ ;
Apoi , se aplică primilor qubiți ai rezultatului , care, ținând cont de faptul că , dă [4] : $n$ $H^{\otimes (n))$ $f(x)=a\cdot x$ ${\textstyle {\frac {1}{\sqrt {2^{n}}))\sum \limits _{x\in \{0,1\}^{n}}{(-1)}^{ a\cdot x}|x\rangle |-\rangle {\xrightarrow {~H^{\otimes (n)}~}}{\frac {1}{2^{n}}}\sum \limits _{ x,y\in \{0,1\}^{n}}{(-1)}^{(a\cdot x)\oplus (x\cdot y)}|y\rangle |-\rangle \sim |a\rangle |-\rangle }$ .

Ca rezultat, măsurarea registrului de intrare va da valoarea [1] . Astfel, în formularea cuantică a problemei, este suficient să ne referim la oracol. În cazul general, construcția și utilizarea unui oracol necesită elemente logice , dar acest lucru nu este luat în considerare la analiza algoritmului din acest model, deoarece doar numărul de apeluri către oracol este semnificativ pentru acesta [1] . Algoritmul sub această formă a fost implementat pe calculatoare IBM de 5 și 16 qubiți [1] , este posibil și asamblarea unui sistem optic care implementează algoritmul [7] . $|a\rangle$ $O(1)$ $O(4^{n})$

Implementarea algoritmului pe calculatoarele IBM

În orice implementare practică a algoritmului Bernstein-Vazirani, principala dificultate este crearea unui oracol, deoarece construcția și utilizarea unui oracol necesită un element logic . [unu] $O(4^{n})$

Pe lângă complexitatea construirii unui oracol, implementarea practică este însoțită de probleme de acuratețe. Sistemul a fost testat pe șiruri de 1, 2 și 3 biți, pe care simulatorul IBM-Qiskit răspunsul cu o acuratețe de 100% Apoi, testarea șirurilor de 1 și 2 biți a fost efectuată pe o mașină ibmqx4 de 5 qubiți și o mașină ibmqx5 de 16 qubiți, unde au fost înregistrate erori de calcul și o abatere puternică de la rezultatul așteptat [1] .

Aplicație practică

Algoritmul Bernstein-Wazirani poate fi aplicat:

În bazele de date [8] . Cu ajutorul unui algoritm, accesul la datele necesare poate fi obținut teoretic mult mai rapid decât în cazul clasic.
În atacul asupra cifrului bloc [9] . Algoritmul Bernstein-Wazirani oferă câteva modalități noi, mai avansate decât în cazul clasic, de a ataca un cifru bloc.
În testul de performanță pentru calculatoarele cuantice [10] . Algoritmul este folosit ca test de performanță pentru un computer cuantic de 11 qubiți.

Note

↑ 1 2 3 4 5 6 7 8 9 10 11 12 Coles et al, 2018 , p. 10-13.
↑ Ethan Bernstein, Umesh Vazirani. Teoria complexității cuantice // Lucrările celui de-al douăzeci și cincilea simpozion anual ACM privind teoria calculului. - New York, NY, SUA: ACM, 1993. - S. 11-20 . — ISBN 978-0-89791-591-5 . - doi : 10.1145/167088.167097 .
↑ Hidary, 2019 , p. 104-107.
↑ 1 2 Sevag Gharibian. Curs 7: Algoritmii Deutsch-Josza și Berstein-Vazirani // Introduction to Quantum Computation Summer 2018, University of Paderborn. - P. 1-10 .
↑ Hidary, 2019 , p. 12-13.
↑ Coles et al, 2018 , p. patru.
↑ P. Londero, K. Banaszek, I.A. Walmsley, C. Dorrer, M. Anderson. Implementarea optică eficientă a algoritmului Bernstein-Vazirani (engleză) // Physical Review A. - 2004. - V. 69 , nr. 1 . — S. 010302–010302.4 . — ISSN 1050-2947 . - doi : 10.1103/PhysRevA.69.010302 .
↑ A.A. Iezhov. Câteva probleme ale neurotehnologiei cuantice (rusă) // Sesiune științifică MEPhI–2003. V Conferință științifică și tehnică din întreaga Rusie „Neuroinformatică-2003”: prelegeri despre neuroinformatică. Partea 2. - 2003. - S. 44-45 . Arhivat din original pe 21 ianuarie 2022.
↑ Huiqin Xie, Li Yang. Folosirea algoritmului Bernstein–Vazirani pentru a ataca cifrurile bloc // Designuri, coduri și criptare. — 01-05-2019. — Vol. 87 , iss. 5 . — P. 1161–1182 . — ISSN 1573-7586 . - doi : 10.1007/s10623-018-0510-5 .
↑ K. Wright, K. M. Beck, S. Debnath, J. M. Amini, Y. Nam, N. Grzesiak, J.-S. Chen, NC Pisenti, M. Chmielewski, C. Collins, KM Hudek, J. Mizrahi, JD Wong-Campos, S. Allen, J. Apisdorf, P. Solomon, M. Williams, AM Ducore, A. Blinov, SM Kreikemeier , V. Chaplin, M. Keesan, C. Monroe & J. Kim. Evaluarea comparativă a unui computer cuantic de 11 qubiți // Nature Communications. - 2019. - Vol. 10. - S. 5464. - doi : 10.1038/s41467-019-13534-2 .

Link -uri

Patrick J. Coles, Stephan Eidenbenz, Scott Pakin, Adetokunbo Adedoyin, John Ambrosiano. Implementări de algoritm cuantic pentru începători // arXiv:1804.03719 [quant-ph]. — 2018.
David Deutsch, Roger Penrose. Teoria cuantică, principiul Church-Turing și computerul cuantic universal (engleză) // Proceedings of the Royal Society of London. A. Ştiinţe matematice şi fizice. - 1985. - 8 iulie ( vol. 400 , iss. 1818 ). — P. 97–117 . - doi : 10.1098/rspa.1985.0070 .
Charles H. Bennett, Ethan Bernstein, Gilles Brassard, Umesh Vazirani. Puncte tari și puncte slabe ale calculului cuantic (engleză) // SIAM J. Comput .. - 1997. - Vol. 26. - P. 1510-1523. - doi : 10.1137/S0097539796300933 . — arXiv : quant-ph/9701001 .
Jack D. Hidary. Calcularea cuantică: o abordare aplicată . - Springer International Publishing, 2019. - P. 104-107. — ISBN 978-3030239213 . - doi : 10.1007/978-3-030-23922-0 .

informatica cuantica

Concepte generale

comunicații cuantice

canal cuantic
- rețea cuantică
criptografia cuantică
- Distribuția cheii cuantice
Teleportarea energiei cuantice
teleportarea cuantică
Codare cuantică ultradensă
LOCC
distilare cuantică

Algoritmi cuantici

simulator cuantic
Algoritmul Deutsch-Yozhi
Algoritmul Bernstein-Wazirani
Algoritmul lui Grover
Transformată Fourier cuantică
algoritmul lui Shor
problema lui Simon
Algoritmul de estimare a fazei cuantice
Algoritmul de calcul cuantic
recoacere cuantică
Răcire algoritmică
Algoritm cuantic pentru rezolvarea unui sistem de ecuații liniare
Câștig de amplitudine

Teoria complexității cuantice

Modele de calcul cuantic

circuit cuantic
- poarta cuantică
Calculator cuantic unilateral
- cluster
Calcul cuantic adiabatic
Calculator cuantic topologic

Prevenirea decoerenței

Corectarea erorilor cuantice
Codurile de stabilizare
Formalismul de stabilizare
Cod convoluțional cuantic

Implementări fizice

optica cuantică	Electrodinamica cuantică a cavitației Electrodinamica cuantică de contur Calcul cuantic bazat pe optică liniară Protocolul KLM Prelevarea bosonică
atomi superreci	Calculator cuantic cu ioni absorbiți Gratar optic
pe spate	Calculator cuantic bazat pe rezonanța magnetică nucleară Calculatorul cuantic al lui Kane Pierdere computer cuantic - DiVincenzo Centrul NV
Calculatoare cuantice supraconductoare	încărcați qubit streaming qubit qubit de fază Transmon