Matkustavan myyjän ongelman ratkaiseminen kvanttitietokoneiden avulla

Tietojenkäsittelytieteen alalla klassinen algoritminen ongelma, joka tunnetaan nimellä Matkustavan myyjän ongelma (TSP), on erinomainen esimerkki kombinatoriellisesta optimointiongelmasta.

Mikä tarkalleen ottaen on TSP? Tämä matemaattinen klassikko käsittelee lyhimmän mahdollisen reitin löytämistä, jossa N kaupunkia käydään läpi täsmälleen kerran ennen paluuta lähtökaupunkiin. Kuitenkin, kun kaupunkien määrä kasvaa, myös mahdollisten reittien määrä ja optimaalisen ratkaisun laskenta-aika kasvavat. Kun tätä ongelmaa voidaan ratkaista likimääräisillä menetelmillä, kvanttitietokoneet voisivat tarjota paljon parempia ratkaisuja ja tehdä sen paljon nopeammin.

Tämä on juuri se, mitä teoreettinen fyysikko Prof. Dr. Jens Eisertin tiimi osoitti: että tällaiset ongelmat voidaan ratkaista paremmin ja nopeammin kvanttitietokoneilla.

Kvanttitietokoneet hyödyntävät laitteistoa ja algoritmeja, jotka käyttävät kvanttimekaniikkaa ratkaistakseen monimutkaisia ongelmia, jotka ovat perinteisten, myös supertietokoneiden, ulottumattomissa. Huolimatta niiden tehosta, supertietokoneet—massiiviset klassiset tietokoneet, joissa on tuhansia CPU- ja GPU-ytimiä—ovat rajoittuneita 20‑luvun transistoriteknologiaan, kun ne ratkaisevat erittäin monimutkaisia ongelmia.

Tässä kohtaa kvanttifysiikka astuu kuvaan. Toisin kuin klassiset tietokoneet, jotka koodaavat tiedon binäärisinä biteinä (0 ja 1), kvanttitietokoneet käyttävät kvanttibittejä tai kubitteja monidimensionaalisten kvanttialgoritmien suorittamiseen.

Lisäksi, toisin kuin perinteiset tietokoneet, jotka käyttävät tuulettimia jäähdytykseen, kvanttitietokoneet vaativat kvanttiprosessorinsa ylläpitämistä äärimmäisen kylmissä lämpötiloissa, jotta ne säilyttävät kvanttitilansa. Tämä saavutetaan superkylmillä supervirtaajilla.

Superjohtimet ovat materiaaleja, jotka osoittavat kriittisen kvanttimekaanisen ilmiön, jonka avulla elektronit voivat kulkea niiden läpi ilman vastusta. Kun elektronit kulkevat, ne parittuvat kantamaan varauksen esteiden yli. Kun kaksi superjohtinta asetetaan eristeen kummallekin puolelle, muodostuu Josephsonin liitos, jota käytetään superjohtavien kubittien johtamiseen.

Kubitti on hyödyllinen tärkeässä tehtävässä, jossa sen kvanttitieto asetetaan superpositiotilaan, joka on kubitin mahdollisten konfiguraatioiden yhdistelmä. Superpositiossa olevat kubittiryhmät voivat luoda monimutkaisia, monidimensionaalisia laskentatiloja, joissa monimutkaiset ongelmat voidaan esittää.

Tässä, kahden kubitin lomittumisen kautta yhden muutokset voivat vaikuttaa suoraan toiseen, ja kun nämä lomittuneet kubitit asetetaan superpositiotilaan, syntyy lukuisia todennäköisyyksiä. Kvanttitietokoneen laskenta toimii valmistamalla superpositio kaikista mahdollisista laskentatilasta, ja interferenssin avulla löydetään ratkaisuja.

Tietenkin monien kubittien sisältävän kvanttitietokoneen rakentaminen on erittäin monimutkainen prosessi, vaikka useita menetelmiä tutkitaan sen suhteen, mitä tällaiset tietokoneet voivat saavuttaa.

Eisertin mukaan, joka johtaa yhteistä tutkimusryhmää Helmholtz‑Zentrum Berlinissä (HZB), energiamateriaalitutkimuksen keskuslaitoksessa, sekä julkisessa tutkimusyliopistossa Freie Universität Berlin:

“Tähän liittyy paljon myyttejä, ja joskus myös ylimääräistä puhetta ja hypeä. Olemme kuitenkin lähestyneet asiaa perusteellisesti käyttäen matemaattisia menetelmiä ja toimittaneet vankkoja tuloksia aiheesta. Ennen kaikkea olemme selventäneet, missä mielessä etuja voi olla lainkaan.”

Kriittinen matkustavan myyjän ongelma

Optimointiongelmana TSP:llä on suuri taloudellinen merkitys logistiikka- ja toimitusketjualalla. Se kuuluu laajempaan kombinatoristen optimointiongelmien kategoriaan, johon kuuluvat myös työtehtävien aikataulutus, resurssien allokointi, salkun optimointi ja jopa proteiinien taittuminen, kaikki kriittisiä eri sektoreille.

Koska näillä ongelmilla on sosiaalinen ja taloudellinen merkitys, ne ovat olleet intensiivisen tutkimuksen kohteena. Näin ollen tehokkaimman toimitusketjun ja edullisimman reitin löytäminen vaikuttaa positiivisesti päivittäiseen elämäämme.

Kuitenkin monien kohteiden toimitusreittien optimointi ottaen huomioon erilaiset rajoitteet, kuten liikenteen ruuhkautuminen, kasvavat operatiiviset kulut, äkilliset reittimuutokset, viime hetken liiketoimintatapaamiset ja asiakaspyynnöt, tekee TSP:stä vielä haastavampaa ratkaista. Näistä haasteista huolimatta TSP:n ratkaiseminen on ratkaisevan tärkeää tavaroiden tehokkaan toimituksen varmistamiseksi, mikä takaa kannattavan liiketoimintamallin.

Tämän ongelman ratkaisemisesta on monia hyötyjä, kuten matkan ja ajokilometrien vähentäminen sekä polttoaineen kulutuksen säästäminen. Matkan pituuden minimointi voi merkittävästi pienentää hiilijalanjälkeä, mikä johtaa parempaan ilmanlaatuun, hidastaa ilmastonmuutosta ja edistää talouskasvua. Lisäksi TSP:n ratkaiseminen voi parantaa tavaroiden ajoissa tapahtuvaa toimitusta ja ajallisesti oikeiden tapaamisten toteutumista asiakkaiden kanssa, mikä parantaa asiakaskokemusta ja kenttäpalveluyrityksiä.

Kuten olemme nähneet, ongelman ratkaiseminen ei ainoastaan auta yrityksiä, vaan nämä hyödyt vuotavat myös asiakkaille, rikastuttaen kokemusta kaikille osapuolille.

TSP-ongelman ratkaisemiseen voidaan käyttää useita menetelmiä. Yksi tällainen menetelmä on ‘Brute-Force’-lähestymistapa, joka laskee kaikki mahdolliset permutaatiot löytääkseen lyhimmän reitin. Branch-and-bound-menetelmässä ongelma jaetaan useisiin aliongelmiin, ja kunkin vaiheen ratkaisu vaikuttaa seuraavien vaiheiden ratkaisuihin.

Dynaamisessa ohjelmoinnissa keskitytään turhien laskelmien välttämiseen. Nearest Neighbor -menetelmä on puolestaan likimääräinen algoritmi, jossa aloitat lähtöpisteestä ja siirryt sitten lähimpään kaupunkiin. Kun kaikki kaupungit on käyty läpi, palaat lähtöpisteeseen. Vaikka menetelmä on käytännöllinen ja melko nopea, se ei aina tuota tehokkainta reittiä.

Teknologian kehittyessä reittisuunnittelu ja optimointi voidaan toteuttaa paljon tehokkaammin. Erityisesti tekoäly (AI) voi auttaa ratkaisemaan ongelman analysoimalla valtavan määrän dataa nopeasti, mikä auttaa monia nykyaikaisia yrityksiä tekemään operatiivisia ja strategisia päätöksiä.

