Kvantová Fourierova transformace

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 2. ledna 2020; kontroly vyžadují 5 úprav .

Kvantová Fourierova transformace (zkr. QFT) je lineární transformace kvantových bitů ( qubits ), která je kvantovým analogem diskrétní Fourierovy transformace (DFT). QPF je zahrnuta v mnoha kvantových algoritmech , zejména v Shorově algoritmu pro rozdělení čísla do faktorů a výpočtu diskrétního logaritmu , v algoritmu kvantového odhadu fáze pro nalezení vlastních hodnot unitárního operátoru a v algoritmech pro nalezení skryté podskupiny .

Kvantová Fourierova transformace je efektivně prováděna na kvantových počítačích speciálním rozkladem matice na produkt jednodušších unitárních matic . S tímto rozšířením může být diskrétní Fourierova transformace na vstupních amplitudách implementována pomocí kvantové sítě sestávající z Hadamardových hradel a řízených kvantových hradel , kde je počet qubitů [1] . Oproti klasickému DFT , který využívá paměťové prvky ( je počet bitů ), která je exponenciálně větší než kvantová FFT hradla . $2^{n}$ $O(n^{2})$ $n$ $O(n2^{n})$ $n$ $O(n^{2})$

Nejznámější kvantové algoritmy Fourierovy transformace (od konce roku 2000) používají pouze hradla k dosažení požadované aproximace výsledku [2] . $O(n\log n)$

Definice

Kvantová Fourierova transformace je klasická diskrétní Fourierova transformace aplikovaná na amplitudový vektor kvantových stavů. Obvykle považujte takové vektory za délku . Klasická Fourierova transformace působí na vektor a mapuje jej na vektor podle vzorce : $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,

kde je N -tý kořen jednoty . $\omega _{n}=e^{\frac {2\pi i}{N))$

Podobně QTF působí na kvantový stav a mapuje jej do kvantového stavu podle vzorce: $|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,

kde je to stejné jako předtím. Protože se jedná o rotaci, provede se inverzní Fourierova transformace podobně $\omega_{n}$ $\omega_{n}$

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

Pokud je základní kvantový stav , lze kvantovou Fourierovu transformaci reprezentovat jako zobrazení [3] : $X$

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

Na QFT lze ekvivalentně pohlížet jako na jednotnou matici (což jsou kvantová hradla ) působící na vektory kvantových stavů [4] . Taková matice nemá libovolnou, ale přesně definovanou formu $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}}

Protože a je nejjednodušší (nejméně modulová exponenciální část) N -tá odmocnina jednoty , pro případ a fázi získáme transformační matici $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 }}

Vlastnosti

Unitarita

Většina vlastností CFT vyplývá ze skutečnosti, že daná transformace je unitární . Tento fakt lze snadno ověřit vynásobením matic , kde je hermitovská konjugovaná matice k . $FF^{\dagger }=F^{\dagger }F=I$ ${\displaystyle F^{\dagger ))$ $F$

Z unitárních vlastností vyplývá, že inverzní k transformaci QFT má matici Hermitovu konjugovanou k matici Fourierovy transformace, tedy . Pokud existuje efektivní kvantová síť, která implementuje QFT, pak lze stejnou síť spustit v opačném směru, aby se provedla inverzní kvantová Fourierova transformace. A to znamená, že obě transformace mohou efektivně fungovat na kvantovém počítači. ${\displaystyle F^{-1}=F^{\dagger ))$

Kvantové síťové simulace dvou možných 2-qubitových FFT pomocí a jsou ukázány jako identický výsledek (pomocí Q-Kit ). $F$ $F^{-1}$

Budování sítí

Kvantová hradla používaná v sítích KPF jsou Hadamardovo hradlo a hradlo s řízenou fází . Z hlediska matriky

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

kde je th kořen jednoty. ${\displaystyle \omega _{m}:=e^{\frac {2\pi i}{2^{m))))$ $2^{m}$

