Väitös, tietotekniikka, DI Henrik Lievonen

Väitöskirjan nimi: Locality in distributed quantum and online graph algorithms

Väittelijä: Henrik Lievonen 
Vastaväittäjä: professori Artur Czumaj, Department of Computer Science, University of Warwick, Yhdistynyt kuningaskunta
Kustos: apulaisprofessori Jukka Suomela, Aalto-yliopiston perustieteiden korkeakoulu 

Tietotekniikan kehittyessä tietokoneiden määrä on kasvanut räjähdysmäisesti, ja samalla on kasvanut tarve yhdistää useita tietokoneita toisiinsa erilaisten tehtävien suorittamiseksi. Tällaisia suuria tietokoneverkkoja kutsutaan hajautetuiksi järjestelmiksi, ja niissä suoritettavavaa laskentaa hajautetuksi laskennaksi. Tässä väitöskirjassa tarkastellaan tehtävien ratkaisemisen paikallisuutta useissa hajautetun laskennan malleissa. Paikallisuudella tarkoitetaan, kuinka kauas tiedon on kuljettava verkossa tarvittavan tehtävän suorittamiseksi. Koska tiedon siirtämiseen kuluu aikaa, pienempi paikallisuus tarkoittaa suoraan nopeampaa ratkaisua. Väitöskirjassa tutkitaan erityisesti paikallisesti tarkistettavien merkitsemisongelmien paikallisuutta; nämä ovat laskennallisia ongelmia – eli tehtäviä – joiden ratkaisun tarkastaminen onnistuu paikallisesti, mutta ratkaisun löytäminen voi vaatia tiedon välittämistä pitkiäkin matkoja.

Väitöskirjassa paikallisuutta tarkastellaan sekä yksittäisten ongelmien kautta että osoittamalla laajoja yhteyksiä useiden laskennan mallien välille, mikä mahdollistaa monien paikallisuustulosten helpon yleistämisen useille hajautetun laskennan malleille. Väitöskirjassa esitelläänkin ensimmäinen paikallisesti tarkistettava laskennallinen ongelma, jolle voidaan todistaa hajautettu kvanttietu: kyseinen ongelma ratkeaa todistettavasti nopeammin, kun käytössä on kvanttitietokoneiden verkko klassisen hajautetun järjestelmän sijaan. Ongelma on koostettu yhdistämällä useita kvanttipelejä toisiinsa; kvanttipelit ovat yksinkertaisia matemaattisia yhteistyöpelejä, joiden voittamiseen tarvitaan kvanttitietokoneita.

Väitöskirjan toinen keskeinen kontribuutio on paikallisuuden käsitteen esitteleminen online-verkkoalgoritmeihin. Nämä ovat algoritmeja, joille esitellään verkko yksi solmu kerrallaan, ja jokaisen solmun esittelyn jälkeen algoritmin täytyy tuottaa ratkaisun osa kyseiselle solmulle siten, että tuotettu ratkaisu on lopuksi yhtenevä koko verkolle. Yleisesti tiedetään, että monet laskennalliset ongelmat ovat mahdottomia ratkaista tässä mallissa, ellei algoritmille anneta jotain lisätietoa verkon rakenteesta. Tässä väitöskirjassa tutkitaan, mitkä ongelmat on mahdollista ratkaista, mikäli lisätietona annetaan verkon paikallinen rakenne, eli kaikki verkon solmut ja yhteydet tiettyyn annettuun etäisyyteen – eli paikallisuuteen – asti. Väitöskirjassa osoitetaankin, että kaikki ongelmat, jotka ovat ratkaistavissa nopeasti joko klassisissa hajautetuissa järjestelmissä tai hajautetuissa kvanttitietokoneverkoissa ovat ratkaistavissa myös tässä mallissa pienellä paikallisuudella. Väitöskirjassa myös esitellään tälle laskennan mallille uusi nopea verkon 3-väritysalgoritmi, sekä osoitetaan, että se on paras mahdollinen.

Avainsanat: hajautetut algoritmit, hajautetut kvanttialgoritmit, LCL-ongelmat

Linkki väitöskirjan sähköiseen esittelykappaleeseen (esillä 7 päivää ennen väitöstä): Aalto-yliopiston riiputussivu.

Yhteystiedot:
https://henriklievonen.fi/
https://research.cs.aalto.fi/da/