Kvanttitietokoneita tutkitaan myös ongelman ratkaisemiseksi; ne tarjoavat merkittäviä laskentanopeuden parannuksia perinteisiin tietokoneisiin verrattuna. On pitkään esitetty, että nämä tietokoneet voivat todellakin parantaa näiden ongelmien likimääräisiä ratkaisuja.

Kvanttitietokoneiden tekniikoiden käyttäminen TSP:n ratkaisemiseen

Vaikka kvanttitietokoneet keräävät valtavaa kiinnostusta ja tarjoavat lupaavia tuloksia tietyille ongelmille, kvanttieteen etuuden laajuus on edelleen suurelta osin tutkimatta.

Tämän seurauksena tutkimus tarjosi täyden konstruktiivisen todistuksen siitä, että kvanttitietokoneet voivat todellakin ylittää perinteiset tietokoneet kombinaatiollisten optimointiongelmien likimääräisten ratkaisujen löytämisessä.

Viimeisin tutkimus, jonka johdossa olivat Eisert ja hänen kollegansa Jean‑Pierre Seifert, käytti ainoastaan analyyttisiä menetelmiä arvioidakseen, kuinka kvanttitietokone kubitteineen voi ratkaista TSP-ongelman.

“Oletamme yksinkertaisesti, riippumatta fyysisestä toteutuksesta, että kubitteja on riittävästi ja tarkastelemme niiden avulla suoritettavien laskentatoimintojen mahdollisuuksia,” mikä paljastaa samankaltaisuuden yleiseen kryptografian ongelmaan, eli datan salaukseen, selitti Vincent Ulitzsch, tohtorikoulutuksen suorittanut opiskelija Berliinin teknillisessä yliopistossa.

Tämän jälkeen tiimi käytti Shorin algoritmia, kvanttialgoritmia, löytääkseen kokonaisluvun alkutekijät ja ratkaistakseen näiden optimointiongelmien alaluokan. Tämän avulla laskenta-aika ei enää räjähdä kaupunkien määrän kasvaessa. Se kasvaa vain polynomisesti, eli Nx:n, missä x on vakio. Näin saatu ratkaisu on myös laadullisesti paljon parempi kuin perinteisellä algoritmilla saatu likimääräinen ratkaisu.

Käyttämällä kryptografisia käsitteitä ja laskennallista oppimisteoriaa, tutkimus antaa “täysin konstruktiivisen todistuksen siitä, että kvanttitietokoneilla on superpolynominen etu perinteisiin tietokoneisiin nähden kombinaatiollisten optimointiongelmien likimääräisessä ratkaisemisessa.”

Tutkimus totesi lisäksi, että tutkimusryhmä on edistynyt merkittävästi tärkeässä kysymyksessä siitä, mitä potentiaaliset kvanttitietokoneet voivat tarjota kombinaatiollisten optimointiongelmien ratkaisujen likimääräiseen arviointiin, joilla on merkittäviä sosiaalisia ja taloudellisia vaikutuksia.

Tutkimus rahoitettiin Einstein Research Unitin, Berliinin Matematiikan Tutkimuskeskuksen (MATH+ Cluster of Excellence), BMBF:n (Hybrid), BMWK:n (EniQmA), Münchenin Quantum Valleyn ja DFG:n toimesta. Saksan liittovaltion opetus- ja tutkimusministeriö (BMBF) myönsi myös taloudellista tukea.

Kvanttitietokoneiden potentiaalin tutkiminen

Vaikka se on suuri saavutus, tämä ei ollut ensimmäinen kerta, kun kvanttitietokoneita on käytetty matkustavan myyjän ongelman ratkaisemiseen. On ollut monia tapauksia, joissa harrastajat ja tutkijat ovat pyrkineet ratkaisemaan ongelman hyödyntäen kvanttitietokoneita.

Joulukuussa 2022, paper ehdotti kvanttialgoritmia TSP:lle, joka perustuu Grover Adaptive Search (GAS) -menetelmään. GAS-viitekehyksen alla on vähintään kaksi perustavanlaatuista vaikeutta — ratkaisut eivät välttämättä ole toteutettavissa, ja nykyisten kvanttitietokoneiden kubittien määrä on hyvin rajallinen eikä täytä vähimmäisvaatimuksia, mikä rajoittaa kvantti‑algoritmien soveltamista kombinaatiollisiin optimointiongelmiin.

