Shorin algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 22. kesäkuuta 2021 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Shorin algoritmi on kvanttifaktorointialgoritmi (joka hajottaa luvun alkutekijöiksi), jonka avulla voit hajottaa luvun ajassa käyttämällä loogisia kubitteja . $M$ $O(\log ^{3}M)$ $O(\log M)$

Peter Shor kehitti Shorin algoritmin vuonna 1994 . Seitsemän vuotta myöhemmin, vuonna 2001 , ryhmä IBM :n asiantuntijoita osoitti sen suorituskyvyn . Luku 15 kerrottiin 3:lla ja 5:llä käyttämällä kvanttitietokonetta 7 qubitillä .

Tietoja algoritmista

Algoritmin merkitys on siinä, että sen avulla (käytettäessä useiden tuhansien loogisten kubittien kvanttitietokonetta) on mahdollista murtaa julkisen avaimen salausjärjestelmät . Esimerkiksi RSA käyttää julkista avainta , joka on kahden suuren alkuluvun tulos. Yksi tapa rikkoa RSA-salaus on löytää tekijät. Riittävän suurilla se on lähes mahdotonta tehdä tunnetuilla klassisilla algoritmeilla . Tunnetuimmat klassiset deterministiset todistetut faktorointialgoritmit, kuten Shanksin neliömuotomenetelmä ja Pollard-Strassen-algoritmi vaativat järjestysaikaa. Myös Shanksin neliömuotomenetelmä voi toimia järjestysajassa, jos Riemannin hypoteesi on totta . Probabilistisista algoritmeista tekijöiden jakamisen johtajana on erityinen lukukenttäseulamenetelmä , joka pystyy löytämään alkujakajan todennäköisyydellä 1/2 subeksponentiaalisessa ajassa. Shorin algoritmi kvanttitietokoneiden kykyjä käyttäen pystyy jakamaan luvun. ei vain polynomiajassa, vaan ajassa, joka ei ole paljon suurempi kokonaisluvun kertolaskuaika (eli melkein yhtä nopea kuin itse salaus). Siten skaalautuvan kvanttitietokoneen käyttöönotto tekee lopun suurimmasta osasta nykyaikaista kryptografista suojausta. Tämä ei koske vain RSA-järjestelmää, joka perustuu suoraan tekijöiden jakamisen monimutkaisuuteen, vaan myös muista vastaavista järjestelmistä, joita kvanttitietokone voi murtaa samalla tavalla. $M,$ $M.$ $M$ $M^{1/4}.$ $M^{1/5}$ $\exp \left(\left({\frac {32}{9}}\cdot \log M\right)^{1/3}\cdot (\log \log M)^{2/3} \oikea).$

Shorin algoritmilla on todennäköisyyspohjainen luonne. Ensimmäinen satunnaisuuden lähde on rakennettu klassiseen todennäköisyyteen perustuvaan faktorisoinnin pelkistykseen jonkin funktion periodin löytämiseksi. Toinen lähde tulee tarpeesta tarkkailla kvanttimuistia, joka antaa myös satunnaisia tuloksia [1] .

Kuinka Shorin algoritmi toimii

Shorin algoritmin perusta: kvanttitietokoneiden tietoyksiköiden - kubittien - kyky ottaa useita arvoja samanaikaisesti ja olla " kvanttikietoutumisessa ". Siksi se mahdollistaa laskelmien suorittamisen kubittien taloudellisuuden olosuhteissa. Shor-algoritmin toimintaperiaate voidaan jakaa kahteen osaan: ensimmäinen on klassinen faktorisoinnin pelkistys tietyn funktion periodin löytämiseksi, toinen on tämän funktion jakson kvanttilöytö. Päästää:

M

- luku, jonka haluamme kertoa (se ei saa olla parittoman luvun kokonaislukupotenssi);

N

- käytetyn muistirekisterin koko (lukuun ottamatta dumppia). Tämän muistin bittikoko on noin 2 kertaa suurempi kuin . Tarkemmin sanottuna ;

