Kvantti-Fourier-muunnos

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 2.1.2020 tarkistetusta versiosta . tarkastukset vaativat 5 muokkausta .

Kvantti-Fourier-muunnos (lyhennetty QFT) on kvanttibittien ( qubits ) lineaarinen muunnos , joka on diskreetin Fourier-muunnoksen (DFT) kvanttianalogi. QPF sisältyy moniin kvanttialgoritmeihin , erityisesti Shorin algoritmiin lukujen laskemiseksi tekijöiksi ja diskreetin logaritmin laskemiseen, kvanttivaiheen estimointialgoritmiin unitaarioperaattorin ominaisarvojen löytämiseksi ja algoritmeihin piilotetun aliryhmän löytämiseksi .

Kvantti-Fourier-muunnos suoritetaan tehokkaasti kvanttitietokoneissa matriisin erityishajotuksella yksinkertaisempien unitaaristen matriisien tuloksi . Tällä laajennuksella diskreetti Fourier-muunnos tuloamplitudilla voidaan toteuttaa kvanttiverkolla, joka koostuu Hadamard-porteista ja ohjatuista kvanttiporteista , jossa on kubittien lukumäärä [1] . Verrattuna klassiseen DFT :hen , joka käyttää muistielementtejä ( on bittien lukumäärä ), joka on eksponentiaalisesti suurempi kuin kvantti-FFT-portit . $2^{n}$ $O(n^{2})$ $n$ $O(n2^{n})$ $n$ $O(n^{2})$

Tunnetuimmat kvantti-Fourier-muunnosalgoritmit (vuoden 2000 lopulla) käyttävät vain portteja tuloksen halutun likiarvon saavuttamiseksi [2] . $O(n\log n)$

Määritelmä

Kvantti-Fourier-muunnos on klassinen diskreetti Fourier-muunnos, jota sovelletaan kvanttitilojen amplitudivektoriin. Yleensä pidetään sellaisia vektoreita, joiden pituus on . Klassinen Fourier-muunnos vaikuttaa vektoriin ja kartoittaa sen vektoriin seuraavan kaavan mukaan : $N:=2^{n}$ ${\displaystyle (x_{0},x_{1},\ldots ,x_{N-1})\in \mathbb {C} ^{N))$ ${\displaystyle (y_{0},y_{1},\ldots ,y_{N-1})\in \mathbb {C} ^{N))$

y_{k}={\frac {1}{\sqrt {N))}\sum _{j=0}^{N-1}x_{j}\omega _{n}^{-jk },\quad k=0,1,2,\ldots ,N-1,

missä on ykseyden N :s juuri . $\omega _{n}=e^{\frac {2\pi i}{N}}$

Vastaavasti QTF vaikuttaa kvanttitilaan ja kartoittaa sen kvanttitilaan seuraavan kaavan mukaan: $|x\rangle =\sum _{i=0}^{N-1}x_{i}|i\rangle$ $\sum _{i=0}^{N-1}y_{i}|i\rangle$

y_{k}={\frac {1}{\sqrt {N}}}\sum _{j=0}^{N-1}x_{j}\omega _{n}^{jk} ,\quad k=0,1,2,\ldots ,N-1,

missä on sama kuin ennen. Koska on rotaatio, käänteinen Fourier-muunnos suoritetaan samalla tavalla $\omega_{n}$ $\omega_{n}$

y_{k}={\frac {1}{\sqrt {N))}\sum _{j=0}^{N-1}x_{j}\omega _{n}^{-jk }

Jos on peruskvanttitila , kvantti-Fourier-muunnos voidaan esittää kuvauksena [3] : $x$

QFT(|x\rangle )={\frac {1}{\sqrt {N}}}\sum _{j=0}^{N-1}\omega _{n}^{jx}| j\rangle

QFT voidaan vastaavasti nähdä unitaarina matriisina (joka ovat kvanttiportit ), joka vaikuttaa kvanttitilojen vektoreihin [4] . Tällaisella matriisilla ei ole mielivaltaista, vaan tiukasti määritelty muoto $F_{N}$