Tämän vuoksi paperi hiomasi Hamiltonian Cycle Detection (HCD) -orakelin, joka voi poistaa epäkäytännölliset ratkaisut automaattisesti algoritmin suorituksen aikana. He suunnittelivat myös “ankkuri‑rekisteri”-strategian kubittien käytön säästämiseksi, ottaen täysin huomioon kvanttitietokoneen käännettävyyden vaatimuksen ja voittaen vaikeuden, että käytetyt kubitit eivät ole yksinkertaisesti ylikirjoitettavissa tai vapautettavissa. Tämä mahdollisti, että tutkimus tarvitsi vain 31 kubittia, ja ratkaisun onnistumisprosentti oli 86,71 %.

Vuonna 2019, itse määrittelemä fysiikan harrastaja Joseph Cammidge kirjoitti kvantti‑annealointiprosessorin käytöstä, jonka avulla hän ratkaisi matkustavan myyjän ongelman seitsemälle kaupungille ja jolla on teoreettinen potentiaali ratkaista yhdeksän kaupunkia, kun teknologiset rajoitteet poistetaan.

Uusi laskentamenetelmä, kvantti‑annealing, on osoittanut potentiaalia ratkaista optimointiongelmia nopeammin kuin klassiset tekniikat. Sen teoria viittaa siihen, että kubitit saavuttavat optimaalisen matala‑energiatilan, kun ne ovat superkylmiä.

Kuitenkin vuonna 2021, tutkimus rahoitettuna Supply Chain Digital & Data Science, Johnson & Johnson (JNJ ) havaitsi, että kvantti‑annealeri pystyy käsittelemään vain enintään 8 solmua, ja sen suorituskyky on heikko sekä ajan että tarkkuuden suhteen verrattuna klassiseen ratkaisijaan.

Kvanttitietokoneiden käyttö TSP-ongelman ratkaisemiseen on jatkunut jo jonkin aikaa. Yli kaksi vuosikymmentä sitten, vuonna 2001, etsimässä aloitettiin tutkimus kvanttialgoritmista, joka ratkaisee ongelman.

Paperissa Buckley Hopper University of Alabamasta tarkasteli Groverin ja Shorin kvanttitietokonealgoritmeja. Hän totesi, että Groverin algoritmi tarjoaa vain neliöjuurisen parannuksen, mikä tarkoittaa, että se ei tee klassisesti ratkaisemattomasta ongelmasta ratkaistavan kvanttitietokoneella. Shorin algoritmin osalta Hopper havaitsi, että vaikka se voi muuttaa oletettavasti ratkaisemattoman alkutekijäongelman ratkaistavaksi kvanttikoneessa, se soveltuu vain hyvin erityiseen ongelmatyyppiin.

Kaiken kaikkiaan Hopper “ei löytänyt tyydyttävää tulosta algoritmille, joka laskisi matkustavan myyjän ongelman likimääräisiä ratkaisuja.”

Muutama vuosi sen jälkeen Institute of Electrical and Electronics Engineers (IEEE) esitteli uuden algoritmin ongelman ratkaisemiseksi, joka sai inspiraationsa sekä geneettisistä algoritmeista että kvanttitietokoneista. IEEE havaitsi, että ehdotetun algoritmin soveltamisesta joihinkin matkustavan myyjän ongelman tapausten ratkaisuihin saadaan huomattavasti parempia tuloksia kuin perinteisillä geneettisillä algoritmeilla.

Klikkaa tästä oppiaksesi kvanttitietokoneiden nykytilasta.

Kvanttitietokoneiden kanssa työskentelevät yritykset

Katsotaanpa nyt muutamia nimiä, jotka työskentelevät kvanttitietokoneiden tutkimus- ja kehitystyön parissa:

#1. IBM

International Business Machines Corporation (IBM ) toimii laajalla alalla, mukaan lukien tekoäly, pilvipalvelut, IT, asiakasrahoitus ja kaupallinen rahoitus. Teknologiavalmistaja on myös mukana kvanttitietokoneissa IBM Quantum Platformin kautta, joka tarjoaa julkista ja premium-pääsyä sen pilvipohjaisiin kvanttitietokonepalveluihin. Näihin kuuluvat IBM:n prototyyppiset kvanttiprosessorit, kvanttialgoritmien opetusohjelmat ja interaktiivinen oppikirja.

