Quantum Fourier transformation

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 2. januar 2020; checks kræver 5 redigeringer .

Kvante-Fourier-transformationen (forkortet QFT) er en lineær transformation af kvantebits ( qubits ), som er kvanteanalogen af den diskrete Fourier-transformation (DFT). QPF er inkluderet i mange kvantealgoritmer , især Shor's algoritme til at faktorisere et tal i faktorer og beregne den diskrete logaritme , kvantefase- estimeringsalgoritmen til at finde egenværdierne for en enhedsoperator og algoritmer til at finde en skjult undergruppe .

Kvante-Fourier-transformationen udføres effektivt på kvantecomputere ved speciel nedbrydning af matrixen til et produkt af enklere enhedsmatricer . Med denne udvidelse kan den diskrete Fourier-transformation ved inputamplituder implementeres af et kvantenetværk bestående af Hadamard-porte og kontrollerede kvanteporte , hvor er antallet af qubits [1] . Sammenlignet med den klassiske DFT , som bruger hukommelseselementer ( er antallet af bits ), som er eksponentielt større end kvante-FFT-porte . $2^{n}$ $O(n^{2})$ $n$ $O(n2^{n})$ $n$ $O(n^{2})$

De bedst kendte kvante-Fourier-transformationsalgoritmer (fra slutningen af 2000) bruger kun porte for at opnå den ønskede tilnærmelse af resultatet [2] . $O(n\log n)$

Definition

Kvante-Fourier-transformationen er en klassisk diskret Fourier-transformation anvendt på amplitudevektoren af kvantetilstande. Normalt overveje sådanne vektorer at have længde . Den klassiske Fourier-transformation virker på en vektor og kortlægger den til en vektor i henhold til formlen : $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,

hvor er den N'te rod af enhed . $\omega _{n}=e^{\frac {2\pi i}{N))$

På samme måde virker QTF på en kvantetilstand og kortlægger den til en kvantetilstand i henhold til formlen: $|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,

hvor er det samme som før. Da det er en rotation, udføres den inverse Fourier-transformation på samme måde $\omega_{n}$ $\omega_{n}$

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

Hvis er den grundlæggende kvantetilstand , kan kvante-Fourier-transformationen repræsenteres som en kortlægning [3] : $x$

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

QFT kan tilsvarende ses som en enhedsmatrix (hvilket er, hvad kvanteporte er ), der virker på vektorer af kvantetilstande [4] . En sådan matrix har ikke en vilkårlig, men en strengt defineret form $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 &&\vdots \\1&\omega _{n}^{N-1}&\omega _{n}^{2(N-1)}&\omega _{n}^{3(N-1)} &\cdots &\omega _{n}^{(N-1)(N-1)}\end{bmatrix}}

Da og er den enkleste (den mindste modulo eksponentielle del) N'te rod af enhed , for tilfælde og fase opnår vi transformationsmatrixen $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 }}

Egenskaber

Enhed

De fleste af egenskaberne ved CFT følger af, at den givne transformation er ensartet . Dette faktum kan let verificeres ved at gange matricerne , hvor er den hermitiske konjugerede matrix af k . $FF^{\dolk }=F^{\dolk }F=I$ ${\displaystyle F^{\dolk ))$ $F$

Det følger af enhedsegenskaberne, at den inverse til QFT-transformationen har en matrix- hermitisk konjugat til matrixen af Fourier-transformationen, derfor . Hvis der er et effektivt kvantenetværk, der implementerer QFT, så kan det samme netværk startes i den modsatte retning for at udføre den omvendte kvante Fourier-transformation. Og det betyder, at begge transformationer kan fungere effektivt på en kvantecomputer. ${\displaystyle F^{-1}=F^{\dolk ))$

Kvantenetværkssimuleringer af to mulige 2-qubit FFT'er ved hjælp af og vises for at demonstrere det identiske resultat (ved hjælp af Q-Kit ). $F$ $F^{-1}$

Opbygning af netværk

Kvanteporte, der bruges i KPF-netværk, er Hadamard-porten og porten med kontrolleret fase . Med hensyn til matricer

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}},

hvor er roden til enhed. ${\displaystyle \omega _{m}:=e^{\frac {2\pi i}{2^{m))))$ $2^{m}$

Der anvendes kun lineære kvanteoperationer i transformationen, således at specificering af en funktion for hver af grundtilstandene gør det muligt at bestemme blandede tilstande ud fra linearitet. Dette er forskelligt fra definitionen af tilstande i den sædvanlige Fourier-transformation. Angiv Fourier-transformationen i sædvanlig forstand - beskriv hvordan resultatet opnås for vilkårlige inputdata. Men her, som i mange andre tilfælde, er det lettere at beskrive adfærden af en bestemt grundtilstand og beregne resultatet ud fra linearitet.

FTC-netværket kan bygges til et hvilket som helst antal indgangsamplituder N ; dette er dog nemmest at gøre i tilfælde af . Så får vi det ortonormale system af vektorer $N=2^{n}$

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

Basistilstandene viser alle mulige tilstande af qubits:

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

hvor ifølge tensor summationsreglen betyder , at qubit er i tilstanden , med 0 eller 1. Ved konvention angiver basistilstandsindekset de mulige tilstande af denne qubit, det vil sige, at det er en binær udvidelse: $\ nogle gange$ $|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

Det er også praktisk at bruge binær brøknotation:

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

For eksempel og $[0.x_{1}]={\frac {x_{1}}{2}}$ $[0.x_{1}x_{2}]={\frac {x_{1}}{2}}+{\frac {x_{2}}{2^{2}}}.$

Ved at bruge disse notationer skrives CPF kort [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)

eller

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).

Kortheden er tydelig ved at præsentere den binære ekspansion tilbage som en sum

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}\}\i \{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}\}\i \{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 )

Det kan ses, at output-qubit 1 er i superposition af tilstande , og qubit 2 er i superposition osv . for resten af qubits (se diagrammet ovenfor). $|0\interval$ $e^{2\pi i\,[0.x_{1}...x_{n}]}|1\rangle$ $|0\interval$ $e^{2\pi i\,[0.x_{2}...x_{n}]}|1\rangle$

Med andre ord kan DFT, en operation på n qubits, dekomponeres til et tensorprodukt af n one-qubit operationer. Faktisk er hver af disse en-qubit operationer effektivt implementeret på fasekontrollerede porte og Hadamard gates. Den første qubit vil kræve én Hadamard-gate og (n-1) fasekontrollerede porte, den anden vil kræve to Hadamard-gates og (n-2) fasekontrollerede porte, og så videre (se diagrammet ovenfor). Som et resultat vil der kræves porte, hvilket er kvadratisk polynomium med hensyn til antallet af qubits. $|x_{1}\rangle$ $|x_{2}\rangle$ $n+(n-1)+\cdots +1=n(n+1)/2=O(n^{2})$

Eksempel

Overvej kvante-Fourier-transformationen på tre qubits. Matematisk er det skrevet

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

hvor er den enkleste ottendedel af enhed tilfredsstillende (fordi ). $\Omega 3}$ $\omega _{3}^{8}=\left(e^{\frac {2\pi i}{2^{3}}}\right)^{8}=1$ $N=2^{3}=8$

For kortheds skyld sætter vi , derefter matrixrepræsentationen af QPF på tre qubits ${\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}}.

Dette kan forenkles ved at notere , , , , og . $\omega ^{4}=-1$ $\omega ^{2}=i$ $\omega ^{6}=-i$ $\omega ^{5}=-\omega$ $\omega ^{3}=i\omega$ $\omega ^{7}=-i\omega$

3-qubit kvante Fourier-transformationen omskrives som

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)

eller

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).

For at bruge netværket vil vi sammensætte dekomponeringen af QPF i omvendt rækkefølge, nemlig

|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).

Figuren nedenfor viser netværket for (med omvendt rækkefølge af output-qubits i forhold til den direkte FFT). $n:=3$

Som beregnet ovenfor anvendes porte, hvilket svarer til . $n(n+1)/2=6$ $n=3$

Derudover implementerer følgende netværk 1-, 2- og 3-qubit FFT'er: Skematisk og simulering af 1-, 2- og 3-qubit FFT'er Arkiveret 23. marts 2019 på Wayback Machine