F_{N}={\frac {1}{\sqrt {N}}}{\begin{bmatrix}1&1&1&1&\cdots &1\\1&\omega _{n}&\omega _{n}^{ 2}&\omega _{n}^{3}&\cdots &\omega _{n}^{N-1}\\1&\omega _{n}^{2}&\omega _{n}^ {4}&\omega _{n}^{6}&\cdots &\omega _{n}^{2(N-1)}\\1&\omega _{n}^{3}&\omega _ {n}^{6}&\omega _{n}^{9}&\cdots &\omega _{n}^{3(N-1)}\\\vdots &\vdots &\vdots &\vdots &&\vpisteet \\1&\omega _{n}^{N-1}&\omega _{n}^{2(N-1)}&\omega _{n}^{3(N-1)} &\cdots &\omega _{n}^{(N-1)(N-1)}\end{bmatrix}}

Koska ja on yksikön yksinkertaisin (pienin modulo-eksponentiaalinen osa) N :s juuri , tapaukselle ja vaiheelle saadaan muunnosmatriisi $N:=2^{n}$ ${\displaystyle \omega _{n}:=e^{\frac {2\pi i}{2^{n))))$ $N=4=2^{2}$ $\omega _{2}=i$

F_{4}={\frac {1}{2}}{\begin{bmatrix}1&1&1&1\\1&i&-1&-i\\1&-1&1&-1\\1&-i&-1&i\end{bmatrix }}

Ominaisuudet

Unitarity

Suurin osa CFT:n ominaisuuksista johtuu siitä, että annettu muunnos on unitaarinen . Tämä tosiasia on helppo tarkistaa kertomalla matriisit , missä on k: n hermiittinen konjugaattimatriisi . $FF^{\dagger }=F^{\dagger }F=I$ ${\displaystyle F^{\tikari ))$ $F$

Unitaarisista ominaisuuksista seuraa, että QFT-muunnoksen käänteisellä on matriisi Hermitian konjugaatti Fourier-muunnoksen matriisiin, joten . Jos on olemassa tehokas kvanttiverkko, joka toteuttaa QFT:n, niin sama verkko voidaan käynnistää vastakkaiseen suuntaan käänteisen kvantti-Fourier-muunnoksen suorittamiseksi. Ja tämä tarkoittaa, että molemmat muunnokset voivat toimia tehokkaasti kvanttitietokoneessa. ${\displaystyle F^{-1}=F^{\tikari ))$

Kvanttiverkkosimulaatiot kahdesta mahdollisesta 2 qubit FFT:stä käyttämällä ja osoittavat identtisen tuloksen (käyttäen Q-Kit ). $F$ $F^{-1}$

Verkkojen rakentaminen

KPF - verkoissa käytetyt kvanttiportit ovat Hadamard - portti ja portti , jossa on ohjattu vaihe . Matriisien suhteen

H:={\frac {1}{\sqrt {2))}{\begin{pmatrix}1&1\\1&-1\end{pmatrix)),\quad R_{m}:={\begin {pmatrix}1&0\\0&\omega _{m}\end{pmatrix}},

missä on yhtenäisyyden juuri. ${\displaystyle \omega _{m}:=e^{\frac {2\pi i}{2^{m))))$ $2^{m}$

Muunnoksessa käytetään vain lineaarisia kvanttioperaatioita, joten funktion määrittäminen kullekin perustilalle mahdollistaa sekatilojen määrittämisen lineaarisuudesta. Tämä eroaa tilojen määritelmästä tavallisessa Fourier-muunnoksessa. Määritä Fourier-muunnos tavallisessa merkityksessä - kuvaile kuinka tulos saadaan mielivaltaiselle syötedatalle. Mutta tässä, kuten monissa muissa tapauksissa, on helpompi kuvata tietyn perustilan käyttäytymistä ja laskea tulos lineaarisuudesta.

FTC-verkko voidaan rakentaa mille tahansa määrälle tuloamplitudeja N ; tämä on kuitenkin helpoin tehdä tapauksessa . Sitten saadaan ortonormaali vektorijärjestelmä $N=2^{n}$

|0\rangle ,\ldots ,|2^{n}-1\rangle .

Perustilat luettelevat kaikki mahdolliset kubittien tilat:

|x\rangle =|x_{1}x_{2}\ldots x_{n}\rangle =|x_{1}\rangle \otimes |x_{2}\rangle \otimes \cdots \otimes |x_ {n}\rangle

missä tensorisummaussäännön mukaan tarkoittaa , että qubit on tilassa 0 tai 1. Sopimuksen mukaan perustilaindeksi ilmaisee tämän kubitin mahdolliset tilat, eli kyseessä on binäärilaajennus: $\otimes$ $|x_{j}\rangle$ $j$ $x_{j}$ $x_{j}$ $x$

