Bernstein-Wazirani algoritmus

A Bernstein-Vazirani algoritmus egy kvantumalgoritmus , amely megoldja a fekete dobozba rejtett -bit szám (a külföldi szakirodalomban a rejtett karakterlánc [1] kifejezést is használják ) megtalálásának problémáját . Ethan Bernstein és Umesh Wazirani javasolta 1993-ban . Ez az algoritmus sokkal gyorsabban oldja meg a problémát, mint a nem kvantum-formulációban lehetséges . Az algoritmus használható adatbázisokban , blokkrejtjelek elleni támadásokban , kvantumszámítógépek teljesítménytesztjeiben , 5 és 16 qubites IBM kvantumszámítógépeken valósították meg [ . $n$

Történelem

Az algoritmust az Berkeley professzora, Vazirani és tanítványa, Ethan Bernstein javasolta Az algoritmus leírásakor a modern források általában Bernstein és Vazirani [2] beszédére hivatkoznak a számításelméleti szimpóziumon 1993-ban [3] . A Bernstein-Vazirani algoritmus a Deutsch-Yozhi algoritmus kiterjesztett változata , mivel ahelyett, hogy meghatározná, hogy egy függvény egy adott osztályhoz tartozik - kiegyensúlyozott vagy konstans (vagyis bármely argumentumhoz 0 vagy 1 értéket vesz fel), a algoritmus talál egy "rejtett" vektort, amely lehetővé teszi az értékfüggvények egyedi meghatározását bármely pontban [4] .

A Bernstein-Vazirani algoritmus a feladatban bemutatja, hogy megoldja a klasszikus és kvantum algoritmusok közötti szakadékot az orákulumhoz intézett legkevesebb kérések számában (fekete doboz). Ha engedélyezi is a valószínűségi algoritmusok használatát (előre korlátozott hibavalószínűséggel), a klasszikus probléma megoldásához szükség lesz az orákulum meghívására, míg a kvantum algoritmusban elegendő meghívni [5] . $Tovább)$ $O(1)$

A Bernstein-Vazirani probléma megállapítása

A klasszikus probléma

Tekintsünk egy orákulumot, amely egy -bites számot egy bitté alakít, azaz . $n$ $f:\{0,1\}^{n}\rightarrow \{0,1\}$

Sőt , hol van az alak skaláris szorzata: . Úgy tekintjük, hogy egy függvényhívás konstans időben történik. $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$

Meg kell találni [1] . $a$

A kvantumprobléma

A kvantummodell problémafelvetése hasonló, de az orákulumhoz való hozzáférés nem közvetlenül a függvényen keresztül történik, hanem egy qubit -rendszerre ható lineáris operátoron keresztül : $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|

ahol a kvantumállapotnak megfelelő ket vektor , a kvantumállapotnak megfelelő bra vektor , a Kronecker-szorzat , és a modulo 2 összeadás . $|x\rangle$ $x$ $\langle x|$ $x$ $\otimes$ $\oplus$

A kvantumállapotok és megfelelnek a és a vektoroknak . A közös állapot vektora szorzatként ábrázolható [6] . $0$ $egy$ ${\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$

A klasszikus esethez hasonlóan feltételezzük, hogy az orákulum hívása, amely a qubit - ből számítja ki az operátor bemeneti rendszerre történő alkalmazásának eredményét , állandó időben történik. $U_{f}$ $n+1$

Kvantumesetben, akárcsak a klasszikus esetben, feltételezzük, hogy , és meg kell találni [1] . $f(x)=a\cdot x$ $a$

Algoritmus

A klasszikus probléma

A klasszikus esetben minden orákulumhívás a szám egy bitjét adja vissza , így a -bit szám megtalálásához meg kell hívni az orákulumidőket . Az alábbiakban az orákulum hívásainak egy változata látható, amely lehetővé teszi az [1] teljes visszaállítását : $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}$

Az orákulum hívásainak száma klasszikus esetben , ahol a szám bitjeinek száma . Az egyszerű információelméleti érvelés megmutatja, hogy ez a korlát még a BPP osztály keretein belül sem javítható [1] . $Tovább)$ $n$ $a$

