Gráfelméleti algoritmusok beágyazása D-Wave kvantumszámítógépbe
| Szerző | Szabó Dániel |
|---|---|
| Konzulens | Friedl Katalin |
| Típus | TDK (II. helyezett) |
| Dátum | 2017. november 16. |
| Nyelv | magyar |
| Referencia | https://tdk.bme.hu/VIK/Szimu/Grafelmeleti-algoritmusok-beagyazasa-DWave |
Absztrakt
Napjainkban egyre gyakrabban hallani híreket a kvantuminformatika világából, például új kvantumszámítógépekről vagy kvantumkommunikációs áttörésekről. Ezekkel összefüggésben egyre fontosabb szerep juthat a közeljövőben a kvantumalgoritmusoknak.
A kvantuminformatika a kvantummechanikából ismert jelenségeken alapul, amely szerint a mikrorészecskék mozgása valószínűségi módon írható le. Ilyen részecskével valósítható meg egy kvantumbit: egyszerre van a két, jól megkülönböztethető klasszikus állapot (0 és 1) szuperpozíciójában, az egyikben $p$, a másikban $1-p$ valószínűséggel. Ilyen módon egy $n$ kvantumbites rendszer egyszerre $2^n$ állapotban van, ennek leírására (azaz az egyes állapotok valószínűségének eltárolására) klasszikus esetben $2^n$-nel arányos darabszámú bit kell. Ettől lehet hatékonyabb sok probléma megoldása kvantumszámítógéppel, mint klasszikusan: pl. prímtényezőkre bontás, rendezetlen halmazban keresés [1], [2].
A kanadai D-Wave Systems vállalat volt az első a világon, amely kvantumszámítógépet adott el, a legutóbbi számítógépük 2048 kvantumbites [3]. Bár megoszlanak a vélemények arról, hogy valóban kvantumos elven működő számítógépekről van-e szó, ettől függetlenül érdemes foglalkozni azzal a számítási modellel, amely a gépek mögött van. A modell alapja a Kiméra gráf (Chimera graph), amelybe be kell ágyazni a problémákat [4].
A dolgozat célja, hogy segítségül szolgáljon a modell megértéséhez. Ezen kívül elvégeztem néhány NP-teljes gráfelméleti probléma beágyazását (pl. van-e egy gráfban megadott méretű klikk; van-e olyan részgráfja, ami adott méretű teljes páros gráf). Ehhez már megoldott problémák alapötleteit használtam fel [5], amelyeket szintén ismertetek. Mivel nem kevés hétköznapi probléma megfogalmazható gráfelméleti úton (pl. nagy hálózatokban közösségek keresése), remélhetőleg idővel néhány ilyen feladat hatékony megoldásához vezethetnek a leírtak.
Források:
[1] Mika Hirvensalo. Quantum Computing (2. kiadás, 2004). Springer – Verlag Berlin Heidelberg
[2] Nielsen, M. and Chuang, I. L.. Quantum Computing and Quantum Information (2001). Cambridge University Press, Cambridge.
[3] Wikipédia – D-Wave Systems: https://en.wikipedia.org/wiki/D-Wave_Systems (2017. 09. 20.)
[4] E. D. Dahl. Programming with D-Wave: Map Coloring Problem (2013): https://www.dwavesys.com/sites/default/files/Map%20Coloring%20WP2.pdf
[5] Eleanor G. Rieffel, Davide Venturelli, Bryan O’Gorman, Minh B. Do, Elicia Prystay, and Vadim N. Smelyanskiy. A case study in programming a quantum annealer for hard operational planning problems (2014). arXiv:1407.2887v1: https://arxiv.org/pdf/1407.2887.pdf