x=x_{1}2^{n-1}+x_{2}2^{n-2}+\cdots +x_{n}2^{0}.\quad

On myös kätevää käyttää murtolukua:

[0.x_{1}\ldots x_{m}]=\sum _{k=1}^{m}x_{k}2^{-k}.

Esimerkiksi ja $[0.x_{1}]={\frac {x_{1}}{2}}$ $[0.x_{1}x_{2}]={\frac {x_{1}}{2}}+{\frac {x_{2}}{2^{2}}}.$

Näitä merkintöjä käyttäen CPF kirjoitetaan pian [5] :

QFT(|x_{1}x_{2}\ldots x_{n}\rangle )={\frac {1}{\sqrt {N))}\ \left(|0\rangle +e^{ 2\pi i\,[0.x_{n}]}|1\rangle \right)\otimes \left(|0\rangle +e^{2\pi i\,[0.x_{n-1} x_{n}]}|1\rangle \right)\otimes \cdots \otimes \left(|0\rangle +e^{2\pi i\,[0.x_{1}x_{2}\ldots x_ {n}]}|1\rangle \right)

tai

QFT(|x_{1}x_{2}\ldots x_{n}\rangle )={\frac {1}{\sqrt {N))}\ \left(|0\rangle +\omega _ {1}^{x}|1\rangle \right)\otimes \left(|0\rangle +\omega _{2}^{x}|1\rangle \right)\otimes \cdots \otimes \left( |0\rangle +\omega _{n}^{x}|1\rangle \right).

Lyhytisyys käy ilmi esittämällä binäärinen laajennus takaisin summana

QFT(|x_{1}x_{2}\ldots x_{n}\rangle )={\frac {1}{\sqrt {N))}\sum _{k=0}^{2^ {n}-1}e^{2\pi ik[0.x_{1}x_{2}\ldots x_{n}]}|k\rangle

={\frac {1}{\sqrt {N}}}\sum _{\{k_{0},k_{1},...k_{n-1}\}\in \{0 ,1\}^{n}}e^{2\pi i\sum _{j=1}^{n}k_{nj}2^{j-1}[0.x_{1}x_{2} \ldots x_{n}]}|k_{0}k_{1}\ldots k_{n-1}\rangle

={\frac {1}{\sqrt {N}}}\sum _{\{k_{0},k_{1},...k_{n-1}\}\in \{0 ,1\}^{n}}\prod _{j=1}^{n}e^{2\pi ik_{nj}[0.x_{j}x_{j+1}\ldots x_{n} ]}|k_{0}k_{1}\ldots k_{n-1}\rangle

={\frac {1}{\sqrt {N}}}(|0\rangle +e^{2\pi i[0.x_{n}]}|1\rangle )\sum _{\ {k_{1},...k_{n-1}\}\in \{0,1\}^{n-1}}\prod _{j=1}^{n-1}e^{ 2\pi ik_{nj}[0.x_{j}x_{j+1}\ldots x_{n}]}|k_{1}\ldots k_{n-1}\rangle

={\frac {1}{\sqrt {N}}}\prod _{j=1}^{n}(|0\rangle +e^{2\pi i[0.x_{j} x_{j+1}\ldots x_{n}]}|1\rangle )

Voidaan nähdä, että lähtö kubitti 1 on tilojen superpositiossa ja , qubit 2 on superpositiossa jne . muiden kubittien kohdalla (katso yllä oleva kaavio). $|0\alue$ $e^{2\pi i\,[0.x_{1}...x_{n}]}|1\rangle$ $|0\alue$ $e^{2\pi i\,[0.x_{2}...x_{n}]}|1\rangle$

Toisin sanoen DFT, n kubitin operaatio , voidaan hajottaa n yhden kubitin operaation tensorituloksi.Jokainen näistä yhden kubitin operaatioista on todellakin toteutettu tehokkaasti vaiheohjatuilla porteilla ja Hadamardin porteilla. Ensimmäinen kubitti vaatii yhden Hadamard-portin ja (n-1) vaiheohjattua porttia, toinen kaksi Hadamard-porttia ja (n-2) vaiheohjattua porttia ja niin edelleen (katso kaavio yllä). Tämän seurauksena vaaditaan portit, joka on neliöpolynomi suhteessa kubittien määrään. $|x_{1}\rangle$ $|x_{2}\rangle$ $n+(n-1)+\cdots +1=n(n+1)/2=O(n^{2})$

