Bernstein-Wazirani algoritme

Bernstein - Vazirani- algoritmen er en kvantealgoritme , der løser problemet med at finde et -bit-tal (begrebet skjult streng [1] bruges også i udenlandsk litteratur ) skjult i en sort boks . Foreslået af Ethan Bernstein og Umesh Wazirani i 1993 . Denne algoritme løser problemet meget hurtigere, end det er muligt i den ikke-kvanteformulering . Algoritmen kan bruges i databaser , angreb på blokcifre , ydeevnetest for kvantecomputere , blev implementeret på 5- og 16-qubit IBM kvantecomputere . $n$

Historie

Algoritmen blev foreslået af Berkeley professor Vazirani og hans studerende Ethan Bernstein Når de beskriver algoritmen, henviser moderne kilder som regel til Bernsteins og Vaziranis tale [2] ved et symposium om beregningsteorien i 1993 [3] . Bernstein-Vazirani-algoritmen er en udvidet version af Deutsch-Yozhi-algoritmen , fordi i stedet for at bestemme, om en funktion tilhører en bestemt klasse - balanceret eller konstant (det vil sige, den tager enten værdien 0 eller 1 for eventuelle argumenter) - algoritmen finder en "skjult" vektor, der giver dig mulighed for entydigt at bestemme værdifunktionerne på ethvert punkt [4] .

Bernstein-Vazirani-algoritmen demonstrerer i problemet, at den løser kløften mellem klassiske og kvantealgoritmer i form af det mindst nødvendige antal anmodninger til oraklet (sort boks). Selvom man tillader brugen af probabilistiske algoritmer (med en forudbegrænset fejlsandsynlighed), vil løsningen af det klassiske problem kræve kald til oraklet, mens det i kvantealgoritmen er nok at kalde det [5] . $På)$ $O(1)$

Udtalelse af Bernstein-Vazirani-problemet

Det klassiske problem

Overvej et orakel, der konverterer et -bit-tal til en bit , dvs. $n$ $f:\{0,1\}^{n}\højrepil \{0,1\}$

Desuden , hvor er det skalære produkt af formen: . Vi vurderer, at et funktionskald udføres i konstant tid. $f(x)=a\cdot x$ $\cdot$ ${\displaystyle x\cdot y=x_{1}y_{1}\oplus x_{2}y_{2}\oplus ...\oplus x_{n}y_{n))$ $f$

Det er nødvendigt at finde [1] . $-en$

Kvanteproblemet

Problemformuleringen i kvantemodellen ligner, men adgang til oraklet i den udføres ikke direkte gennem funktionen , men gennem en lineær operator, der virker på et system af qubits : $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|

hvor er ket-vektoren svarende til kvantetilstanden , er bra-vektoren svarende til kvantetilstanden , er Kronecker-produktet og er modulo 2-addition . $|x\rangle$ $x$ $\langle x|$ $x$ $\ nogle gange$ $\plus$

Kvantetilstandene og svarer til vektorerne og . Vektoren for den fælles tilstand kan repræsenteres som et produkt [6] . $0$ $en$ ${\textstyle |0\rangle ={\binom {1}{0))}$ ${\textstyle |1\rangle ={\binom {0}{1))}$ ${\displaystyle 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$

I lighed med det klassiske tilfælde antages det, at opkaldet til oraklet, som beregner resultatet af at anvende operatøren til inputsystemet fra qubit , udføres i konstant tid. $U_{f}$ $n+1$

I kvantetilfældet, som i det klassiske tilfælde, antages det, at , og det kræves for at finde [1] . $f(x)=a\cdot x$ $-en$

Algoritme

Det klassiske problem

I det klassiske tilfælde returnerer hvert orakelkald en bit af nummeret , så for at finde -bit-nummeret skal du ringe til orakeltiderne . Nedenfor er en variant af opkald til oraklet, der giver dig mulighed for fuldstændigt at gendanne [1] : $-en$ $n$ $-en$ $n$ $n$ $-en$

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

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

$\vprikker$

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

Antallet af opkald til oraklet i det klassiske tilfælde er , hvor er antallet af bits af nummeret . Simpel informationsteoretisk ræsonnement kan vise, at denne grænse ikke kan forbedres selv inden for rammerne af BPP -klassen [1] . $På)$ $n$ $-en$

