Groverin algoritmin soveltuvuus hakualgoritmina

Abstract

Groverin hakualgoritmi on ollut viime vuosina tarkastelun kohteena uutena vaihtoehtona etsiä alkiota tietokannasta. Sen kvanttimekaniikkaan pohjautuva toteutus on todettu ajalliselta kompleksisuudeltaan tehokkaammaksi löytää alkio järjestämättömästä tietokannasta kuin minkään muun hakualgoritmin. Tämän tutkielman tarkoituksena on selvittää Groverin algoritmin soveltuvuutta hakualgoritmina teorian sekä käytännön näkökulmasta. Teorian näkökulmasta tutkielma selvittää, millaisilla tietokannan ominaisuuksilla Groverin algoritmi on asymptoottisesti tehokkaampi verrattuna klassisiin hakualgoritmeihin. Klassisina hakualgoritmeina tutkielma käsittelee peräkkäishakua, puolitushakualgoritmia sekä hajautustaulua. Käytännön näkökulmana tutkielma tekee kirjallisuuskatsauksen tutkimuksiin, jossa Groverin hakualgoritmi on toteutettu kvanttitietokoneella. Tutkielmassa selvisi, että Groverin algoritmin asymptoottinen tehokkuus on riittävän dynaamisessa tietokannassa melkein aina klassisia hakualgoritmeja parempi haettaessa yksittäistä alkiota tietokannasta. Tietokannan suuruuden kasvaessa, Groverin algoritmin asymptoottinen tehokkuus on yhä useammin parempi verrattuna klassisiin hakualgoritmeihin. Ainoastaan staattisissa tietokannoissa klassiset hakualgoritmit ovat huomattavasti Groverin algoritmia tehokkaampia. Kirjallisuuskatsauksen tulokset antoivat kuitenkin päinvastaisen kuvan algoritmin suorituskyvystä. Tutkimuksissa Groverin algoritmin suorituskyky oli teoreettista alkion löytämisen todennäköisyyttä huomattavasti pienempi. Tämä johti siihen, että jo hyvin pienillä kvanttitietokannoilla, algoritmi ei kyennyt löytämään alkiota riittävän useasti. Ero teorian ja käytännön välillä, perustuen tutkimuksien hypoteeseihin, uskotaan liittyvän kvanttitietokoneiden virhealttiuteen muun muassa porteissa tapahtuvien virheiden sekä dekoherenssin vuoksi. Tutkimuksen lopputuloksena on, että nykyinen kvanttitietokoneiden teknologia ei ole riittävällä tasolla Groverin algoritmin toteuttamiseksi riittävän suurella onnistumisen todennäköisyydellä. Kuitenkin teoreettisesti Groverin algoritmilla on tietyillä tietokannan ominaisuuksilla huomattavasti parempi asymptoottinen tehokkuus kuin muilla hakualgoritmeilla. Groverin hakualgoritmin todellisen soveltuvuuden tutkielma määrittelee muodostuvan kvanttitietokoneiden tulevaisuuden kehityksen tuomista mahdollisista ratkaisuista.