Kahdeksan kuningattaren ongelma kvanttilaskennassa

Niklas Halonen ja Matti Heikkinen 8.4.2022

Sisällys

Tässä artikkelissa  tutkitaan miten klassista matematiikan ja algoritmiikan  kahdeksan kuningattaren ongelma voidaan ratkaista kvanttitietokoneen suorittaman kvanttialgoritmin avulla.

8 kuningattaren ongelmassa tehtävänä on ratkaista miten 8 kuningatarta voi laittaa 8×8 ruudun shakkilaudalle ilman että yksikään kuningatar uhkaisi toista.

Artikkelissa tutkitaan yleistettyä N kuningattaren ongelman ratkaisua kvanttilaskennan avulla. Kvanttialgoritmin lisäksi artikkelin lopussa esitetään myös perinteisen tietokoneen algoritmi N kuningattaren ongelmaan.

Artikkelissa havaitaan, että perinteisten tietokoneiden ratkaisualgoritmit ovat eksponentaalisesti hitaampia kuin kvanttialgoritmi. Voit kokeilla omalla tietokoneellasi ja huomata, että perinteisten tietokoneiden laskentakapasiteetti ei aina riitä kvanttitietokoneen suorittaman kvanttipiirin simulointiin. Esimerkiksi viiden kuningattaren ongelma vaatii 40 kubittia ja 17 teratavua keskusmuistia tilavektorin simuloimiseksi perinteisellä tietokoneella.

Jos kvanttialgoritmi suoritetaan oikealla kvanttitietokoneella, niin tarvitaan paljon kubitteja, sekä monimutkaisia kvanttiportteja, joilla suuri tarkkuus eli fideliteetti laskentavirheiden välttämiseksi. Tällä hetkellä verkon yli käytettävissä ilmaisissa kvanttitietokoneissa on tarjolla yleensä 5 kubittia. Kvanttitietokoneiden kehitys on kuitenkin nopeaa tällä hetkellä.

Jypyter notebook -tiedosto on ladattavissa Otaniemen lukion GitHub-tililtä, jos haluat suorittaa koodia itse omalla koneellasi.

 

HUOMAA: Teoria ja python-esimerkit käännetty html-versioksi, jotta materiaalin voi lukea helposti nettiselaimessa.

Linkit materiaaliin: