Quantum Fourier Transform

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 2 januari 2020; kontroller kräver 5 redigeringar .

Kvantfouriertransformen (förkortning QFT) är en linjär transformation av kvantbitar ( qubits ), som är kvantanalogen till den diskreta Fouriertransformen (DFT). QPF ingår i många kvantalgoritmer , särskilt Shors algoritm för att faktorisera ett tal i faktorer och beräkna den diskreta logaritmen , kvantfasuppskattningsalgoritmen för att hitta egenvärdena för en enhetlig operator och algoritmer för att hitta en dold undergrupp .

Kvantfouriertransformen exekveras effektivt på kvantdatorer genom speciell nedbrytning av matrisen till en produkt av enklare enhetsmatriser . Med denna expansion kan den diskreta Fouriertransformen vid ingångsamplituder implementeras av ett kvantnätverk bestående av Hadamard-grindar och kontrollerade kvantgrindar , där är antalet kvantbitar [1] . Jämfört med den klassiska DFT , som använder minneselement ( är antalet bitar ), som är exponentiellt större än kvant-FFT-grindar . $2^{n}$ $O(n^{2})$ $n$ $O(n2^{n})$ $n$ $O(n^{2})$

De mest kända kvant-Fourier-transformationsalgoritmerna (senom 2000) använder endast grindar för att uppnå den önskade approximationen av resultatet [2] . $O(n\log n)$

Definition

Kvantfouriertransformen är en klassisk diskret Fouriertransform som appliceras på amplitudvektorn för kvanttillstånd. Vanligtvis anser att sådana vektorer har längd . Den klassiska Fouriertransformen verkar på en vektor och mappar den till en vektor enligt formeln : $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,

var är den N: te roten till enhet . $\omega _{n}=e^{\frac {2\pi i}{N}}$

På liknande sätt verkar QTF på ett kvanttillstånd och mappar det till ett kvanttillstånd enligt formeln: $|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,

var är samma som tidigare. Eftersom det är en rotation utförs den inversa Fouriertransformen på liknande sätt $\omega_{n}$ $\omega_{n}$

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

Om är det grundläggande kvanttillståndet , kan kvantfouriertransformen representeras som en avbildning [3] : $x$

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

QFT kan på motsvarande sätt ses som en enhetlig matris (vilket är vad kvantportar är ) som verkar på vektorer av kvanttillstånd [4] . En sådan matris har inte en godtycklig, utan en strikt definierad 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}}

Eftersom och är den enklaste (den minst modulo exponentiella delen) N: te roten av enhet , för fallet och fasen får vi transformationsmatrisen $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 }}

Egenskaper

Enhet

De flesta av egenskaperna hos CFT följer av det faktum att den givna transformationen är enhetlig . Detta faktum kan enkelt verifieras genom att multiplicera matriserna , där är den hermitiska konjugerade matrisen av k . $FF^{\dolk }=F^{\dolk }F=I$ ${\displaystyle F^{\dolk ))$ $F$

Det följer av de enhetliga egenskaperna att inversen till QFT-transformationen har en hermitisk matriskonjugat till Fouriertransformens matris, därför . Om det finns ett effektivt kvantnätverk som implementerar QFT, kan samma nätverk startas i motsatt riktning för att utföra den inversa kvantfouriertransformen. Och detta betyder att båda transformationerna kan fungera effektivt på en kvantdator. ${\displaystyle F^{-1}=F^{\dolk ))$

Kvantnätverkssimuleringar av två möjliga 2-qubit FFTs med och visas för att demonstrera det identiska resultatet (med Q-Kit ). $F$ $F^{-1}$

Bygga nätverk

Kvantgrindar som används i KPF-nätverk är Hadamard-porten och grinden med kontrollerad fas . När det gäller matriser

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

var är enhetens th rot. ${\displaystyle \omega _{m}:=e^{\frac {2\pi i}{2^{m))))$ $2^{m}$

Endast linjära kvantoperationer används i transformationen, så att specificera en funktion för vart och ett av grundtillstånden gör det möjligt att bestämma blandade tillstånd från linearitet. Detta skiljer sig från definitionen av tillstånd i den vanliga Fouriertransformen. Specificera Fouriertransformen i vanlig mening - beskriv hur resultatet erhålls för godtyckliga indata. Men här, som i många andra fall, är det lättare att beskriva beteendet hos ett visst grundtillstånd och beräkna resultatet från linjäritet.

FTC-nätverket kan byggas för valfritt antal ingångsamplituder N ; detta är dock enklast att göra i fallet med . Då får vi det ortonormala vektorsystemet $N=2^{n}$

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

Bastillstånden listar alla möjliga tillstånd för qubits:

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

där, enligt tensor summationsregeln , betyder att qubit är i tillståndet , med 0 eller 1. Enligt konvention indikerar bastillståndsindex de möjliga tillstånden för denna qubit, det vill säga det är en binär expansion: $\ ibland$ $|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 är också bekvämt att använda binär bråknotation:

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

Till exempel och $[0.x_{1}]={\frac {x_{1}}{2}}$ $[0.x_{1}x_{2}]={\frac {x_{1}}{2}}+{\frac {x_{2}}{2^{2}}}.$

Med hjälp av dessa notationer skrivs CPF inom 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).

Kortheten är uppenbar genom att presentera den binära expansionen tillbaka som en summa

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