Figuren viser to forskellige implementeringer af 3-qubit FFT, der er ækvivalente.

Se også

Fourier transformation

Noter

↑ Michael A. Nielsen og Isaac Chuan. Kvanteberegning og kvanteinformation, s. 217 (engelsk) . - Cambridge: Cambridge University Press , 2000. - ISBN 0-521-63503-9 .
↑ Hales, Hallgren, 2000 .
↑ Weinstein, Havel, Emerson et al., 2004 .
↑ Ronald de Wolf , Den klassiske og kvante Fourier transformation, 1.1 Den diskrete Fourier transformation, s. 1, (pdf) Arkiveret 12. september 2011 på Wayback Machine
↑ Thomas G. Draper, Addition on a Quantum Computer, s. 5, 1. september 1998, (pdf) Arkiveret 24. december 2018 på Wayback Machine

Litteratur

K. R. Parthasarathy , forelæsninger om kvanteberegning og kvantefejlkorrigerende koder (Indian Statistical Institute, Delhi Center, juni 2001)
Preskill, John , Lecture Notes for Physics 229: Quantum Information and Computation (CIT, september 1998)
Hales L. R. , Hallgren S. En forbedret kvante-Fourier-transformationsalgoritme og applikationer // FOCS 2000 : 41st Annual Symposium on Foundations of Computer Science, Redondo Beach, CA, USA, USA, 12.-14. nov. 2000. Proceedings - IEEE , 2000. - S. 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. Kvanteprocestomografi af kvante-Fourier-transformationen // J. Chem. Phys / H. Urey , J. E. Mayer , Clyde A. Hutchison, Jr. , D. Levy , M. I. Lester - AIP , 2004. - Vol. 121, Iss. 13. - P. 6117-6133. — ISSN 0021-9606 ; 1089-7690 ; 1520-9032 - doi:10.1063/1.1785151 - PMID:15446906 - arXiv:quant-ph/0406239

Links

Wolfram Demonstration Project: Quantum Circuit Implementing Grover's Search Algorithm Arkiveret 20. november 2020 på Wayback Machine
Wolfram Demonstration Project: Quantum Circuit Implementing Quantum Fourier Transform Arkiveret 22. december 2018 på Wayback Machine
Q-Kit: Graphical Quantum Circuit Simulator Arkiveret 23. marts 2019 på Wayback Machine
Quirk online life quantum fourier transformation Arkiveret 1. januar 2019 på Wayback Machine

kvanteinformatik

Generelle begreber

kvantekommunikation

kvantekanal
- kvantenetværk
kvantekryptografi
- Kvantenøglefordeling
Teleportering af kvanteenergi
kvanteteleportation
Quantum ultra-tæt kodning
LOCC
kvantedestillation

Kvantealgoritmer

kvantesimulator
Deutsch-Yozhi algoritme
Bernstein-Wazirani algoritme
Grovers algoritme
Quantum Fourier transformation
Shors algoritme
Simons problem
Kvantefase-estimeringsalgoritme
Kvanteberegningsalgoritme
kvanteudglødning
Algoritmisk køling
Kvantealgoritme til løsning af et system af lineære ligninger
Amplitudeforstærkning

Kvantekompleksitetsteori

Turing kvantemaskine
EQP
BQP
QMA
PostBQP
QIP

Kvantecomputermodeller

kvantekredsløb
- kvanteport
Ensidet kvantecomputer
- klynge
Adiabatisk kvanteberegning
Topologisk kvantecomputer

Forebyggelse af dekohærens

Korrektion af kvantefejl
Stabiliseringskoder
Stabiliseringsformalisme
Kvante foldningskode

Fysiske implementeringer

kvanteoptik	Kavitationskvanteelektrodynamik Kontur kvanteelektrodynamik Kvanteberegning baseret på lineær optik KLM protokol Bosonisk prøvetagning
superkolde atomer	Absorberet ion kvantecomputer Optisk gitter
ryg baseret	Kvantecomputer baseret på kernemagnetisk resonans Kanes kvantecomputer Tabskvantecomputer - DiVincenzo NV center
Superledende kvantecomputere	opladningsqubit streaming qubit Fase qubit Transmon