n=\log _{2}N

M

M^{2}<N=2^{n}<2M^{2}

t

on satunnaisparametri siten, että ja (missä on suurin yhteinen jakaja ).

1<t<M

\operaattorin nimi {gcd} (t,M)=1

{\näyttötyyli \operaattorin nimi {gcd} }

Huomaa, että , , ovat kiinteät. Shorin algoritmi käyttää tavanomaista tapaa pelkistää laajennusongelma ongelmaksi löytää funktion jakso satunnaisesti valitulle luvulle [2] . $t$ $N$ $M$ $r$ $t$

Algoritmin klassinen osa

Minimi , joka on modulo - järjestys $r$ $t^{r}\equiv 1\ {\mbox{mod}}\ M,$ $t$ $M.$

Järjestys on funktion jakso jossa $r$ $f(x)=t^{x}\ {\mbox{mod}}\ M,$ $x=0,1,2,...,N-1.$

Jos voidaan laskea tehokkaasti funktiona , niin voidaan löytää oma jakaja ajassa, jota rajoittaa polynomi : n todennäköisyydellä mille tahansa kiinteälle . $r$ $t$ $M$ $\log _{2}M$ $\geqslant 1-M^{{-m}}$ $m$

Oletetaan, että tietylle ajanjaksolle on tasainen ja täyttää ehdon $t$ $r$ $(r\equiv 0\ {\mbox{mod}}\ 2)$

t^{\frac {r}{2}}\not \equiv -1\ {\mbox{mod}}\ M.

Sitten

\operaattorin nimi {gcd} (t^{\frac {r}{2}}+1,M)

— oma jakaja Funktio on laskettavissa polynomiajassa.

M.

{\näyttötyyli \operaattorin nimi {gcd} }

Tämän ehdon täyttymisen todennäköisyys missä on erilaisten parittomien alkujakajien määrä , siis tässä tapauksessa. Siksi hyvä arvo löytyy todennäköisesti yrityksissä. Pisin laskenta yhdellä yrityksellä on laskutoimitus [3] [4] . $\geqslant 1-{\frac {1}{2^{k-1))},$ $k$ $M$ $\geqslant {\frac {1}{2}}$ $t$ $\geqslant 1-M^{{-m}}$ $O(\log M)$ $t^{\frac {r}{2}}$

Algoritmin kvanttiosa

Algoritmin kvanttiosan toteuttamiseksi laskentapiiri on kvanttirekisteri ja . Aluksi jokainen niistä koostuu joukosta kubitteja nollassa loogisessa tilassa $2$ $X$ $Y$ $|0\rangle .$

Rekisteriä käytetään funktion argumenttien sijoittamiseen Rekisteriä (apu) käytetään sijoittamaan funktion arvot laskettavalla jaksolla . $X$ $x$ $f(x).$ $Y$ $f(x)$ $r$

Kvanttilaskenta koostuu 4 vaiheesta [5] :

Ensimmäinen askel . Ensimmäisessä vaiheessa käyttämällä Walsh-Hadamard-operaatiota, joka on qubitin muunnos operaattorilla, rekisterin alkutila muunnetaan kaikkien loogisten tilojen tasatodennäköiseksi superpositioksi . Toinen rekisteri pysyy tilassa. Tämän seurauksena kahden rekisterin järjestelmälle saadaan seuraava tila: $H={\frac {1}{\sqrt {2))}{\begin{bmatrix}1&1\\1&-1\end{bmatrix)),$ $|0\rangle \$ $X$ $N$ $Y$ $|0\rangle .$ ${\frac {1}{\sqrt {N}}}\sum \limits _{x=0}^{N-1}|x,0\rangle .$

Toinen vaihe . Antaa olla unitaarinen muunnos , joka muuttuu Toisessa vaiheessa, unitaarinen muunnos sovelletaan kahden rekisterin järjestelmään. Tästä seuraa järjestelmän tila: $U_{f}$ $|x,0\kulma$ $|x,f(x)\rangle .$

