Kvantum algoritmus

A kvantumalgoritmus egy kvantumszámítógépen való futtatásra tervezett  algoritmus .

Alapelvek

A kvantumalgoritmus egy klasszikus algoritmus, amely egységes műveletek sorozatát (kapuk vagy kapuk) határozza meg, jelezve, hogy mely qubiteken kell végrehajtani azokat. A kvantum-algoritmus vagy az ilyen parancsok szóbeli leírása, vagy grafikus jelölése révén egy kapurendszer (kvantumkapu tömb) formájában van megadva.

A kvantumalgoritmus eredménye valószínűségi [1] . Az algoritmusban a műveletek számának kismértékű növekedése miatt tetszőlegesen a megfelelő eredmény elérésének valószínűségét lehet hozni.

A kvantumszámítógépen és a klasszikuson megoldható feladatsorok egybeesnek. A kvantumszámítógép így nem növeli az algoritmikusan megoldható problémák számát. A kvantumszámítógép használatának lényege, hogy bizonyos problémákat sokkal gyorsabban tud megoldani, mint bármelyik klasszikus. Ehhez a kvantumalgoritmusnak összefonódott kvantumállapotokat kell generálnia és használnia a számítás során (lásd Kvantum - szuperpozíció és Kvantumösszefonódás ).

Bármilyen kvantumalgoritmussal megoldott probléma megoldható klasszikus számítógéppel is, exponenciális dimenziójú unitárius mátrixok közvetlen kiszámításával, a kvantumállapotok explicit formáját kapva. Különösen azok a problémák, amelyek a klasszikus számítógépeken megoldhatatlanok (például a leállítási probléma ), a kvantumszámítógépeken is megoldhatatlanok maradnak. Ám az ilyen közvetlen szimulációhoz exponenciális időre van szükség, ezért a kvantumpárhuzamot alkalmazva lehetővé válik néhány klasszikus algoritmus felgyorsítása kvantumszámítógépen [2] .

A kvantumszámítógépen a gyorsulás nem függ össze a processzor órajelével. A kvantumpárhuzamon alapul. A kvantumszámítás egy lépése sokkal több munkát végez, mint a klasszikus számítástechnika egy lépése. Hiba lenne azonban egyenlőségjelet tenni a kvantumszámítás és a párhuzamosított klasszikus számítások közé. Például egy kvantumszámítógép nem tudja gyorsabban megoldani a számlálási problémát, mint hol  van egy determinisztikus klasszikus számlálási algoritmus futási ideje (lásd [3] ), míg egy nemdeterminisztikus klasszikus algoritmus időben megoldja . De egy nem determinisztikus klasszikus algoritmus exponenciális memória erőforrást igényel, azaz fizikailag nem kivitelezhető, míg a kvantum algoritmus nem mond ellent az ismert természeti törvényeknek.

A kvantumszámítás egy speciális folyamat. Speciális fizikai erőforrást használ: a kvantum - összefonódott állapotokat , ami bizonyos esetekben lehetővé teszi, hogy elképesztő időnövekedést érjenek el. Az ilyen eseteket a klasszikus számítástechnika kvantumgyorsításának nevezik.

A kvantumgyorsulás esetei a klasszikus algoritmusok általános tömegének hátterében nagyon ritkák (lásd [4] ). Ez azonban mit sem von le a kvantumszámítás alapvető fontosságából, mert alapvetően képesek felgyorsítani a brute-force feladatok végrehajtását.

Alapvető kvantumgyorsítási sémák

A kvantumalgoritmusok által felgyorsított problémák fő típusai a brute-force problémák. 2 fő csoportra oszthatók:

1. Komplex rendszerek dinamikájának modellezésének problémái (Feynman eredeti ötlete) ill
2. Matematikai feladatok, amelyek a lehetőségek felsorolásában merülnek fel:
   1. Általános felsorolási eset: Grover séma és változatai, valamint
   2. Rejtett periódusok keresésének problémái: Shor séma a gyors kvantum Fourier transzformáció és analógjai felhasználására.

Az 1) típust a Zalka-Wiesner algoritmus képviseli, amely a részecskék kvantumrendszereinek unitárius dinamikáját szinte valós időben és lineáris memóriával modellezi. Ez az algoritmus a kvantum Fourier transzformáció Shor sémáját használja.

2. típus) bemutatva:

• Grover algoritmusa az általános keresési problémára és annak folytonos és adiabatikus változatai, valamint Grover sémáját használó algoritmusok: strukturális keresés (Fari, Gutman), szélsőséges keresési algoritmus (Hoyer stb.) és megfelelő sorok keresése az adatbázisban (Ambainis) ,
• Shor algoritmusa egész számok faktorizálására, Abrams-Lloyd algoritmus periódusdetektálásra, Kitaev algoritmusa rejtett alcsoportok meghatározására stb.

A kvantumszámítógép további alkalmazásai szempontjából az 1) típus a legérdekesebb.

Osztályozás

A kvantumalgoritmusok osztályozása elvégezhető az algoritmus által használt kvantumtranszformációk típusa szerint. Az általánosan használt transzformációk a következők: en:phase kick-back , fázisbecslés , en:quantum Fourier transzformáció , en:quantum walk , en:amplitúdóerősítés , en:topológiai kvantumtérelmélet . Lehetőség van a kvantum algoritmusok csoportosítására is aszerint, hogy milyen típusú problémákat oldanak meg. [5]

Jól ismert algoritmusok

• Shor algoritmusa
• Grover algoritmusa
• Deutsch-Yozhi algoritmus

Lásd még

• kvantumszámítógép
• kvantum programozás
• A kvantumszámítás idővonala
• Kvantumkulcs-elosztás
• Algoritmusok listája
• BQP osztály

Jegyzetek

1. ↑ „Véletlenség mint számítási erőforrás” Archivált : 2017. október 29., a Computerra Wayback Machine No. 10, 2002. március 18. „A kvantum algoritmusok hasonlítanak a valószínűségi algoritmusokra. Először is az eredmény bizonytalansága.
2. ↑ "Kvantumszámítógépek", PhD L. Fedichkin, FTI RAS. Nizh, 2001 No. 01 "A kvantumszámítógépek bevezetése nem vezet algoritmikusan megoldhatatlan klasszikus problémák megoldásához, csak felgyorsít néhány számítást"
3. ↑ Jurij Ozhigov, A kvantumkeresés alsó határai az extrém pontokhoz, Proc. Roy. Soc. London. A455 (1999) 2165-2172 [1]
4. ↑ Jurij Ozsigov, a Quantum Computers Speed ​​​​Up Classical nulla valószínűséggel, Chaos Solitons Fractals 10 (1999) 1707-1714 [2]
5. ↑ Childs, Andrew M; Wim van Dam. Kvantumalgoritmusok algebrai problémákhoz  (neopr.)  // 0812.0380. - 2008. - december 2.

Linkek

• Stephen Jordan, Algebrai és számelméleti algoritmusok  – Kvantumalgoritmusok átfogó katalógusa, NIST, 2013

Szótárak és enciklopédiák	nagy kínai