Deutsch-Yozhi algoritmus

A Deutsch-Joja algoritmus (más néven Deutsch-Joza algoritmus ) David Deutsch és Richard Joja által 1992 -ben javasolt kvantumalgoritmus , és az egyik első kvantumalgoritmus . Az algoritmus a kvantumösszefonódás jelenségén és a szuperpozíció elvén alapul , aminek köszönhetően kvantumfölényt mutat – sokkal hatékonyabb működést az ismert klasszikus algoritmusokhoz képest.

Deutsch algoritmusa a Deutsch által 1985 -ben kifejlesztett algoritmus első változata; egy változó függvényét veszi figyelembe $f(x_{1})$

Kihívás

Ismeretes, hogy egy logikai függvény konstans (ugyanazt az értéket vesz fel minden argumentumhalmazhoz) vagy kiegyensúlyozott (az argumentumkészletek feléhez a , a másik feléhez ). A függvény típusát úgy kell meghatározni, hogy a függvényt minél kevesebbszer kiértékelő orákulumra hivatkozunk. Továbbá a rövidség kedvéért a teljes halmazt egy számmal is jelölhetjük tól -ig a megfelelő bináris jelöléssel . $f(x_{1},x_{2},\dots ,x_{n})$ $0$ $egy$ $x_{1},x_{2},\pontok ,x_{n}$ $0$ $2^{n}-1$

A pontos válasz megszerzéséhez minden klasszikus determinisztikus algoritmusnak legrosszabb esetben meg kell hívnia az orákulumot, mivel az első számítások ugyanazt az értéket adhatják, annak ellenére, hogy a függvény kiegyensúlyozott. A klasszikus valószínűségi algoritmus kevesebb számítást igényel, hogy garantálja a helyes válasz megszerzésének nagy valószínűségét, de egységet is csak nem kevesebb, mint számítás után ér el. $2^{{n-1}}+1$ $2^{{n-1}}$ $2^{{n-1}}+1$

A kvantumbeállításban a függvény kiszámítása egy kvantum orákulum hívása formájában történik , amely egy egységes transzformációt hoz létre, amely a függvény argumentumaként működő qubitek halmazára , valamint egy cél qubitre hat . amelyet a számítások tükrözni fognak. Egy ilyen transzformáció eredménye bármely sajátállapot esetén a halmaz , ahol a kizárólagos „vagy” jelölése , amely megfelel egy qubit qubit segítségével szabályozott negációjának műveletének eredményének . Mivel az egységtranszformációk lineárisak , egy adott transzformáció eredménye a sajátállapotok szuperpozíciójára a következőképpen definiálható: $U_{f}$ $|x_{1}x_{2}\dots x_{n}\rangle |y\rangle =|x\rangle |y\rangle$ $n$ $x_{1},x_{2},\pontok ,x_{n}$ $y$ $|x\rangle$ $|x\rangle |y\oplus f(x)\rangle$ $\oplus$ $|y\rangle$ $|f(x)\rangle$ $|x\rangle =\alpha _{0}|0\rangle +\ldots +\alpha _{2^{n}-1}|2^{n}-1\rangle$ $U_{f}(|x\rangle |y\rangle )=\alpha _{0}|0\rangle |y\oplus f(0)\rangle +\ldots +\alpha _{2^{n }-1}|{2^{n}-1}\rangle |y\oplus f(2^{n}-1)\rangle .$

A Deutsch-Jozhi algoritmus esetében egyetlen kvantum-orákulum hívása elegendő a probléma megbízható megoldásához.

Algoritmus

Az algoritmus a Hadamard transzformáción alapul , amely qubit sajátállapotok szuperpozícióit eredményezi ${\textstyle H}$

|+\rangle =H|0\rangle ={\frac {1}{\sqrt {2}}}{\big (}|0\rangle +|1\rangle {\big )},

|-\rangle =H|1\rangle ={\frac {1}{\sqrt {2}}}{\big (}|0\rangle -|1\rangle {\big )}.