{\frac {1}{\sqrt {N))}\sum \limits _{x=0}^{N-1}|x,0\rangle \quad {\xrightarrow {U_{f)) }\quad {\frac {1}{\sqrt {N}}}\sum \limits _{x=0}^{N-1}|x,t^{x}\ {\mbox{mod}}\ M\rangle ,

eli molempien rekisterien tilojen välille muodostuu tietty suhde.

Kolmas vaihe . Kvantti-Fourier-muunnos on muodon -ulotteisen tilavektorin kuvaaman kvanttirekisterin tilan unitaarinen muunnos toiseen tilaan . $N$ $\sum \limits _{x=0}^{N-1}f(x)|x\rangle ,$ $\sum \limits _{k=0}^{N-1}{\tilde {f}}(k)|k\rangle \ :$

\mathrm {QFT} _{N}:\sum \limits _{x=0}^{N-1}f(x)|x\rangle \ \Rightarrow \sum \limits _{k=0} ^{N-1}{\tilde {f}}(k)|k\rangle \ ,

jossa Fourier-muunnoksen amplitudilla on muoto

f(x)

{\tilde {f}}(k)={\frac {1}{N}}\sum \limits _{x=0}^{N-1}\exp(2\pi \ i\ kx /N)f(x).

Kaksiulotteisessa tasossa Fourier-muunnos vastaa koordinaattiakselien kiertoa 90°, mikä johtaa asteikon muuntamiseen asteikolla . Kolmannessa vaiheessa Fourier-muunnos suoritetaan ensimmäisen rekisterin tilaan, ja se selviää

x,k

x

k

{\frac {1}{N}}\sum \limits _{x=0}^{N-1}\sum \limits _{k=0}^{N-1}\exp(2\ pi \ i\ kx/N)|k,t^{x}\ {\mbox{mod}}\ M\rangle .

Neljäs vaihe . Neljännessä vaiheessa ensimmäinen rekisteri mitataan suhteessa näkymän ortogonaaliseen projektioon : $X$

|0,0\rangle \otimes I,\quad |1,1\rangle \otimes I,\quad \dots ,\quad |N-1,N-1\rangle \otimes I,

missä on identiteettioperaattori toisen rekisterin Hilbert - avaruudessa .

minä

Y

Tämän seurauksena se osoittautuu todennäköisyydellä [6] $|k,t^{k}\ {\mbox{mod}}\ M\rangle \$

\left|{\frac {1}{N}}\sum \limits _{x:\ t^{x}\equiv t^{k}\ {\mbox{mod}}\ M}\exp (2\pi \ i\ kx/N)\oikea|^{2}.

Loput ajosta suoritetaan perinteisellä tietokoneella:

Etsi paras likiarvo (alhaalta) kohtaan nimittäjällä ${\frac {k}{N}}\$ $r'<M<{\sqrt {N}}:$ $\left|{\frac {k}{N}}\ -{\frac {d'}{r'}}\right|<{\frac {1}{2N}}.$

Kokeillaan roolissa : $r'$ $r$
- Jos , niin pitäisi laskea $r'\equiv 0\ {\mbox{mod}}\ 2$ $\operaattorin nimi {gcd} (t^{\frac {r'}{2}}\pm 1,M).$
- Jos se on pariton tai parillinen, mutta omaa jakajaa ei löydy, sinun tulee toistaa ajo uudelleen samalla . Epäonnistumisen sattuessa muuta algoritmia ja aloita uusi ajo [3] [4] . $r'$ $r'$ $M$ $O(\log \log M)$ $t$ $t$

Jossain määrin funktion jakson määrittäminen Fourier-muunnoksen avulla on samanlaista kuin kidehilavakioiden mittaaminen röntgen- tai neutronidiffraktiolla. Jakson määrittämiseksi ei tarvitse laskea kaikkia arvoja. Tässä mielessä ongelma on samanlainen kuin Deutsch - tehtävä, jossa ei ole tärkeää tietää kaikkia funktion arvoja, vaan vain osa sen arvoista. ominaisuudet [6] . $r,$ $f\left(x\right).$

