Kvanttialgoritmi

Kvanttialgoritmi  on algoritmi , joka on suunniteltu toimimaan kvanttitietokoneessa .

Perusperiaatteet

Kvanttialgoritmi on klassinen algoritmi, joka määrittää sekvenssin yhtenäisiä operaatioita (portit tai portit) ja ilmoittaa, mille qubiteille ne on suoritettava. Kvanttialgoritmi määritellään joko tällaisten komentojen sanallisen kuvauksen muodossa tai niiden graafisen merkinnän avulla porttijärjestelmän (kvanttiporttitaulukko) muodossa.

Kvanttialgoritmin tulos on todennäköisyys [1] . Algoritmin operaatioiden määrän pienestä kasvusta johtuen voidaan mielivaltaisesti nostaa oikean tuloksen saamisen todennäköisyys yhteen.

Ongelmajoukot, jotka voidaan ratkaista kvanttitietokoneella ja klassisella tietokoneella, ovat samat. Kvanttitietokone ei siis lisää algoritmisesti ratkaistavien ongelmien määrää. Kvanttitietokoneen käyttötarkoitus on, että se voi ratkaista joitakin ongelmia paljon nopeammin kuin mikään klassisista. Tätä varten kvanttialgoritmin on generoitava ja käytettävä kietoutuneet kvanttitilat laskennan aikana (katso Kvanttisuperpositio ja Kvanttikietoutuminen ).

Mikä tahansa kvanttialgoritmilla ratkaistava ongelma voidaan ratkaista myös klassisella tietokoneella laskemalla suoraan eksponentiaalimittaisia ​​unitaarisia matriiseja, jolloin saadaan kvanttitilojen eksplisiittinen muoto. Erityisesti ongelmat, joita ei voida ratkaista klassisilla tietokoneilla (kuten pysäytysongelma ), pysyvät ratkaisemattomina myös kvanttitietokoneissa. Mutta tällainen suora simulointi vaatii eksponentiaalista aikaa, ja siksi on mahdollista nopeuttaa joitain klassisia algoritmeja kvanttitietokoneella [2] .

Kvanttitietokoneen kiihtyvyys ei liity prosessorin kellotaajuuteen. Se perustuu kvanttirinnalleisuuteen. Yksi kvanttilaskennan vaihe tekee paljon enemmän työtä kuin yksi askel klassisessa laskennassa. Olisi kuitenkin virhe rinnastaa kvanttilaskenta rinnakkaiseen klassiseen laskemiseen. Esimerkiksi kvanttitietokone ei pysty ratkaisemaan laskentatehtävää nopeammin kuin missä on deterministisen klassisen laskenta-algoritmin  käyntiaika (katso [3] ), kun taas ei-deterministinen klassinen algoritmi ratkaisee sen ajassa . Mutta ei-deterministinen klassinen algoritmi vaatii eksponentiaalista muistiresurssia, eli se ei ole fyysisesti toteutettavissa, kun taas kvanttialgoritmi ei ole ristiriidassa tunnettujen luonnonlakien kanssa.

Kvanttilaskenta on erityinen prosessi. Se käyttää erityistä fyysistä resurssia: kvanttikietoisia tiloja , mikä mahdollistaa joissain tapauksissa uskomattomien hyötyjen saavuttamisen ajassa. Tällaisia ​​tapauksia kutsutaan klassisen laskennan kvanttikiihtyvyydeksi.

Kvanttikiihtyvyyden tapaukset klassisten algoritmien yleisen massan taustalla ovat erittäin harvinaisia ​​(katso [4] ). Tämä ei kuitenkaan vähennä kvanttilaskennan perustavaa laatua olevaa merkitystä, koska ne pystyvät perusteellisesti nopeuttamaan raa'an voiman tehtävien suorittamista.

Kvanttikiihtyvyyden perusmallit

Kvanttialgoritmien kiihdyttämien ongelmien päätyypit ovat raakavoima-ongelmat. Ne voidaan jakaa 2 pääryhmään:

1. Monimutkaisten järjestelmien dynamiikan mallintamisen ongelmat (Feynmanin alkuperäinen idea) ja
2. Matemaattiset tehtävät, jotka tiivistyvät vaihtoehtojen luetteloon:
   1. Yleinen luettelointitapaus: Groverin kaavio ja sen muunnelmat sekä
   2. Piilojaksojen etsimisen ongelmat: Shorin menetelmä nopean kvantti-Fourier-muunnoksen ja sen analogien käyttämiseksi.

Tyyppiä 1) edustaa Zalka-Wiesner-algoritmi hiukkasten kvanttijärjestelmien unitaaridynamiikan mallintamiseen lähes reaaliajassa ja lineaarisella muistilla. Tämä algoritmi käyttää kvantti-Fourier-muunnoksen Shor-mallia.

Tyyppi 2) esitetty:

• Groverin algoritmi yleiseen hakuongelmaan ja sen jatkuvaan ja adiabaattiseen muunnelmaan sekä Groverin mallia käyttävät algoritmit: rakennehaku (Fari, Gutman), äärimmäinen hakualgoritmi (Hoyer jne.) ja vastaavien rivien haku tietokannasta (Ambainis) ,
• Shorin algoritmi kokonaislukujen faktorointiin, Abrams-Lloydin algoritmi jaksojen havaitsemiseen, Kitaevin algoritmi piilotettujen aliryhmien määrittämiseen jne.

Tyyppi 1) on eniten kiinnostava kvanttitietokoneen lisäsovellusten kannalta.

Luokitus

Kvanttialgoritmien luokittelu voidaan suorittaa algoritmin käyttämien kvanttimuunnosten tyypin mukaan. Yleisesti käytettyjä muunnoksia ovat: en:phase kick-back , vaiheestimointi , en:quantum Fourier-muunnos , en:quantum walk , en:amplitudivahvistus , en:topologinen kvanttikenttäteoria . Kvanttialgoritmit on myös mahdollista ryhmitellä niiden ratkaisemien ongelmien tyypin mukaan. [5]

Tunnetut algoritmit

• Shorin algoritmi
• Groverin algoritmi
• Deutsch-Yozhi algoritmi

Katso myös

• kvanttitietokone
• kvanttiohjelmointi
• Kvanttilaskennan aikajana
• Kvanttiavainten jakelu
• Luettelo algoritmeista
• BQP luokka

Muistiinpanot

1. ↑ “Satunnaisuus laskennallisena resurssina” Arkistoitu 29. lokakuuta 2017 Computerra Wayback Machinessa No. 10, 18. maaliskuuta 2002 “Kvanttialgoritmit muistuttavat todennäköisyyspohjaisia. Ensinnäkin tuloksen epävarmuus.
2. ↑ "Kvanttitietokoneet", PhD L. Fedichkin, FTI RAS. Nizh, 2001 nro 01 "Kvanttitietokoneiden käyttöönotto ei johda algoritmisesti ratkaisemattomien klassisten ongelmien ratkaisuun, vaan vain nopeuttaa joitain laskelmia"
3. ↑ Juri Ozhigov, Lower Bounds of Quantum Search for Extreme Point, Proc. Roy, Soc. London. A455 (1999) 2165-2172 [1]
4. ↑ Juri Ozhigov, Quantum Computers Speed ​​​​Up Classical todennäköisyydellä nolla, Chaos Solitons Fractals 10 (1999) 1707-1714 [2]
5. ↑ Childs, Andrew M; Wim van Dam. Kvanttialgoritmit algebrallisiin ongelmiin  (neopr.)  // 0812.0380. - 2008. - 2. joulukuuta.

Linkit

• Stephen Jordan, Algebralliset ja lukuteoreettiset algoritmit  - kattava kvanttialgoritmien luettelo, NIST, 2013

Sanakirjat ja tietosanakirjat	iso kiinalainen