Seuraava artikkeli auttaa sinua: 6 kvanttialgoritmia, jotka muuttavat tietojenkäsittelyn ikuisesti
Olemme tietojenkäsittelyn uuden aikakauden kynnyksellä, jossa tietojenkäsittelyn perusyksiköt eivät ole enää klassiset bitit vaan kvanttibitit, tai qubits. Tämä muutos avaa valtavan, uudenlaisen mahdollisuuden ratkaista monimutkaisia matemaattisia ongelmia, joita klassiset tietokoneet eivät pysty ratkaisemaan tehokkaasti.
Esimerkkinä mainittakoon, että Googlen kvanttitietokoneiden sanotaan olevan 158 miljoonaa kertaa nopeampia kuin nykypäivän kehittynein supertietokone – mikä tarkoittaa, että tehtävä, jonka Boolen logiikkatietokoneilla kestää kymmenen vuotta, nämä tietokoneet pystyvät suorittamaan. kolmessa sekunnissa.
Lähitulevaisuudessa kvanttilaskennan vaikutukset – jotka kattavat useat eri toimialat, kuten rahoituksen, logistiikan ja kryptografian – ovat ilmeisiä kaikille.
Tässä on luettelo suosituimmista kvanttialgoritmeista, jotka korostavat kvantin merkittävää vaikutusta klassiseen maailmaan:
Shorin algoritmi
Koko tietoturvajärjestelmämme perustuu olettamukseen, että tuhannen tai useamman numeron kokonaislukujen laskeminen on käytännössä mahdotonta. Se oli siihen asti, kunnes Peter Shor vuonna 1995 ehdotti, että kvanttimekaniikka sallii tekijöiden jakamisen polynomiajassa klassisten algoritmien avulla saavutetun eksponentiaalisen ajan sijaan.
Klassisten factoring-algoritmien, kuten yleisen numerokentän seulan (GNFS) suoritusaika kasvaa eksponentiaalisesti tekijöiden kokonaisluvun numeroiden määrän myötä. Shorin algoritmi puolestaan on kvanttialgoritmi kokonaislukujen laskemiseen, jolla on polynominen ajoaika, mikä tarkoittaa, että kokonaisluvun tekijöihin kuluva aika kasvaa vain polynomisesti kokonaisluvun numeroiden määrän kanssa.
Tässä on yksi variantti Aleksei Kitaevin Shorin algoritmista, joka vähentää tekijöiden jakamisen suorittamiseen tarvittavien kubittien määrää, mutta pystyy kuitenkin kellottamaan suoritusajan suunnilleen d^3:n paikkeilla.
Voit tarkistaa Qiskitin toteutuksen täältä.
Groverin algoritmi
Intialais-amerikkalaisen tietojenkäsittelytieteilijän kehittämä Grover’s Algorithm on laajalti tunnustettu yhdeksi tärkeimmistä kvanttialgoritmeista Shorin algoritmin jälkeen. Sen ensisijainen käyttö on nopeuttaa jäsentämättömiä hakuongelmia neliöllisesti, mutta se toimii myös arvokkaana työkaluna tai aliohjelmana, jolla saadaan aikaan neliöllisiä ajonaikaisia parannuksia monille muille algoritmeille.
Kuvittele, että sinulla on N kohteen luettelo ja yrität löytää luettelosta yhden ainutlaatuisen kohteen. Klassisen tietokoneen pitäisi tarkistaa keskimäärin N/2 kohdetta luettelosta löytääkseen yksilöllisen kohteen, ja pahimmassa tapauksessa sen pitäisi tarkistaa kaikki N kohdetta. Kvanttilaskentaa käytettäessä Groverin amplitudivahvistus voi kuitenkin merkittävästi vähentää vaiheiden määrää karkeasti arvoon √N, mikä on neliöllinen nopeus verrattuna klassisiin algoritmeihin.
Lähde: IBM QuantumVoit tarkistaa Qiskitin toteutuksen täältä.
Deutsch-Jozsa -algoritmi
Deutsch-Jozsa-algoritmi on kvanttialgoritmi, joka on suunniteltu ratkaisemaan “Deutsch-Jozsa-ongelma”. Tämä ongelma sisältää sen määrittämisen, onko tietty Boolen funktio “vakio” (eli palauttaa saman lähdön kaikille mahdollisille syötteille) vai “balansoitu” (eli palauttaa eri lähdöt ainakin yhdelle tuloparille) vähimmällä määrällä kyselyitä.
varten n bittejä syötteinä, klassinen algoritmi vaatii vähintään kaksi kutsua maksimiarvoon 2^(n-1)+1 varmistaakseen, onko tietty funktio vakio vai balansoitu, kun taas kvanttitietokone voi ratkaista tämän käyttämällä vain yhtä kutsua funktiolle. f(x).
Voit tarkistaa Qiskitin toteutuksen täältä.
Bernstein-Vazirani-algoritmi
Kuten Deutsch–Jozsa-ongelma, myös Bernstein–Vazirani-algoritmi ratkaisee tietyn mustan laatikon ongelman. Ongelma liittyy löytämiseen s funktiossa f(x) = s . x, missä s on jokin tuntematon merkkijono ja . tarkoittaa bittikohtaista tuloa (eli AND) -toimintoa.
Annettu syöte xklassisen algoritmin pitäisi kutsua funktio f(x) useita kertoja ja käytä tuloksia määrittääksesi bitit s yksi kerrallaan, vaatii n kutsuu funktiota koko merkkijonon palauttamiseksi. Kvanttitietokone voi kuitenkin ratkaista ongelman 100 %:n varmuudella vain yhden funktion kutsun jälkeen f(x).
Voit tarkistaa Qiskitin toteutuksen täältä.
Simonin algoritmi
Simon’s oli ensimmäinen algoritmi, joka osoitti eksponentiaalista nopeutta verrattuna parhaaseen klassiseen algoritmiin tietyn ongelman ratkaisemisessa.
Käsillä oleva ongelma liittyy funktioon f(x) sillä on vain kaksi tulosta – joko se kartoittaa jokaisen yksilöllisen tulon yksilölliseen ulostuloon (yksi yhteen) tai yhdistää kaksi erillistä tuloa yhdeksi ainutlaatuiseksi ulostuloksi (kaksi yhteen). Lisäksi on tuntematon merkkijono s joka on sellainen, että kaikille syötemerkkijonoille xf(x) on yhtä suuri kuin f(x⊕s).
Jos arvo s on nollasta poikkeava, niin funktio f on kaksi yhteen, kun taas milloin s on nollamerkkijono, funktio f on yksi yhteen. Siksi tavoitteena on määrittää, onko toiminto f on yksi yhteen tai kaksi yhteen yksinkertaisesti etsimällä salainen merkkijono s.
Klassisesti arvo s löytyy funktiolle f varmuudella tarkistamalla jopa 2^(n/2) funktiokutsua. Mutta kvantissa käyttämällä eksponentiaalisesti vähemmän kyselyjä – vain hieman enemmän kuin n puhelut – ratkaisu 100 % varmuudella löytyy.
Voit tarkistaa Qiskitin toteutuksen täältä.
Kvanttifaasiestimointi (QPE) -algoritmi
QPE on tärkeä aliohjelma, joka toimii useiden kvanttialgoritmien keskeisenä rakennuspalikkana. Algoritmi pohjimmiltaan arvioi unitaarioperaattorin ominaisarvon vaiheen. Toisin sanoen annettu yhtenäinen operaattori U ja ominaisvektori |ψ⟩ siten, että U|ψ⟩ = e^(2πiθ)|ψ⟩, missä θ on tuntematon vaihekulma, QPE:n tavoitteena on estimoida θ.
Sitä käytetään monissa sovelluksissa, kuten kvanttisimulaatiossa, kvanttikemiassa ja optimoinnissa.
Voit lukea siitä lisää täältä.