Funktion jakson löytäminen algoritmista

Antaa olla funktio, jonka jakso on tuntematon $F$ $r:$

F:|x,0\rangle \ \rightarrow |x,f(x)\rangle \f:Z\rightarrow Z_{2^{m}}\ r<2^{n}.

Jakson määrittämiseksi tarvitaan kaksi rekisteriä, joissa on koot ja kubitit, joiden on aluksi oltava tilassa $r,$ $2n$ $m$ $|0,0\rangle .$

Ensimmäisessä vaiheessa suoritetaan ensimmäisen rekisterin kaikkien kantavektoreiden yksipuolinen superpositio käyttämällä seuraavan muotoista operaattoria: $U$

U|0,0\rangle \ =\sum \limits _{i=0}^{N-1}c_{i}|i,0\rangle \

, missä ja

|c_{i}|={\frac {1}{\sqrt {N))}

N=2^{2n}.

Tässä käytetään Hadamardin pseudomuunnosa . Nykyiseen tilaan sovellettaessa saamme: $H_{1}={\begin{bmatrix}2&1\\1&1\end{bmatrix}}$ $F$

|\psi \rangle =FH_{1}|0,0\rangle =F{\frac {1}{2^{n))}\sum \limits _{i=0}^{N-1 }|i,0\rangle ={\frac {1}{2^{n}}}\sum \limits _{i=0}^{N-1}|i,f(i)\rangle .

Toisen rekisterin mittaaminen tuloksella mihin johtaa tilan $k=f(s),$ $s<r,$

|\psi '\rangle =\sum \limits _{j=0}^{[N/r]-1}c_{j}'|rj+s,k\rangle ,\qquad

missä

c_{j}'=\left[{\frac {N}{r}}\right]^{-1/2}.

Tilan mittauksen jälkeen ensimmäinen rekisteri koostuu vain kantavektoreista, joiden muoto on sellainen, että sillä on siis diskreetti homogeeninen spektri. Pistettä tai sen kerrannaista on mahdotonta saada suoraan mittaamalla ensimmäistä rekisteriä, koska tässä on satunnaismuuttuja. Tässä käytetään muodon diskreettiä Fourier-muunnosta $|\psi '\rangle$ $|rj+s\rangle$ $f(rj+s)=f(s)$ $j.$ $r$ $s$

\mathrm {DFT:} |x\rangle \rightarrow {\frac {1}{\sqrt {N))}\sum \limits _{y=0}^{N-1}e^{{\ frac {2\pi i}{N}}xy}|y\rangle

rekisterissä, koska spektrin todennäköisyys muunnetussa tilassa on muuttumaton siirtymän suhteen (vain vaiheet voidaan muuntaa, ei amplitudien absoluuttisia arvoja).

|\psi ''\rangle =\mathrm {DFT} |\psi '\rangle =\sum \limits _{i=0}^{N-1}c_{i}''|i,k\ range.

c_{i}''={\frac {\sqrt {r}}{N}}\sum \limits _{j=0}^{p-1}\exp \left({\frac {2 \pi i}{N}}i(jr+s)\right)={\frac {\sqrt {r}}{N}}e^{\varphi _{i}}\sum \limits _{j= 0}^{p-1}\exp \left({\frac {2\pi i}{N}}ijr\oikea),

missä ja

\varphi _{i}=2\pi i{\frac {is}{N}}\quad

\quad p=\left[{\frac {N}{r}}\right].

Jos on monikerta , niin jos on monikerta ja muuten. Vaikka ei potenssi 2, spektri näyttää yksittäisiä huippuja, joiden piste on koska $N=2^{2n}$ $r$ $c_{i}''={\frac {e^{\varphi _{i))}{\sqrt {r))},$ $i$ ${\frac {N}{r)),$ $c_{i}''=0$ $r$ $|\psi ''\rangle$ ${\frac {N}{r)),$