={\frac {1}{\sqrt {N}}}\summa _{\{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}}}\summa _{\{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 )\summa _{\ {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 att utsignalen qubit 1 är i superposition av tillstånd och qubit 2 är i superposition och etc. för resten av qubits (se diagrammet ovan). $|0\intervall$ $e^{2\pi i\,[0.x_{1}...x_{n}]}|1\rangle$ $|0\intervall$ $e^{2\pi i\,[0.x_{2}...x_{n}]}|1\rangle$

Med andra ord kan DFT, en operation på n qubits, brytas upp till en tensorprodukt av n en-qubit-operationer. I själva verket är var och en av dessa en-qubit-operationer effektivt implementerad på fasstyrda grindar och Hadamard-grindar. Den första qubiten kommer att kräva en Hadamard-grind och (n-1) fasstyrda grindar, den andra kommer att kräva två Hadamard-grindar och (n-2) fasstyrda grindar, och så vidare (se diagram ovan). Som ett resultat kommer grindar att krävas, vilket är kvadratiskt polynom med avseende på antalet qubits. $|x_{1}\rangle$ $|x_{2}\rangle$ $n+(n-1)+\cdots +1=n(n+1)/2=O(n^{2})$

Exempel

Betrakta kvantfouriertransformen på tre kvantbitar. Matematiskt är det skrivet

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

var är den enklaste åttonde roten av enhet tillfredsställande (eftersom ). $\Omega 3}$ $\omega _{3}^{8}=\left(e^{\frac {2\pi i}{2^{3}}}\right)^{8}=1$ $N=2^{3}=8$

För korthetens skull sätter vi , sedan matrisrepresentationen av 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}}.

Detta kan förenklas genom att notera , , , , och . $\omega ^{4}=-1$ $\omega ^{2}=i$ $\omega ^{6}=-i$ $\omega ^{5}=-\omega$ $\omega ^{3}=i\omega$ $\omega ^{7}=-i\omega$

3-qubit kvant Fourier-transformen skrivs om 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).

För att använda nätverket kommer vi att komponera nedbrytningen av QPF i omvänd ordning, nämligen

|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 nedan visar nätverket för (med omvänd ordning av utgående qubits med avseende på den direkta FFT). $n:=3$

Som beräknat ovan används grindar, vilket motsvarar . $n(n+1)/2=6$ $n=3$

Dessutom implementerar följande nätverk 1-, 2- och 3-qubit FFT:er: Schematisk och simulering av 1-, 2- och 3-qubit FFT:er Arkiverad 23 mars 2019 på Wayback Machine

Figuren visar två olika implementeringar av 3-qubit FFT som är likvärdiga.

Se även

Fouriertransform

Anteckningar

↑ Michael A. Nielsen och Isaac Chuan. Kvantberäkning och kvantinformation, sid. 217 (engelska) . - Cambridge: Cambridge University Press , 2000. - ISBN 0-521-63503-9 .
↑ Hales, Hallgren, 2000 .
↑ Weinstein, Havel, Emerson et al., 2004 .
↑ Ronald de Wolf , Den klassiska och kvanta Fourier-transformen, 1.1 Den diskreta Fourier-transformen, sid. 1, (pdf) Arkiverad 12 september 2011 på Wayback Machine
↑ Thomas G. Draper, Addition on a Quantum Computer, sid. 5, 1 september 1998, (pdf) Arkiverad 24 december 2018 på Wayback Machine

Litteratur

K. R. Parthasarathy , föreläsningar om kvantberäkning och kvantfelskorrigerande 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 förbättrad quantum Fourier transform algorithm and applications // FOCS 2000 : 41st Annual Symposium on Foundations of Computer Science, Redondo Beach, CA, USA, USA, 12-14 nov. 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. - 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

Länkar

Wolfram Demonstration Project: Quantum Circuit Implementing Grovers Search Algorithm Arkiverad 20 november 2020 på Wayback Machine
Wolfram Demonstration Project: Quantum Circuit Implementing Quantum Fourier Transform Arkiverad 22 december 2018 på Wayback Machine
Q-Kit: Graphical Quantum Circuit Simulator Arkiverad 23 mars 2019 på Wayback Machine
Quirk online life quantum fourier transform Arkiverad 1 januari 2019 på Wayback Machine

kvantinformatik

Allmänna begrepp

kvantkommunikation

kvantkanal
- kvantnät
kvantkryptografi
- Kvantnyckeldistribution
Teleportering av kvantenergi
kvantteleportering
Quantum ultra-tät kodning
LOCC
kvantdestillation

Kvantalgoritmer

kvantsimulator
Deutsch-Yozhi algoritm
Bernstein-Wazirani Algoritm
Grovers algoritm
Quantum Fourier Transform
Shors algoritm
Simons problem
Quantum Phase Estimation Algoritm
Quantum Computing Algoritm
kvantglödgning
Algoritmisk kylning
Kvantalgoritm för att lösa ett system av linjära ekvationer
Amplitudförstärkning

Kvantkomplexitetsteori

Turing kvantmaskin
EQP
BQP
QMA
PostBQP
QIP

Quantum Computing Models

kvantkrets
- kvantport
Ensidig kvantdator
- klunga
Adiabatisk kvantberäkning
Topologisk kvantdator

Förebyggande av dekoherens

Korrigering av kvantfel
Stabiliseringskoder
Stabiliseringsformalism
Quantum faltningskod

Fysiska implementeringar

kvantoptik	Kavitationskvantelektrodynamik Kontur kvantelektrodynamik Kvantberäkning baserad på linjär optik KLM-protokoll Bosonisk provtagning
superkalla atomer	Absorberad jon kvantdator Optiskt galler
ryggbaserad _	Kvantdator baserad på kärnmagnetisk resonans Kanes kvantdator Förlust kvantdator - DiVincenzo NV centrum
Supraledande kvantdatorer	ladda qubit strömmande qubit Fas qubit Transmon