Kvantum algoritmus

Az algoritmus az n-qubit Hadamard operátoron alapul :

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

És az is, hogy egy operátor alkalmazása a forma állapotára , ahol az [1] értéket eredményezi . ${\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 }$

Az algoritmus működése lépésről lépésre a következőképpen ábrázolható [1] :

Az első lépésben a Hadamard operátort alkalmazzuk egy -qubit állapotra , amely egy alapállapotból és egy : $H^{\otimes {(n+1)))$ $(n+1)$ $|0\rangle ^{n}|1\rangle$ $|0\rangle ^{n}$ $|1\tartomány$ ${\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 }$ ;
Ezután az operátort alkalmazzuk az előző lépés eredményére : $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 }$ ;
Ezután az eredmény első qubitjére kerül alkalmazásra , amely figyelembe véve, hogy [ 4] : $n$ ${\displaystyle 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 }$ .

Ennek eredményeként a bemeneti regiszter mérése az [1] értéket adja . Így a probléma kvantumfogalmazásánál elegendő az orákulumra hivatkozni. Általános esetben egy orákulum felépítéséhez és használatához logikai elemekre van szükség , de ezt ebben a modellben nem vesszük figyelembe az algoritmus elemzésekor, mivel számára csak az orákulum hívásainak száma jelentős [1] . Az algoritmust ebben a formában 5 és 16 qubites IBM számítógépeken valósították meg [1] , lehetőség van az algoritmust megvalósító optikai rendszer összeállítására is [7] . $|a\rangle$ $O(1)$ $O(4^{n})$

Az algoritmus megvalósítása IBM számítógépeken

A Bernstein-Vazirani algoritmus bármely gyakorlati megvalósítása során a fő nehézséget az orákulum létrehozása jelenti, mivel az orákulum felépítéséhez és használatához logikai elemre van szükség . [egy] $O(4^{n})$

Az orákulum felépítésének bonyolultsága mellett a gyakorlati megvalósítást a pontossággal kapcsolatos problémák is kísérik. A rendszert 1-, 2- és 3-bites karakterláncokon teszteltük, amelyeken az IBM-Qiskit szimulátor 100%-os pontossággal meg aEzután az 1- és 2-bites karakterláncok tesztelését végezték el egy 5 qubites ibmqx4 és egy 16 qubit ibmqx5 gépen, ahol számítási hibákat és a várt eredménytől való erős eltérést rögzítettek [1] .

Gyakorlati alkalmazás

A Bernstein-Wazirani algoritmus alkalmazható:

Adatbázisokban [8] . Egy algoritmus segítségével a szükséges adatokhoz elméletileg sokkal gyorsabban hozzá lehet jutni, mint a klasszikus esetben.
A blokk titkosítás elleni támadásban [9] . A Bernstein-Wazirani algoritmus számos új, a klasszikusnál fejlettebb módszert kínál a blokk titkosítás megtámadására.
A kvantumszámítógépek teljesítménytesztjében [10] . Az algoritmust egy 11 qubites kvantumszámítógép teljesítménytesztjeként használják.

Jegyzetek