\lim _{n\to \infty }{\frac {1}{n}}\sum \limits _{k=0}^{n-1}e^{2\pi ik\alpha }={\begin {cases}1\ \ ,\alpha \in Z\\0\ \ ,\alpha \notin Z\\\end{cases}}

Ensimmäisessä rekisterissä käytetään kubitteja, kun koska tämä takaa vähintään alkiot annetussa summassa ja siten huippujen leveys on luokkaa $2n$ $r<2^{n},$ $2^{n}$ $O(1).$

Jos nyt lasketaan ensimmäinen rekisteri, saadaan arvo, joka on lähellä kohtaa Se voidaan kirjoittaa muodossa Tämä tiivistyy siihen, että löydetään likiarvo missä tietylle binääripisteen määrälle . Tämän ongelman ratkaisemiseksi käytetään jatkuvia murtolukuja. $c,$ ${\frac {\lambda N}{r)),$ $\lambda \in Z_{r}.$ ${\frac {c}{N}}=c\cdot 2^{-2n}\approx {\frac {\lambda }{r)).$ ${\frac {a}{b)),$ $a,b<2^{n},$ $c\cdot 2^{-2n}.$

Koska rationaaliluvun muoto ei ole yksiselitteinen, u määritellään ikään kuin todennäköisyys, että sekä luvut että ovat alkulukuja, on suurempi kuin siksi, jotta onnistumisen todennäköisyys olisi lähellä yhtä, tarvitaan vain yrityksiä [7] [5] . $\lambda$ $r$ ${\frac {a}{b}}={\frac {\lambda }{r)),$ $\operaattorin nimi {gcd} (\lambda ,r)=1.$ $\lambda$ $r$ ${\frac {1}{\ln r)),$ $Päällä)$

Diskreetti logaritmi

Toinen matemaattinen ongelma, diskreetti logaritmi , jota usein käytetään luomaan epäsymmetrisiä salausjärjestelmiä, on myös haavoittuvainen Shorin samassa artikkelissa ehdottaman kvanttialgoritmin suhteen [8] .

Katso myös

kvanttitietokone

Muistiinpanot

↑ Beckman, Chari, Devabhaktuni et ai., 1996 .
↑ Valiev, 2004 , s. 86-92.
↑ 12 Feynman , 1986 .
↑ 12 Feynman , 1982 .
↑ 12 lyhyt , 1997 .
↑ 1 2 Valiev, 2004 , s. 81-92.
↑ Shor, 1994 .
↑ Shor P. Kvanttilaskennan algoritmit: Diskreetit logaritmit ja faktorointi // Foundations of Computer Science, 1994 Proceedings . , 35th Annual Symposium on - IEEE , 1994. - S. 124–134. - ISBN 0-8186-6580-7 - doi:10.1109/SFCS.1994.365700

Kirjallisuus

Feynman R. Simulating Physics with Computers (englanniksi) // International Journal of Theoretical Physics - Springer Science + Business Media , 1982. - Voi. 21, Iss. 6 / 7. - s. 467-488. — ISSN 0020-7748 ; 1572-9575 - doi:10.1007/BF02650179
Feynman R. Kvanttimekaaniset tietokoneet (englanniksi) // Fysiikan perusteet / Gerard 't Hooft - Springer Science + Business Media , 1986. - Voi. 16, Iss. 6. - P. 507-531. — ISSN 0015-9018 ; 1572-9516 - doi:10.1007/BF01886518
D B., AN C., S D., J P., Beckman D. , Chari A. N. , Devabhaktuni S. , Preskill J. Tehokkaat verkot kvanttifaktorointiin // Phys . Rev. A - College Park, MD : American Physical Society , 1996. - Voi. 54, Iss. 2. - P. 1034-1063. — ISSN 2469-9926 ; 2469-9934 ; 2469-9942 - doi:10.1103/PHYSREVA.54.1034 - PMID:9913575 - arXiv:quant-ph/9602016
Shor P. Kvanttilaskennan algoritmit: Diskreetit logaritmit ja faktorointi (englanniksi) // Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on - IEEE , 1994. - S. 124–134. - ISBN 0-8186-6580-7 - doi:10.1109/SFCS.1994.365700
Lyhyt PW -polynomi-aikaalgoritmit alkutekijöihin ja diskreeteille logaritmeille kvanttitietokoneessa // Tietojenkäsittelytieteen perusteet: Konferenssijulkaisut. - 1997. - S. 1484-1509.
Valiev K. A. , Kokin A. A. Kvanttitietokoneet: toiveet ja todellisuus. - Izhevsk: RHD, 2004. - 320 s.