Kvantealgoritme

Algoritmen er baseret på n-qubit Hadamard-operatoren :

{\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|}}

Og også det faktum, at anvendelse af en operator på en tilstand af formen , hvor resulterer i værdien [1] . ${\tekststil U_{f))$ ${\tekststil |x\rangle |-\rangle =|x\rangle \nogle gange |-\rangle }$ ${\tekststil |-\rangle ={\frac {|0\rangle -|1\rangle }{\sqrt {2))))$ ${\tekststil U_{f}(|x\rangle |-\rangle )=(-1)^{f(x)}|x\rangle |-\rangle }$

Trin for trin kan operationen af algoritmen repræsenteres som følger [1] :

I det første trin anvendes Hadamard-operatoren på en -qubit-tilstand, der består af en grundtilstand og en hjælpebit : $H^{\otimes {(n+1)))$ $(n+1)$ $|0\rangle ^{n}|1\rangle$ $|0\rangle ^{n}$ $|1\interval$ ${\textstyle |0\rangle ^{n}|1\rangle {\xrightarrow {H^{\otimes {(n+1))))}{\frac {1}{\sqrt {2^{n)) }}\sum \limits _{x\i \{0,1\}^{n}}|x\rangle |-\rangle }$ ;
Derefter anvendes operatøren på resultatet af det foregående trin : $U_{f}$ ${\tekststil {\frac {1}{\sqrt {2^{n))))\sum \limits _{x\i \{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 }$ ;
Derefter anvendes , på de første qubits af resultatet , som under hensyntagen til det giver [4] : $n$ ${\displaystyle H^{\nogle gange (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 }$ .

Som et resultat vil måling af inputregisteret give værdien [1] . I kvanteformuleringen af problemet er det således tilstrækkeligt at henvise til oraklet. I det generelle tilfælde kræver konstruktionen og brugen af et orakel logiske elementer , men dette tages ikke i betragtning, når man analyserer algoritmen i denne model, da kun antallet af kald til oraklet er signifikant for det [1] . Algoritmen i denne form blev implementeret på 5- og 16-qubit IBM-computere [1] , det er også muligt at sammensætte et optisk system , der implementerer algoritmen [7] . $|a\rangle$ $O(1)$ $O(4^{n})$

Implementering af algoritmen på IBM-computere

I enhver praktisk implementering af Bernstein-Vazirani-algoritmen er den største vanskelighed oprettelsen af et orakel, da konstruktionen og brugen af et orakel kræver et logisk element . [en] $O(4^{n})$

Ud over kompleksiteten ved at bygge et orakel, er praktisk implementering ledsaget af problemer med nøjagtighed. Systemet blev testet på 1-, 2- og 3-bit strenge, hvorpå IBM-Qiskit-simulatoren det svar med 100 % nøjagtighed Derefter blev test af 1- og 2-bit strenge udført på en 5-qubit ibmqx4-maskine og en 16-qubit ibmqx5-maskine, hvor der blev registreret regnefejl og en kraftig afvigelse fra det forventede resultat [1] .

Praktisk anvendelse

Bernstein-Wazirani-algoritmen kan anvendes:

I databaser [8] . Ved hjælp af en algoritme kan adgang til de nødvendige data teoretisk opnås meget hurtigere end i det klassiske tilfælde.
I angrebet på blokchifferet [9] . Bernstein-Wazirani-algoritmen giver flere nye, mere avancerede end i det klassiske tilfælde, måder at angribe en blokchiffer på.
I ydeevnetesten for kvantecomputere [10] . Algoritmen bruges som en præstationstest for en 11-qubit kvantecomputer.

Noter

↑ 1 2 3 4 5 6 7 8 9 10 11 12 Coles et al., 2018 , s. 10-13.
↑ Ethan Bernstein, Umesh Vazirani. Kvantekompleksitetsteori // Proceedings of the 25th Annual ACM Symposium on Theory of Computing. - New York, NY, USA: ACM, 1993. - S. 11-20 . — ISBN 978-0-89791-591-5 . - doi : 10.1145/167088.167097 .
↑ Hidary, 2019 , s. 104-107.
↑ 1 2 Sevag Gharibian. Foredrag 7: Deutsch-Josza og Berstein-Vazirani algoritmerne // Introduction to Quantum Computation Summer 2018, University of Paderborn. - S. 1-10 .
↑ Hidary, 2019 , s. 12-13.
↑ Coles et al, 2018 , s. fire.
↑ P. Londero, K. Banaszek, I.A. Walmsley, C. Dorrer, M. Anderson. Effektiv optisk implementering af Bernstein-Vazirani-algoritmen (engelsk) // Physical Review A. - 2004. - V. 69 , no. 1 . — S. 010302–010302.4 . — ISSN 1050-2947 . - doi : 10.1103/PhysRevA.69.010302 .
↑ A.A. Yezhov. Nogle problemer med kvanteneuroteknologi (russisk) // Videnskabelig session MEPhI–2003. V All-russisk videnskabelig og teknisk konference "Neuroinformatics-2003": forelæsninger om neuroinformatik. Del 2. - 2003. - S. 44-45 . Arkiveret fra originalen den 21. januar 2022.
↑ Huiqin Xie, Li Yang. Brug af Bernstein-Vazirani-algoritmen til at angribe blokcifre // Designs, Codes and Cryptography. - 2019-05-01. — Bd. 87 , iss. 5 . — S. 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. Benchmarking af en 11-qubit kvantecomputer // Nature Communications. - 2019. - Bd. 10. - S. 5464. - doi : 10.1038/s41467-019-13534-2 .

Links

Patrick J. Coles, Stephan Eidenbenz, Scott Pakin, Adetokunbo Adedoyin, John Ambrosiano. Kvantealgoritmeimplementeringer for begyndere // arXiv:1804.03719 [quant-ph]. – 2018.
David Deutsch, Roger Penrose. Kvanteteori, Church–Turing-princippet og den universelle kvantecomputer (engelsk) // Proceedings of the Royal Society of London. A. Matematiske og fysiske videnskaber. - 1985. - 8. juli ( vol. 400 , iss. 1818 ). — S. 97–117 . - doi : 10.1098/rspa.1985.0070 .
Charles H. Bennett, Ethan Bernstein, Gilles Brassard, Umesh Vazirani. Strengths and Weaknesses of Quantum Computing (engelsk) // SIAM J. Comput .. - 1997. - Vol. 26. - P. 1510-1523. - doi : 10.1137/S0097539796300933 . — arXiv : quant-ph/9701001 .
Jack D. Hidary. Quantum Computing: En anvendt tilgang . - Springer International Publishing, 2019. - S. 104-107. — ISBN 978-3030239213 . - doi : 10.1007/978-3-030-23922-0 .

kvanteinformatik

Generelle begreber

kvantekommunikation

kvantekanal
- kvantenetværk
kvantekryptografi
- Kvantenøglefordeling
Teleportering af kvanteenergi
kvanteteleportation
Quantum ultra-tæt kodning
LOCC
kvantedestillation

Kvantealgoritmer

kvantesimulator
Deutsch-Yozhi algoritme
Bernstein-Wazirani algoritme
Grovers algoritme
Quantum Fourier transformation
Shors algoritme
Simons problem
Kvantefase-estimeringsalgoritme
Kvanteberegningsalgoritme
kvanteudglødning
Algoritmisk køling
Kvantealgoritme til løsning af et system af lineære ligninger
Amplitudeforstærkning

Kvantekompleksitetsteori

Turing kvantemaskine
EQP
BQP
QMA
PostBQP
QIP

Kvantecomputermodeller

kvantekredsløb
- kvanteport
Ensidet kvantecomputer
- klynge
Adiabatisk kvanteberegning
Topologisk kvantecomputer

Forebyggelse af dekohærens

Korrektion af kvantefejl
Stabiliseringskoder
Stabiliseringsformalisme
Kvante foldningskode

Fysiske implementeringer

kvanteoptik	Kavitationskvanteelektrodynamik Kontur kvanteelektrodynamik Kvanteberegning baseret på lineær optik KLM protokol Bosonisk prøvetagning
superkolde atomer	Absorberet ion kvantecomputer Optisk gitter
ryg baseret	Kvantecomputer baseret på kernemagnetisk resonans Kanes kvantecomputer Tabskvantecomputer - DiVincenzo NV center
Superledende kvantecomputere	opladningsqubit streaming qubit Fase qubit Transmon