Ha az orákulum elérésekor a cél qubit állapotban van , akkor az orákulum az úgynevezett fázislekérdezést valósítja meg, amelynek eredménye a sajátállapotokra az, hogy a teljes állapotot megszorozza [1] -gyel : $|-\rangle$ ${\megjelenítési stílus (-1)^{f(x)))$

U_{f}{\big (}|x\rangle |-\rangle {\big )}={\frac {1}{\sqrt {2))}|x\rangle {\big (}| f(x)\rangle -|1\oplus f(x)\rangle {\big )}=(-1)^{f(x)}|x\rangle |-\rangle .

Így az állapotok szuperpozíciója esetén a fázislekérdezés minden -nek megfelelő állapot fázisát megfordítja, az állapotnak megfelelő állapotokat pedig változatlanul hagyja . Fázis lekérdezési argumentumként a Deutsch-Joji algoritmus az állapotot használja $x$ $f(x)=1$ $f(x)=0$

H^{\otimes n}|0\rangle ^{\otimes n}=|+\rangle ^{\otimes n}={\frac {1}{\sqrt {2^{n)))) \sum \limits _{x\in \{0,1\}^{n}}|x\rangle ,

amely egy qubit halmaz összes sajátállapotának egyenletes szuperpozíciója. Itt a tenzor (Kronecker) szorzaton keresztüli hatványozást jelöli . A fázislekérdezés ilyen állapotra történő alkalmazásának eredménye az $n$ $\otimes n$ $n$

U_{f}{\big (}|+\rangle ^{\otimes n}|-\rangle {\big )}={\frac {1}{\sqrt {2^{n)))) \sum \limits _{x\in \{0,1\}^{n}}(-1)^{f(x)}|x\rangle |-\rangle .

A transzformáció újbóli alkalmazása után az első qubitekre az állapotamplitúdó egyenlő lesz ${\displaystyle H^{\otimes n))$ $n$ ${\displaystyle |0\rangle ^{\otimes n))$

{\frac {1}{2^{n}}}\sum \limits _{x\in \{0,1\}^{n}}(-1)^{f(x)},

azaz -val vagy -val , vagy ha a függvény kiegyensúlyozott. Így egy függvény egyensúlyának ellenőrzése egyenértékű annak ellenőrzésével, hogy minden qubit az algoritmus végén lévő állapotban van-e. $egy$ $f(x)=0$ $-egy$ $f(x)=1$ $0$ $|0\tartomány$

Más szóval, az algoritmus az operátor alkalmazása a nulla vektorra és a regiszter állapotának mérése. Ha minden regiszterbit egyenlő , akkor a függvény értéke nem függ -től , ellenkező esetben a függvény kiegyensúlyozott. ${\displaystyle |0\rangle ^{\otimes n))$ ${\displaystyle H^{\otimes n}U_{f}H^{\otimes n))$ $0$ $f(x)$ $x$

Ha a függvény kiegyensúlyozatlan, akkor az algoritmus "állandó" választ adhat olyan valószínűséggel, amely a "0" és az "1" szám közötti különbség növekedésével nő [2] . $f$

Az algoritmus működése a Deutsch probléma példáján

Az algoritmus bemenete egy változó logikai függvénye . Négy ilyen funkció létezik [1] : $f(x)$

Nem.	$f(0)$	$f(1)$
egy	0	0	$f(x) \equiv 0$
2	egy	egy	$f(x)\ekvivalens 1$
3	0	egy	$f(x) = x$
négy	egy	0	$f(x)=\neg x$

Az 1. és 2. függvény állandó, a 3. és 4. függvény pedig kiegyensúlyozott.

Az első lépésben a qubit nulla állapotot kap:

|\varphi \rangle =1\cdot |0\rangle +0\cdot |1\rangle .

A Hadamard transzformáció alkalmazása megadja

|\varphi \rangle ={\frac {1}{\sqrt {2}}}\cdot |0\rangle +{\frac {1}{\sqrt {2}}}\cdot |1\rangle .