Linkit

Shor PW -algoritmit kvanttilaskentaan: diskreetit logaritmit ja factoring // Tietojenkäsittelytieteen perusteet : Konferenssijulkaisut. - 1994. - S. 124-134 . - ISBN 0-8186-6580-7 . - doi : 10.1109/SFCS.1994.365700 .

Lyhyt PW -polynomi-aikaalgoritmit alkutekijöihin ja diskreeteille logaritmeille kvanttitietokoneessa // Tietojenkäsittelytieteen perusteet: Konferenssijulkaisut. - 1997. - S. 1484-1509 .

Lähdekoodi kvanttitietokonesimulaattorille C++-kielellä ja Shorin algoritmin täydellinen toteutus, mukaan lukien käännettävä modulaarinen eksponentiojärjestelmä, yksityiskohtainen kuvaus ja kaaviot kvanttiporteista

Kvanttialgoritmit
Shorin algoritmi Groverin algoritmi Deutsch-Yozhi algoritmi Feynmanin ongelma Zalka-Wiesner-algoritmi kvanttihehkutus

kvanttiinformatiikka

Yleiset käsitteet

kvanttiviestintä

kvanttikanava
- kvanttiverkko
kvantti kryptografia
- Kvanttiavainten jakelu
Kvanttienergian teleportaatio
kvanttiteleportaatio
Ultra-tiheä kvanttikoodaus
LOCC
kvanttitislaus

Kvanttialgoritmit

kvanttisimulaattori
Deutsch-Yozhi algoritmi
Bernstein-Wazirani-algoritmi
Groverin algoritmi
Kvantti-Fourier-muunnos
Shorin algoritmi
Simonin ongelma
Kvanttivaiheen arviointialgoritmi
Kvanttilaskenta-algoritmi
kvanttihehkutus
Algoritminen jäähdytys
Kvanttialgoritmi lineaarisen yhtälöjärjestelmän ratkaisemiseen
Amplitudin vahvistus

Kvanttikompleksiteoria

Turingin kvanttikone
EQP
BQP
QMA
PostBQP
QIP

Kvanttilaskentamallit

kvanttipiiri
- kvanttiportti
Yksipuolinen kvanttitietokone
- klusterin
Adiabaattinen kvanttilaskenta
Topologinen kvanttitietokone

Epäkoherenssin ehkäisy

Kvanttivirheiden korjaus
Stabilointikoodit
Stabilointiformalismi
Kvanttikonvoluutiokoodi

Fyysiset toteutukset

kvanttioptiikka	Kavitaatiokvanttielektrodynamiikka Ääriviivan kvanttielektrodynamiikka Lineaariseen optiikkaan perustuva kvanttilaskenta KLM-protokolla Bosoninen näytteenotto
superkylmiä atomeja	Absorboituneen ionin kvanttitietokone Optinen ritilä
takaisin perustuva	Ydinmagneettiseen resonanssiin perustuva kvanttitietokone Kanen kvanttitietokone Häviö kvanttitietokone - DiVincenzo NV keskusta
Suprajohtavat kvanttitietokoneet	lataa qubit suoratoisto qubit Vaihe qubit Transmon