Esimerkki

Tarkastellaan kvantti-Fourier-muunnosta kolmella kubitilla. Matemaattisesti se on kirjoitettu

QFT:|x\rangle \mapsto {\frac {1}{\sqrt {2^{3))))\sum _{k=0}^{2^{3}-1}\omega _ {3}^{xk}|k\rangle ,

missä on ykseyden yksinkertaisin kahdeksasjuuri , joka tyydyttää (koska ). $\Omega 3}$ $\omega _{3}^{8}=\left(e^{\frac {2\pi i}{2^{3}}}\right)^{8}=1$ $N=2^{3}=8$

Lyhyyden vuoksi asetimme , sitten QPF:n matriisiesityksen kolmella kubitilla ${\displaystyle \omega :=\omega _{3))$

F_{2^{3}}={\frac {1}{\sqrt {2^{3}}}}{\begin{bmatrix}1&1&1&1&1&1&1&1\\1&\omega &\omega ^{2}& \omega ^{3}&\omega ^{4}&\omega ^{5}&\omega ^{6}&\omega ^{7}\\1&\omega ^{2}&\omega ^{4} &\omega ^{6}&\omega ^{8}&\omega ^{10}&\omega ^{12}&\omega ^{14}\\1&\omega ^{3}&\omega ^{6 }&\omega ^{9}&\omega ^{12}&\omega ^{15}&\omega ^{18}&\omega ^{21}\\1&\omega ^{4}&\omega ^{ 8}&\omega ^{12}&\omega ^{16}&\omega ^{20}&\omega ^{24}&\omega ^{28}\\1&\omega ^{5}&\omega ^ {10}&\omega ^{15}&\omega ^{20}&\omega ^{25}&\omega ^{30}&\omega ^{35}\\1&\omega ^{6}&\omega ^{12}&\omega ^{18}&\omega ^{24}&\omega ^{30}&\omega ^{36}&\omega ^{42}\\1&\omega ^{7}&\ omega ^{14}&\omega ^{21}&\omega ^{28}&\omega ^{35}&\omega ^{42}&\omega ^{49}\\\end{bmatrix}}={ \frac {1}{\sqrt {2^{3}}}}{\begin{bmatrix}1&1&1&1&1&1&1&1\\1&\omega &\omega ^{2}&\omega ^{3}&\omega ^{4} &\omega ^{5}&\omega ^{6}&\omega ^{7}\\1&\omega ^{2}&\omega ^{4}&\omega ^{6}&1&\omega ^{2 }&\omega ^{4}&\omega ^{6}\\1&\omega ^{3}&\omega ^{6}&\omega &\omega ^{4}&\  omega ^{7}&\omega ^{2}&\omega ^{5}\\1&\omega ^{4}&1&\omega ^{4}&1&\omega ^{4}&1&\omega ^{4}\ \1&\omega ^{5}&\omega ^{2}&\omega ^{7}&\omega ^{4}&\omega &\omega ^{6}&\omega ^{3}\\1&\ omega ^{6}&\omega ^{4}&\omega ^{2}&1&\omega ^{6}&\omega ^{4}&\omega ^{2}\\1&\omega ^{7}& \omega ^{6}&\omega ^{5}&\omega ^{4}&\omega ^{3}&\omega ^{2}&\omega \\\end{bmatrix}}.

Tätä voidaan yksinkertaistaa merkitsemällä , , , ja . $\omega ^{4}=-1$ $\omega ^{2}=i$ $\omega ^{6}=-i$ $\omega ^{5}=-\omega$ $\omega ^{3}=i\omega$ $\omega ^{7}=-i\omega$

3-kubitin Fourier-kvanttimuunnos kirjoitetaan uudelleen muotoon

QFT(|x_{1},x_{2},x_{3}\rangle )={\frac {1}{\sqrt {2^{3))))\ \left(|0\rangle +e^{2\pi i\,[0.x_{3}]}|1\rangle \right)\otimes \left(|0\rangle +e^{2\pi i\,[0.x_{ 2}x_{3}]}|1\rangle \right)\otimes \left(|0\rangle +e^{2\pi i\,[0.x_{1}x_{2}x_{3}] }|1\rangle\right)