Při transformaci jsou použity pouze lineární kvantové operace, takže zadání funkce pro každý ze základních stavů umožňuje určit smíšené stavy z linearity. To se liší od definice stavů v obvyklé Fourierově transformaci. Specifikujte Fourierovu transformaci v obvyklém smyslu - popište, jak se získá výsledek pro libovolná vstupní data. Ale zde, stejně jako v mnoha jiných případech, je jednodušší popsat chování konkrétního základního stavu a vypočítat výsledek z linearity.

Síť FTC lze sestavit pro libovolný počet vstupních amplitud N ; to je však nejjednodušší v případě . Pak dostaneme ortonormální systém vektorů $N=2^{n}$

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

Základní stavy vypisují všechny možné stavy qubitů:

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

kde podle pravidla tensor sumace znamená , že qubit je ve stavu , s 0 nebo 1. Podle konvence index základního stavu udává možné stavy tohoto qubitu, to znamená, že se jedná o binární expanzi: $\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

Je také vhodné použít zlomkovou binární notaci:

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

Například a $[0.x_{1}]={\frac {x_{1}}{2}}$ $[0.x_{1}x_{2}]={\frac {x_{1}}{2}}+{\frac {x_{2}}{2^{2}}}.$

Pomocí těchto zápisů je CPF zapsán krátce [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)

nebo

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

Stručnost je zřejmá tím, že binární expanzi zpětně uvedeme jako součet

QFT(|x_{1}x_{2}\ldots x_{n}\rangle )={\frac {1}{\sqrt {N))}\součet _{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 )\součet _{\ {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 )

Je vidět, že výstupní qubit 1 je v superpozici stavů a , qubit 2 je v superpozici atd . pro zbytek qubitů (viz schéma výše). $|0\rozsah$ $e^{2\pi i\,[0.x_{1}...x_{n}]}|1\rangle$ $|0\rozsah$ $e^{2\pi i\,[0.x_{2}...x_{n}]}|1\rangle$

Jinými slovy, DFT, operaci na n qubitech, lze rozložit na tenzorový součin n jednoqubitových operací, každá z těchto jednoqubitových operací je skutečně efektivně implementována na fázově řízených hradlech a Hadamardových hradlech. První qubit bude vyžadovat jedno Hadamardovo hradlo a (n-1) fázově řízená hradla, druhý bude vyžadovat dvě Hadamardova hradla a (n-2) fázově řízená hradla a tak dále (viz schéma výše). V důsledku toho budou vyžadována hradla, což je kvadratický polynom s ohledem na počet qubitů. $|x_{1}\rangle$ $|x_{2}\rangle$ $n+(n-1)+\cdots +1=n(n+1)/2=O(n^{2})$

Příklad

Uvažujme kvantovou Fourierovu transformaci na třech qubitech. Matematicky je to napsáno

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

kde je nejjednodušší osmý kořen jednoty uspokojující (protože ). $\Omega 3}$ $\omega _{3}^{8}=\left(e^{\frac {2\pi i}{2^{3}}}\right)^{8}=1$ $N=2^{3}=8$

Pro stručnost jsme nastavili , pak maticovou reprezentaci QPF na třech qubitech ${\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}}.

To lze zjednodušit poznámkou , , , a . $\omega ^{4}=-1$ $\omega ^{2}=i$ $\omega ^{6}=-i$ $\omega ^{5}=-\omega$ $\omega ^{3}=i\omega$ $\omega ^{7}=-i\omega$

3-qubitová kvantová Fourierova transformace je přepsána jako

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)

nebo

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

Pro použití sítě složíme rozklad QPF v obráceném pořadí, a to

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

Obrázek níže ukazuje síť pro (s obráceným pořadím výstupních qubitů vzhledem k přímé FFT). $n:=3$

Jak bylo vypočteno výše, jsou použity brány, což odpovídá . $n(n+1)/2=6$ $n=3$

Kromě toho následující sítě implementují 1-, 2- a 3-qubitové FFT: Schéma a simulace 1-, 2- a 3-qubitových FFT Archivováno 23. března 2019 na Wayback Machine

