Vuonna 1994 matemaatikko keksi kuinka saada kvanttitietokone tekemään jotain, mitä mikään tavallinen klassinen tietokone ei pystyisi. Työ paljasti, että periaatteessa kvanttimekaniikan sääntöihin perustuva kone voisi tehokkaasti hajottaa suuren joukon tärkeimpiin tekijöihin – tehtävä on niin vaikea klassiselle tietokoneelle, että se muodostaa perustan suurelle osalle nykypäivän Internet-tietoturvasta.
Siitä seurasi optimismi. Ehkäpä tutkijat ajattelivat, että voimme keksiä kvanttialgoritmeja, jotka voivat ratkaista valtavan määrän erilaisia ongelmia.
Mutta kehitys pysähtyi. "Se on ollut vähän kömpelö liikerata", sanoi Ryan O'Donnell Carnegie Mellonin yliopistosta. "Ihmiset sanoivat: "Tämä on mahtavaa, olen varma, että saamme kaikenlaisia muita hämmästyttäviä algoritmeja." Ei.” Tutkijat löysivät dramaattisia nopeuksia vain yhdelle, kapealle ongelmaryhmälle standardijoukosta nimeltään NP, mikä tarkoittaa, että heillä oli tehokkaasti todennettavissa olevia ratkaisuja – kuten factoring.
Näin oli lähes kolme vuosikymmentä. Sitten huhtikuussa tutkijat keksi pohjimmiltaan uudenlainen ongelma, jonka kvanttitietokoneen pitäisi pystyä ratkaisemaan eksponentiaalisesti nopeammin kuin klassinen. Se sisältää monimutkaisen matemaattisen prosessin syötteiden laskemisen, joka perustuu yksinomaan sen sekaviin lähtöihin. Vielä ei ole päätetty, onko ongelma yksin vai ensimmäinen monien muiden uudella rajalla.
"On jännitystä", sanoi Vinod Vaikuntanathan, Massachusetts Institute of Technologyn tietojenkäsittelytieteilijä. "Monet ihmiset miettivät, mitä muuta siellä on."
Tietojenkäsittelytieteilijät yrittävät ymmärtää, mitä kvanttitietokoneet tekevät paremmin tutkimalla niitä edustavia matemaattisia malleja. Usein he kuvittelevat kvantti- tai klassisen tietokoneen mallin yhdistettynä idealisoituun laskentakoneeseen, jota kutsutaan oraakkeliksi. Oraakkelit ovat kuin yksinkertaisia matemaattisia funktioita tai tietokoneohjelmia, jotka vastaanottavat syötteen ja sylkevät ulos ennalta määrätyn lähdön. Niillä voi olla satunnainen käyttäytyminen, jolloin tulostetaan "kyllä", jos syöte on tietyn satunnaisen alueen sisällä (esim. 12-67) ja "ei", jos se ei ole. Tai ne voivat olla jaksottaisia, joten syöte välillä 1-10 palauttaa "kyllä", 11-20 antaa "ei", 21-30 tuottaa jälleen "kyllä" ja niin edelleen.
Oletetaan, että sinulla on jokin näistä jaksollisista oraakkeleista etkä tiedä jaksoa. Ainoa mitä voit tehdä, on syöttää sille numeroita ja katsoa, mitä se tuottaa. Kuinka nopeasti tietokone voisi löytää ajanjakson näillä rajoituksilla? Vuonna 1993 Daniel Simon, silloinen Montrealin yliopistossa, havaitsi, että kvanttialgoritmi pystyi laskemaan vastauksen läheisesti liittyvään ongelmaan eksponentiaalisesti nopeammin kuin mikään klassinen algoritmi.
Tuloksen ansiosta Simon pystyi määrittämään yhden ensimmäisistä vihjeistä siitä, missä kvanttitietokoneiden dramaattinen ylivoima voitaisiin odottaa. Mutta kun hän esitti paperinsa johtavalle konferenssille, se hylättiin. Paperi kuitenkin kiinnosti konferenssin ohjelmakomitean nuorempaa jäsentä - Peter Shor, joka oli tuolloin Bell Laboratoriesissa New Jerseyssä. Shor jatkoi, että hän voisi mukauttaa Simonin algoritmin laskemaan oraakkelin ajanjakson, jos sillä olisi sellainen. Sitten hän tajusi, että hän voisi mukauttaa algoritmia vielä kerran ratkaistakseen yhtälön, joka käyttäytyy samalla tavalla kuin jaksollinen oraakkeli: yhtälön, joka kuvaa factoringia, joka on jaksollinen.
Shorin tulos oli historiallinen. Hänen löytämänsä kvanttialgoritmi pystyi nopeasti pelkistämään jättimäiset luvut niiden alkutekijöihin, mitä mikään tunnettu klassinen algoritmi ei pysty tekemään. Seuraavina vuosina tutkijat löysivät muita tehokkaita kvanttialgoritmeja. Jotkut niistä, kuten Shorin algoritmi, tarjosivat jopa eksponentiaalista etua, mutta kukaan ei pystynyt osoittamaan dramaattista kvanttietua missään NP-ongelmassa, joka ei ollut jaksollinen.
Tämä edistyksen puute johti kaksi tietotekniikan tutkijaa, Scott Aaronson Texasin yliopistosta, Austinista ja Andris Ambainis Latvian yliopistosta tehdä havainnon. Kvanttiedun todisteet näyttivät aina riippuvan oraakkeleista, joilla oli jonkinlainen ei-satunnainen rakenne, kuten jaksollisuus. Vuonna 2009 he arveltu että NP-ongelmissa, jotka olisivat satunnaisia tai rakenteettomia, ei voi olla dramaattisia nopeuksia. Kukaan ei löytänyt poikkeusta.
Heidän arvauksensa rajasivat kvanttitietokoneiden tehot. Mutta se sanoi vain, että tietyntyyppiselle jäsentämättömälle NP-ongelmalle ei ollut dramaattisia nopeuksia - niille, jotka vastasivat kyllä tai ei. Jos ongelmaan liittyi tarkempien, kvantitatiivisten vastausten keksiminen, mikä tunnetaan hakutehtävänä, olettamus ei kelvannut.
Tämä mielessä, tutkijat Takashi Yamakawa NTT Social Informatics Laboratories ja Mark Zhandry NTT Researchin ja Princetonin yliopiston päättivät kokeilla tiettyä hakuongelmaa, jonka esitteli vuonna 2005 Oded Regev.
Kuvittele joukko tuuliviiriä, jotka kaikki osoittavat samaan suuntaan. Anna kullekin mitattu työntää ja anna sitten puuskaisen tuulen vaikuttaa heidän suuntaansa. Regev halusi määrittää lopullisten ohjeidensa perusteella, mihin he kaikki osoittivat alun perin. Tällaisia ongelmia alettiin kutsua "virheillä oppimiseksi", koska töyssy ja tuuli toimivat satunnaisten virheiden lähteenä alkuperäisessä suunnassa. On näyttöä siitä, että sitä on vaikea ratkaista sekä klassisille että kvanttialgoritmeille.
Yamakawa ja Zhandry virittelivät asetuksia. He muuttivat aloitustyöntöjen vahvuutta tehden niistä ennakoitavampia. Ne myös saivat tuulen määrittämään satunnaisen oraakkelin, niin että se oli joissakin tapauksissa vielä satunnaisempi, mutta toisissa täysin lepotilassa.
Näillä muokkauksilla tutkijat havaitsivat, että kvanttialgoritmi voisi tehokkaasti löytää alkuperäisen suunnan. He myös osoittivat, että minkä tahansa klassisen algoritmin on oltava eksponentiaalisella kertoimella hitaampi. Shorin tavoin he mukauttivat algoritmiaan ratkaisemaan ongelman todellisen version, joka korvaa oraakkelin todellisella matemaattisella yhtälöllä.
Tietojenkäsittelytieteilijät työskentelevät edelleen ongelman ymmärtämiseksi ja kehittämiseksi. Vaikuntanathan vertaa sitä toiseen, joka syntyy tietojen pakkaamisessa: Kun tietoa puristetaan alas, kaksi bittiä voi vahingossa puristua samaan paikkaan, jolloin ne ylikirjoitetaan. Ongelma, joka liittyy törmäysten ennustamiseen etukäteen, jotta voit välttää ne, muistuttaa jonkin verran. "Se on luokka ongelmia, jotka periaatteessa näyttävät tältä", hän sanoi. "Ehkä nämä ongelmat voidaan ratkaista määrällisesti."
Toivottiin, että uuden kaltainen jäsentämätön ongelma voisi olla ratkaistavissa jopa nykypäivän aloittelevissa kvanttitietokoneiden versioissa, mikä tarjoaisi keinon niiden testaamiseen. Ajatus oli, että jäsentämättömät ongelmat saattavat viedä vähemmän resursseja ohjelmointiin tai olla vähemmän herkkiä melulle, koska ne ovat jo satunnaisia. Mutta toistaiseksi uusi ongelma näyttää edelleen liian edistyneeltä olemassa olevien kvanttitietokoneiden ratkaistavaksi. "Se on outo ongelma. En ollut ajatellut määritellä sitä", Aaronson sanoi. "Mutta jälkikäteen katsottuna siinä on joitain erittäin mukavia ominaisuuksia."
Tulos tarjoaa ensimmäisen esimerkin dramaattisesta kvanttiedusta rakenteettoman NP-ongelman suhteen. Voisiko olla monia muita ongelmia, jotka kvanttimaailma muuttaa käytännössä ratkaisemattomasta ratkaistavaksi? Nyt on enemmän syytä ajatella niin.
"Se on jossain määrin horjuttanut uskomuksiamme siitä, minkälaisiin ongelmiin kvanttitietokoneet voisivat olla hyviä", sanoi O'Donnell.