tai

QFT(|x_{1},x_{2},x_{3}\rangle )={\frac {1}{\sqrt {2^{3))))\ \left(|0\rangle +\omega _{1}^{x}|1\rangle \right)\otimes \left(|0\rangle +\omega _{2}^{x}|1\rangle \right)\otimes \left( |0\rangle +\omega _{3}^{x}|1\rangle \right).

Verkon käyttöä varten laadimme QPF:n hajotuksen käänteisessä järjestyksessä, nimittäin

|x_{1},x_{2},x_{3}\rangle \longmapsto {\frac {1}{\sqrt {2^{3))))\ \left(|0\rangle +\ omega _{3}^{x}|1\rangle \right)\otimes \left(|0\rangle +\omega _{2}^{x}|1\rangle \right)\otimes \left(|0 \rangle +\omega _{1}^{x}|1\rangle \right).

Alla olevassa kuvassa näkyy verkko (lähtökubittien käänteisessä järjestyksessä suoran FFT:n suhteen). ${\näyttötyyli n:=3}$

Kuten edellä on laskettu, käytetään portteja, mikä vastaa . ${\näyttötyyli n(n+1)/2=6}$ $n = 3$

Lisäksi seuraavat verkot toteuttavat 1-, 2- ja 3-kubittisia FFT:itä: 1-, 2- ja 3-kubitin FFT:n kaavio ja simulointi Arkistoitu 23. maaliskuuta 2019 Wayback Machinessa

Kuvassa on kaksi erilaista 3-kubitin FFT-toteutusta, jotka ovat vastaavia.

Katso myös

Fourier-muunnos

Muistiinpanot

↑ Michael A. Nielsen ja Isaac Chuan. Kvanttilaskenta ja kvanttitieto, s. 217 (englanniksi) . - Cambridge: Cambridge University Press , 2000. - ISBN 0-521-63503-9 .
↑ Hales, Hallgren, 2000 .
↑ Weinstein, Havel, Emerson et ai., 2004 .
↑ Ronald de Wolf , Klassinen ja kvantti-Fourier-muunnos, 1.1 Diskreetti Fourier-muunnos, s. 1, (pdf) Arkistoitu 12. syyskuuta 2011 Wayback Machinessa
↑ Thomas G. Draper, Addition on a Quantum Computer, s. 5, 1. syyskuuta 1998, (pdf) Arkistoitu 24. joulukuuta 2018 Wayback Machinessa

Kirjallisuus

K. R. Parthasarathy , Lectures on Quantum Computation and Quantum Error Correcting Codes (Indian Statistical Institute, Delhi Center, kesäkuu 2001)
Preskill, John , Lecture Notes for Physics 229: Quantum Information and Computation (CIT, syyskuu 1998)
Hales L. R. , Hallgren S. Parannettu kvantti-Fourier-muunnosalgoritmi ja sovellukset // FOCS 2000 : 41st Annual Symposium on Foundations of Computer Science, Redondo Beach, CA, USA, USA, 12.-14.11. 2000. Proceedings - IEEE , 2000. - P. 515-525. - ISBN 978-0-7695-0850-4 - doi:10.1109/SFCS.2000.892005
Weinstein Y.S. , Havel T.F. , Emerson J. , Boulan N. , Saraceno M. , Lloyd S. , Cory D.G. Quantum process tomography of the quantum Fourier transform // J. Chem. Phys / H. Urey , J. E. Mayer , Clyde A. Hutchison, Jr. , D. Levy , M. I. Lester - AIP , 2004. - Voi. 121, Iss. 13. - P. 6117-6133. — ISSN 0021-9606 ; 1089-7690 ; 1520-9032 - doi:10.1063/1.1785151 - PMID:15446906 - arXiv:quant-ph/0406239

Linkit

Wolfram-esittelyprojekti: Quantum Circuit Implementing Grover's Search Algorithm Arkistoitu 20. marraskuuta 2020 Wayback Machinessa
Wolfram-esittelyprojekti: Quantum Circuit Implementing Quantum Fourier Transform Arkistoitu 22. joulukuuta 2018 Wayback Machinessa
Q-Kit: Graphical Quantum Circuit Simulator arkistoitu 23. maaliskuuta 2019 Wayback Machinessa
Quirk online life quantum fourier transform Arkistoitu 1. tammikuuta 2019 Wayback Machinessa

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