Viime aikoina IBM:n tutkijat ilmoittivat että he ovat askeleen lähempänä esteen voittamista, joka avaa kvanttitietokoneiden mullistavan potentiaalin. Tämän vuoksi he esittelivät uuden kvantti‑virheenkorjauskoodin, jonka he sanovat olevan noin kymmenen kertaa tehokkaampi kuin aiemmat menetelmät.

Viime vuoden lopulla yritys lanseerasi myös kvanttitietokoneen nimeltä Condor, jossa on 1 121 superjohtavaa kubittia, jotka on järjestetty hunajakenno‑kuvioon. IBM esitteli myös IBM Quantum System Two -järjestelmän, ensimmäisen modulaarisen kvanttitietokoneen ja kvanttikeskeisen supertietokonearkkitehtuurin, joka on skaalautuva ja siten voidaan päivittää seuraavien viiden vuoden aikana julkaistavilla siruilla.

Markkina-arvolla 175 miljardia dollaria IBM:n osakkeet käyvät hintaan 190,86 $, nousua 16,66 % vuoden alusta (YTD). IBM on raportoitu liikevaihdolla (TTM) 61,86 miljardia dollaria, EPS (TTM) 8,03, P/E (TTM) 23,76 ja ROE (TTM) 33,36 %. Yritys maksaa osinkotuoton 3,48 %.

#2. D-Wave Systems

Tämä kvanttitietokoneyritys kehittää ja toimittaa siihen liittyviä järjestelmiä, ohjelmistoja ja palveluita. Sen tuotteisiin kuuluvat The Leap ja The Advantage, ja se tarjoaa kvanttisovelluksia aikataulutukseen, logistiikkaan, lääkekehitykseen, valmistusprosesseihin ja muuhun.

Tämän kuukauden alussa D-Wave ilmoitti, että kvanttikoneet voivat nyt ratkaista todellisiin sovelluksiin liittyviä ongelmia nopeammin kuin mikään tavallinen tietokone. Aiemmin tänä vuonna yritys ilmoitti kvanttitietokoneesta, jossa on 1 200 kubittia, 10 000 kytkintä ja 20‑kertainen nopeampi ratkaisuajankohta vaikeissa optimointiongelmissa.

Yrityksen osakkeet käyvät tällä hetkellä hintaan 1,86 $, nousua 138,6 % vuoden alusta (YTD), markkina-arvo 267 miljoonaa dollaria. Se raportoi 8,247 miljoonaa dollaria myyntiä (TTM), -0,66 EPS (TTM) ja -3,19 P/E (TTM), ja ilmoitti yli 20 %:n myynnin kasvusta sekä Q4- että vuoden 2023 lopullisissa tuloksissa, kun taas varauskasvu oli 34 % ja 89 % vastaavasti.

Mielenkiintoista on, että yrityksen toimitusjohtaja, tohtori Alan Baratz, ilmoitti yrityksen vauhdin, viitaten monivuotiseen strategiseen kumppanuuteen Zapata AI:n kanssa, 1 200+ kubittisen Advantage2 -prototyypin esittelyyn, yhteisyrityksiin NEC Australia:n ja Deloitte Canada:n kanssa sekä entisen Homeland Security -ministerin Kirstjen Nielsenin nimittämiseen hallituksen jäseneksi.

Yhteenveto

Kvanttitietokoneiden markkinoiden odotetaan saavuttavan 6,5 miljardia dollaria vuonna 2028, ja niiden potentiaali ratkaista matkustavan myyjän ongelma (TSP) vaikuttaa useisiin teollisuudenaloihin, kuten valmistukseen, logistiikkaan, toimitusketjun hallintaan, verkkokauppaan, kuljetukseen ja tutkimukseen. Lopulta se voi tuottaa merkittäviä hyötyjä, erityisesti tuottavuuden lisäämistä, kulujen leikkaamista ja innovaation edistämistä eri sektoreilla.

Klikkaa tästä saadaksesi listan viidestä parhaasta kvanttitietokoneyrityksestä.