Project Description

Kvanttitietokoneet ja suunnistuksen anatomia

Matti Heikkinen

Teknolgiakasvatusta Otaniemen lukiossa

Kevään kiintorasteilla suunnistajan ensimmäinen ratkaistava kysymys on se, että missä järjestyksessä rastit kannattaa hakea siten, että  kuljettava matka olisi mahdollisimman lyhyt?

Oittaan kiintorastit

Kun rasteja on vähän, niin  ihmisen aivot pärjäävät numeerisia laskuja tekeville koneille.  Vilkaisemalla karttaa jokaisen on helppo rajata pois huonoimmat vaihtoehdot, ja hahmottaa kartasta melko hyvä ja toimiva suunnistusreitti. Seuraavaksi tutkitaan, miten tietokoneet etsivät ratkaisun ongelmaan.

Erilaisten vaihtoehtojen hahmottamiseksi punaiseen kuvaan on piirretty neljä ensimmäistä rastia ja laskettu kaikkien rastien väliset etäisyydet.

Kuva 1. Hyvin yksinkertainen kvanttilaskennan koodi graafisena esityksenä. Kuvassa on 3 kubittia (q0), jotka kytketään toisiinsa ja M-portit siirtävät mittaustulokset klassisille biteille (c0), jolloin kvanttilaskenta päättyy.

Kun ratkaisu etsitään klassisella tietokoneella, on rastit kierrettävä kaikissa mahdollisissa erilaisissa järjestyksissä ja tehtävä samalla kirjanpitoa, mikä on lyhin reitti (tulos sinisessä kuvassa). Laskenta onnistuu, jos rasteja on suhteellisen vähän. Jos tehtävänä olisi esim. laskea optimaalinen tapa jakaa koko Suomen posti yhdellä ajoreitillä, erilaisia vaihtoehtoja olisi hyvin runsaasti. Tällöin perinteisten tietokoneiden laskuteho voi loppua helposti kesken. Ongelman ratkaisu on kuitenkin tärkeää, koska se pienentää logistiikan energiankulutusta ja kustannuksia.

brute-force ratkaisu

Jos rasteja on todella paljon, laskentaongelma sopii hyvin kvanttitietokoneiden ratkaistavaksi, koska optimoititehtävän matemaattinen muotoilu johtaa samanlaiseen yhtälöön kuin fysikaalisessa systeemissä, jossa lasketaan ulkoisessa magneettikentässä olevien keskenään vuorovaikuttavien sauvamagneettien minimienergiatila (ns. Ising-Hamiltonian). Tällöin systeemiä kuvaavat kubitit käyttäytyvät kuin kuvan demonstraatiolaitteen pienet sauvamagneetit U-magneetin ulkoisessa magneettikentässä. Kunkin pienen sauvamagneetin asento eli tila määräytyy viereisten pienten magneettien ja ulkoisen U-magneetin magneettikentän ohjaamana, jolloin kollektiivisena yhteisenä lopputuloksena nähdään kuvassa hahmottuva magneettikentän optimaalisin muoto. Kun kubittien avulla ohjelmoitua kvanttialgoritmia suoritetaan, muodostavat keskenään vuorovaikuttavat kubitit yhdessä ratkaisun sille miten rastit on kierrettävä, että kokonaismatka on mahdollisimman lyhyt. Kvanttialgoritmi on tehokas, koska kvanttitietokoneessa kubittien sisältämän informaation ja kubittien keskenäisen vuorovaikutuksen avulla tutkitaan jokainen mahdollinen suoritusjärjestys samanaikaisesti yhdellä kertaa, jolloin kubitit valikoivat systeemistä sellaisen lopputilan, joka suoritusjärjestykseltään mahdollisimman lyhyt. 

Googlaamalla ”qiskit optimization travelling salesman -problem” IBM:n qiskit-tutoriaaleista löytyy lisätietoa. Vihreässä kuvassa on IBM:n kvanttitietokonetta simuloimalla kvanttialgoritmilla (4^2 = 16 kubitilla) laskettu suunnistusreitti, joka vastaa klassisen tietokoneen tulosta.

Kvanttitietokoneet eivät ole syrjäyttämässä klassisia tietokoneita yhteiskunnassamme, mutta esimerkki havainnolistaa sitä, että kvanttitietokoneiden hyvin erilainen toimintaperiaate mahdollistaa kvanttikoneiden hyödyntämisen sellaisten ongelmien ratkaisemisessa, joihin nykyisten supertietokoneiden laskentateho ei riitä edes parhaimmilla rinnakkaislaskenta optimoinneilla. 

Travelling Salesman Problem-lähdekoodi, jolla kuvat piirretty:

https://github.com/otaniemenlukio/kvanttilaskenta2021/blob/master/materiaaleja/liitteet/testiOittaa.ipynb