↑ 1 2 3 4 5 6 7 8 9 10 11 12 Coles et al, 2018 , p. 10-13.
↑ Ethan Bernstein, Umesh Vazirani. A kvantumkomplexitás elmélete // A Huszonötödik éves ACM Számítástechnikai Szimpózium előadásai. - New York, NY, USA: 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. 7. előadás: A Deutsch-Josza és Berstein-Vazirani algoritmusok // Bevezetés a kvantumszámításba 2018. nyár, Paderborni Egyetem. - P. 1-10 .
↑ Hidary, 2019 , p. 12-13.
↑ Coles et al, 2018 , p. négy.
↑ P. Londero, K. Banaszek, I. A. Walmsley, C. Dorrer, M. Anderson. A Bernstein-Vazirani algoritmus hatékony optikai megvalósítása (angol) // Fizikai Szemle A. - 2004. - V. 69 , no. 1 . — S. 010302–010302.4 . — ISSN 1050-2947 . - doi : 10.1103/PhysRevA.69.010302 .
↑ A.A. Jezsov. A kvantum neurotechnológia néhány problémája (orosz) // Tudományos ülésszak MEPhI–2003. V Össz-oroszországi tudományos és műszaki konferencia "Neuroinformatika-2003": előadások a neuroinformatikáról. 2. rész - 2003. - S. 44-45 . Az eredetiből archiválva : 2022. január 21.
↑ Huiqin Xie, Li Yang. Bernstein–Vazirani algoritmus használata blokkrejtjelek támadására // Tervek, kódok és kriptográfia. — 2019-05-01. — 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 és J. Kim. Egy 11 qubites kvantumszámítógép teljesítményértékelése // Nature Communications. - 2019. - 1. évf. 10. - S. 5464. - doi : 10.1038/s41467-019-13534-2 .

Linkek

Patrick J. Coles, Stephan Eidenbenz, Scott Pakin, Adetokunbo Adedoyin, John Ambrosiano. Kvantum-algoritmus-megvalósítások kezdőknek // arXiv:1804.03719 [quant-ph]. — 2018.
David Deutsch, Roger Penrose. Kvantumelmélet, a Church–Turing-elv és az univerzális kvantumszámítógép (angol) // Proceedings of the Royal Society of London. A. Matematikai és fizikai tudományok. - 1985. - július 8. ( 400. kötet , 1818. évf. ). — P. 97–117 . - doi : 10.1098/rspa.1985.0070 .
Charles H. Bennett, Ethan Bernstein, Gilles Brassard, Umesh Vazirani. Strengths and Weaknesses of Quantum Computing (angol) // SIAM J. Comput .. - 1997. - Vol. 26. - P. 1510-1523. - doi : 10.1137/S0097539796300933 . — arXiv : quant-ph/9701001 .
Jack D. Hidary. Kvantum számítástechnika: alkalmazott megközelítés . - Springer International Publishing, 2019. - P. 104-107. — ISBN 978-3030239213 . - doi : 10.1007/978-3-030-23922-0 .

kvantuminformatika

Általános fogalmak

kvantumkommunikáció

kvantumcsatorna
- kvantumhálózat
kvantumkriptográfia
- Kvantumkulcs-elosztás
A kvantumenergia teleportálása
kvantum teleportáció
Ultra-sűrű kvantumkódolás
LOCC
kvantum desztilláció

Kvantum algoritmusok

kvantum szimulátor
Deutsch-Yozhi algoritmus
Bernstein-Wazirani algoritmus
Grover algoritmusa
Kvantum Fourier transzformáció
Shor algoritmusa
Simon problémája
Kvantumfázis-becslési algoritmus
Kvantumszámítási algoritmus
kvantumlágyítás
Algoritmikus hűtés
Kvantumalgoritmus lineáris egyenletrendszer megoldására
Amplitúdó erősítés

Kvantumkomplexitás elmélet

Turing kvantumgép
EQP
BQP
QMA
PostBQP
QIP

Kvantum számítástechnikai modellek

kvantumkör
- kvantumkapu
Egyoldalas kvantumszámítógép
- fürt
Adiabatikus kvantumszámítás
Topológiai kvantumszámítógép

Dekoherencia megelőzés

Kvantumhibák korrekciója
Stabilizációs kódok
Stabilizációs formalizmus
Kvantumkonvolúciós kód

Fizikai megvalósítások

kvantumoptika	Kavitációs kvantumelektrodinamika Kontúrkvantumelektrodinamika Lineáris optikán alapuló kvantumszámítás KLM protokoll Bozonikus mintavétel
szuperhideg atomok	Elnyelt ion kvantumszámítógép Optikai rács
hát alapú	Mágneses magrezonancián alapuló kvantumszámítógép Kane kvantumszámítógépe Veszteséges kvantumszámítógép - DiVincenzo NV központ
Szupravezető kvantumszámítógépek	töltés qubit streaming qubit Fázis qubit Transmon