Elvileg egy qubithez azonnal hozzá lehet rendelni egy ilyen állapotot, de technikailag egyszerűbb először a nulla állapotot beállítani, majd unitárius transzformációkkal a kívánt formára transzformálni.

Egy függvény fázishívása a következő állapotot adja: ${\displaystyle O_{f))$ $f$

|\varphi \rangle =(-1)^{f(0)}\cdot {\frac {1}{\sqrt {2))}\cdot |0\rangle +(-1)^{f (1)}\cdot {\frac {1}{\sqrt {2))}\cdot |1\rangle .

A második Hadamard-transzformáció a következő állapothoz vezet:

|\varphi \rangle =(-1)^{f(0)}\cdot {\frac {1}{2))\cdot {\big (}|0\rangle +|1\rangle {\ big )}+(-1)^{f(1)}\cdot {\frac {1}{2}}\cdot {\big (}|0\rangle -|1\rangle {\big )}=

=\left((-1)^{f(0)}+(-1)^{f(1)}\right)\cdot {\frac {1}{2}}\cdot |0\ rangle +\left((-1)^{f(0)}-(-1)^{f(1)}\jobbra)\cdot {\frac {1}{2))\cdot |1\rangle .

A qubit állapotának mérésekor 0-t kapunk a konstans függvényekre, 1-et a kiegyensúlyozottakra:

Nem.	$f(0)$	$f(1)$	qubit állapot $\|\varphi \rangle$	0 a valószínűsége	Megszerzésének valószínűsége 1
egy	$0$	$0$	${\big (}(-1)^{0}+(-1)^{0}{\big )}\cdot {\frac {1}{2))\cdot \|0\rangle +{ \big (}(-1)^{0}-(-1)^{0}{\big )}\cdot {\frac {1}{2))\cdot \|1\rangle =1\cdot \|0 \rangle +0\cdot \|1\rangle$	$1^{2}=1$	$0$
2	$egy$	$egy$	${\big (}(-1)^{1}+(-1)^{1}{\big )}\cdot {\frac {1}{2))\cdot \|0\rangle +{ \big (}(-1)^{1}-(-1)^{1}{\big )}\cdot {\frac {1}{2))\cdot \|1\rangle =-1\cdot \| 0\rangle +0\cdot \|1\rangle$	$(-1)^{2}=1$	$0$
3	$0$	$egy$	$((-1)^{0}+(-1)^{1})\cdot {\frac {1}{2}}\cdot \vert 0\rangle +((-1)^{0}-( -1)^{1})\cdot {\frac {1}{2}}\cdot \vert 1\rangle =0\cdot \vert 0\rangle +1\cdot \vert 1\rangle$	$0$	$1^{{2}}=1$
négy	$egy$	$0$	${\big (}(-1)^{1}+(-1)^{0}{\big )}\cdot {\frac {1}{2))\cdot \|0\rangle +{ \big (}(-1)^{1}-(-1)^{0}{\big )}\cdot {\frac {1}{2))\cdot \|1\rangle =0\cdot \|0 \rangle -1\cdot \|1\rangle$	$0$	$(-1)^{2}=1$

Irodalom

Wolf R. d. Quantum Computing (angol) : Előadásjegyzetek - 2019. - 176 p. arXiv : 1907.09415

Jegyzetek

↑ 1 2 M. Lanyha . Quantum Algorithms: Opportunities and Limitations, 2. előadás ( Archiválva : 2011. június 10. a Wayback Machine -nél ), p. 12-13. - Szentpétervár, 2011 tavasz.
↑ M. lomha . Quantum Algorithms 2. előadás Archiválva : 2013. április 26. a Wayback Machine -nál .

Kvantum algoritmusok
Shor algoritmusa Grover algoritmusa Deutsch-Yozhi algoritmus Feynman probléma Zalka-Wiesner algoritmus kvantumlágyítás

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