A kvantumalgoritmus egy kvantumszámítógépen való futtatásra tervezett algoritmus .
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.
A kvantumalgoritmusok által felgyorsított problémák fő típusai a brute-force problémák. 2 fő csoportra oszthatók:
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:
A kvantumszámítógép további alkalmazásai szempontjából az 1) típus a legérdekesebb.
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]
![]() |
---|
Kvantum algoritmusok | |
---|---|
kvantuminformatika | |||||||||
---|---|---|---|---|---|---|---|---|---|
Általános fogalmak |
| ||||||||
kvantumkommunikáció |
| ||||||||
Kvantum algoritmusok |
| ||||||||
Kvantumkomplexitás elmélet |
| ||||||||
Kvantum számítástechnikai modellek |
| ||||||||
Dekoherencia megelőzés |
| ||||||||
Fizikai megvalósítások |
|