Obrázek ukazuje dvě různé implementace 3-qubitové FFT, které jsou ekvivalentní.

Viz také

Fourierova transformace

Poznámky

↑ Michael A. Nielsen a Isaac Chuan. Kvantové výpočty a kvantové informace, str. 217 (anglicky) . - Cambridge: Cambridge University Press , 2000. - ISBN 0-521-63503-9 .
↑ Hales, Hallgren, 2000 .
↑ Weinstein, Havel, Emerson et al., 2004 .
↑ Ronald de Wolf , Klasická a kvantová Fourierova transformace, 1.1 Diskrétní Fourierova transformace, str. 1, (pdf) Archivováno 12. září 2011 na Wayback Machine
↑ Thomas G. Draper, Addition on a Quantum Computer, str. 5, 1. září 1998, (pdf) Archivováno 24. prosince 2018 na Wayback Machine

Literatura

K. R. Parthasarathy , Lectures on Quantum Computation and Quantum Error Correcting Codes (Indian Statistical Institute, Delhi Center, červen 2001)
Preskill, John , Lecture Notes for Physics 229: Quantum Information and Computation (CIT, září 1998)
Hales L. R. , Hallgren S. Vylepšený algoritmus a aplikace kvantové Fourierovy transformace // FOCS 2000 : 41. výroční symposium o základech počítačových věd, Redondo Beach, CA, USA, USA, 12.–14. 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. Kvantová procesní tomografie kvantové Fourierovy transformace // J. Chem. Phys / H. Urey , J. E. Mayer , Clyde A. Hutchison, Jr. , D. Levy , M. I. Lester - AIP , 2004. - Sv. 121, Iss. 13. - S. 6117-6133. — ISSN 0021-9606 ; 1089-7690 ; 1520-9032 - doi:10.1063/1.1785151 - PMID:15446906 - arXiv:quant-ph/0406239

Odkazy

Wolfram Demonstration Project: Quantum Circuit Implementing Grover's Search Algorithm Archived 20. listopadu 2020 na Wayback Machine
Wolfram Demonstration Project: Quantum Circuit Implementing Quantum Fourier Transform Archived 22. prosince 2018 na Wayback Machine
Q-Kit: Graphical Quantum Circuit Simulator Archivováno 23. března 2019 na Wayback Machine
Quirk online život kvantová fourierova transformace Archivováno 1. ledna 2019 na Wayback Machine

kvantová informatika

Obecné pojmy

kvantové komunikace

kvantový kanál
- kvantová síť
kvantová kryptografie
- Kvantová distribuce klíčů
Teleportace kvantové energie
kvantová teleportace
Kvantové ultra-husté kódování
LOCC
kvantová destilace

Kvantové algoritmy

kvantový simulátor
Deutsch-Yozhi algoritmus
Bernstein-Waziraniho algoritmus
Groverův algoritmus
Kvantová Fourierova transformace
Shorův algoritmus
Simonův problém
Algoritmus kvantového odhadu fáze
Kvantový výpočetní algoritmus
kvantové žíhání
Algoritmické chlazení
Kvantový algoritmus pro řešení soustavy lineárních rovnic
Amplitudový zisk

Kvantová teorie složitosti

Kvantové výpočetní modely

kvantový obvod
- kvantová brána
Jednostranný kvantový počítač
- shluk
Adiabatické kvantové výpočty
Topologický kvantový počítač

Prevence dekoherence

Oprava kvantových chyb
Stabilizační kódy
Stabilizační formalismus
Kvantový konvoluční kód

Fyzické implementace

kvantová optika	Kavitační kvantová elektrodynamika Konturová kvantová elektrodynamika Kvantové výpočty založené na lineární optice protokol KLM Bosonické vzorkování
superchladné atomy	Kvantový počítač s absorbovanými ionty Optická mřížka
zpět založené	Kvantový počítač založený na nukleární magnetické rezonanci Kaneův kvantový počítač Ztrátový kvantový počítač - DiVincenzo NV centrum
Supravodivé kvantové počítače	nabít qubit streamovací qubit Fázový qubit Transmon