Kvantum Fourier transzformáció

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. január 2-án felülvizsgált verziótól ; az ellenőrzések 5 szerkesztést igényelnek .

A kvantum-Fourier-transzformáció (röv. QFT) kvantumbitek ( qubitek) lineáris transzformációja , amely a diszkrét Fourier-transzformáció (DFT) kvantumanalógja. A QPF számos kvantumalgoritmusban megtalálható, különösen a Shor-algoritmusban a számok faktorokba való beszámítására és a diszkrét logaritmus kiszámítására, a kvantumfázis - becslési algoritmusra az unitárius operátor sajátértékeinek megtalálására , valamint a rejtett alcsoportok megtalálására szolgáló algoritmusokban .

A kvantum-Fourier-transzformáció hatékonyan végrehajtható kvantumszámítógépeken a mátrixnak egyszerűbb unitárius mátrixok szorzatára történő speciális felbomlásával . Ezzel a bővítéssel a bemeneti amplitúdójú diszkrét Fourier-transzformáció megvalósítható egy Hadamard-kapukból és vezérelt kvantumkapukból álló kvantumhálózattal , ahol a qubitek száma [1] . A klasszikus DFT -hez képest , amely memóriaelemeket használ ( a bitek száma ), amely exponenciálisan nagyobb, mint a kvantum FFT kapuk . $2^{n}$ $O(n^{2})$ $n$ $O(n2^{n})$ $n$ $O(n^{2})$

A legismertebb kvantum Fourier transzformációs algoritmusok (2000 végén) csak kapukat használnak az eredmény kívánt közelítésének eléréséhez [2] . $O(n\log n)$

Definíció

A kvantum-Fourier-transzformáció egy klasszikus diszkrét Fourier-transzformáció, amelyet kvantumállapotok amplitúdóvektorára alkalmaznak. Általában úgy tekintjük, hogy az ilyen vektorok hosszúak . A klasszikus Fourier-transzformáció egy vektorra hat, és a következő képlet szerint képezi le egy vektorra : $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,

hol van az egység N- edik gyökere . $\omega _{n}=e^{\frac {2\pi i}{N}}$

Hasonlóképpen, a QTF egy kvantumállapotra hat, és a következő képlet szerint képezi le kvantumállapotra : $|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,

ahol ugyanaz, mint korábban. Mivel ez egy forgatás, az inverz Fourier-transzformációt hasonlóan hajtjuk végre $\omega_{n}$ $\omega_{n}$

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

Ha az alapkvantumállapot , akkor a kvantum Fourier transzformáció leképezésként ábrázolható [3] : $x$

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

A QFT ekvivalens módon egy unitárius mátrixnak tekinthető (ami a kvantumkapuk ), amely kvantumállapotok vektoraira hat [4] . Egy ilyen mátrixnak nem tetszőleges, hanem szigorúan meghatározott formája van $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{bmátrix}}

Mivel és az egység legegyszerűbb (a legkisebb modulo exponenciális része) N- edik gyöke , esetre és fázisra megkapjuk a transzformációs mátrixot $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{bmátrix }}

Tulajdonságok

Egységesség

A CFT tulajdonságainak többsége abból következik, hogy az adott transzformáció unitárius . Ez a tény könnyen ellenőrizhető a mátrixok szorzásával , ahol a k hermitikus konjugált mátrixa . $FF^{\dagger }=F^{\dagger }F=I$ ${\displaystyle F^{\dagger ))$ $F$

Az unitárius tulajdonságokból következik, hogy a QFT transzformáció inverze a Fourier-transzformáció mátrixához Hermit-féle konjugált mátrixot tartalmaz, ezért . Ha van egy hatékony kvantumhálózat, amely megvalósítja a QFT-t, akkor ugyanazt a hálózatot az ellenkező irányba is elindíthatjuk az inverz kvantum Fourier transzformáció végrehajtására. Ez pedig azt jelenti, hogy mindkét transzformáció hatékonyan működhet kvantumszámítógépen. ${\displaystyle F^{-1}=F^{\tőr ))$

Két lehetséges 2 qubites FFT kvantumhálózati szimulációja a és az azonos eredmény bemutatására szolgál ( Q-Kit használatával ). $F$ $F^{-1}$

Hálózatépítés

A KPF hálózatokban használt kvantumkapuk a Hadamard kapu és a szabályozott fázisú kapu . A mátrixok tekintetében

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

hol van az egység gyökere. ${\displaystyle \omega _{m}:=e^{\frac {2\pi i}{2^{m))))$ $2^{m}$

A transzformáció során csak lineáris kvantumműveleteket használunk, így minden alapállapothoz függvény megadása lehetővé teszi a vegyes állapotok linearitásból történő meghatározását. Ez eltér a szokásos Fourier-transzformációban az állapotok meghatározásától. Adja meg a Fourier-transzformációt a szokásos értelemben - írja le, hogyan kapja meg az eredményt tetszőleges bemeneti adatok esetén. De itt is, mint sok más esetben, egyszerűbb egy adott alapállapot viselkedését leírni, és a linearitásból kiszámítani az eredményt.

Az FTC hálózat tetszőleges számú bemeneti amplitúdóhoz N ; ez azonban a legegyszerűbb esetben . Ekkor megkapjuk a vektorok ortonormális rendszerét $N=2^{n}$

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

Az alapállapotok felsorolják a qubitek összes lehetséges állapotát:

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

ahol a tenzorösszegzési szabály szerint azt jelenti, hogy a qubit 0 vagy 1 állapotban van. Megállapodás szerint az alapállapot-index ennek a qubitnek a lehetséges állapotait jelöli, azaz bináris bővítésről van szó: $\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

Szintén kényelmes a tört bináris jelölés használata:

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

Például, és $[0.x_{1}]={\frac {x_{1}}{2}}$ $[0.x_{1}x_{2}]={\frac {x_{1}}{2}}+{\frac {x_{2}}{2^{2}}}.$

Ezekkel a jelölésekkel a CPF röviden leírható [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)

vagy

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

A rövidség nyilvánvaló, ha a bináris kiterjesztést összegként mutatjuk be

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 )

Látható, hogy az 1 kimeneti qubit az állapotok szuperpozíciójában és a , a 2. qubit szuperpozícióban van stb . a többi qubit esetében (lásd a fenti ábrát). $|0\tartomány$ $e^{2\pi i\,[0.x_{1}...x_{n}]}|1\rangle$ $|0\tartomány$ $e^{2\pi i\,[0.x_{2}...x_{n}]}|1\rangle$

Más szóval, a DFT, egy n qubites művelet, n darab egy qubites művelet tenzorszorzatára bontható fel . Az első qubithez egy Hadamard kapura és (n-1) fázisvezérelt kapura, a másodikhoz két Hadamard kapura és (n-2) fázisvezérelt kapura van szükség, és így tovább (lásd a fenti ábrát). Ennek eredményeként kapukra lesz szükség, ami a qubitek számához képest másodfokú polinom. $|x_{1}\rangle$ $|x_{2}\rangle$ $n+(n-1)+\cdots +1=n(n+1)/2=O(n^{2})$

Példa

Tekintsük a kvantum Fourier transzformációt három qubiten. Matematikailag le van írva

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

ahol az egység legegyszerűbb nyolcadik gyöke kielégítő (mert ). $\Omega 3}$ $\omega _{3}^{8}=\left(e^{\frac {2\pi i}{2^{3}}}\right)^{8}=1$ $N=2^{3}=8$

A rövidség kedvéért beállítjuk , majd a QPF mátrixábrázolását három qubiten ${\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}}.

Ez leegyszerűsíthető a , , , , és . $\omega ^{4}=-1$ $\omega ^{2}=i$ $\omega ^{6}=-i$ $\omega ^{5}=-\omega$ $\omega ^{3}=i\omega$ $\omega ^{7}=-i\omega$

A 3 qubit kvantum Fourier transzformációt a következőképpen írjuk át

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)

vagy

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

A hálózat használatához a QPF bontását fordított sorrendben állítjuk össze, nevezetesen

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

Az alábbi ábra a hálózatot mutatja (a kimeneti qubitek fordított sorrendjében a közvetlen FFT-hez képest). $n:=3$

A fenti számítások szerint kapukat használnak, ami megfelel a . $n(n+1)/2=6$ $n=3$

Ezenkívül a következő hálózatok valósítanak meg 1-, 2- és 3-kbites FFT-ket: 1-, 2- és 3-kbites FFT-k vázlata és szimulációja Archiválva : 2019. március 23. a Wayback Machine -nél

Az ábra a 3 qubites FFT két különböző megvalósítását mutatja, amelyek egyenértékűek.

Lásd még

Fourier transzformáció

Jegyzetek

↑ Michael A. Nielsen és Isaac Chuan. Kvantumszámítás és kvantuminformáció, p. 217 (angol) . - Cambridge: Cambridge University Press , 2000. - ISBN 0-521-63503-9 .
↑ Hales, Hallgren, 2000 .
↑ Weinstein, Havel, Emerson és mtsai, 2004 .
↑ Ronald de Wolf , A klasszikus és kvantum Fourier-transzformáció, 1.1. A diszkrét Fourier-transzformáció, p. 1, (pdf) Archiválva : 2011. szeptember 12. a Wayback Machine -nél
↑ Thomas G. Draper, Addition on a Quantum Computer, p. 5, 1998. szeptember 1., (pdf) Archiválva : 2018. december 24. a Wayback Machine -nél

Irodalom

K. R. Parthasarathy , Lectures on Quantum Computation and Quantum Error Correcting Codes (Indian Statistical Institute, Delhi Center, 2001. június)
Preskill, John , Lecture Notes for Physics 229: Quantum Information and Computation (CIT, 1998. szeptember)
Hales L. R. , Hallgren S. Egy továbbfejlesztett kvantum Fourier transzformációs algoritmus és alkalmazások // FOCS 2000 : 41st Annual Symposium on Foundations of Computer Science, Redondo Beach, CA, USA, USA, november 12-14. 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 transzformáció // J. Chem. Phys / H. Urey , J. E. Mayer , Clyde A. Hutchison, Jr. , D. Levy , M. I. Lester - AIP , 2004. - 2004. évf. 121, Iss. 13. - P. 6117-6133. — ISSN 0021-9606 ; 1089-7690 ; 1520-9032 - doi:10.1063/1.1785151 - PMID:15446906 - arXiv:quant-ph/0406239

Linkek

Wolfram demonstrációs projekt: Quantum Circuit Implementing Grover's Search Algorithm Archiválva 2020. november 20-án a Wayback Machine -nél
Wolfram demonstrációs projekt: Quantum Circuit Implementing Quantum Fourier Transform Archiválva : 2018. december 22. a Wayback Machine -nél
Q-Kit: Grafikus kvantumáramkör-szimulátor archiválva 2019. március 23-án a Wayback Machine -nél
Quirk online life quantum Fourier transzformáció Archivált : 2019. január 1. a Wayback Machine -nél

kvantuminformatika

Általános fogalmak

kvantumkommunikáció

kvantumcsatorna
- kvantumhálózat
kvantumkriptográfia
- Kvantumkulcs-elosztás
A kvantumenergia teleportálása
kvantum teleportáció
Ultra-sűrű kvantumkódolás
LOCC
kvantum desztilláció

Kvantum algoritmusok

kvantum szimulátor
Deutsch-Yozhi algoritmus
Bernstein-Wazirani algoritmus
Grover algoritmusa
Kvantum Fourier transzformáció
Shor algoritmusa
Simon problémája
Kvantumfázis-becslési algoritmus
Kvantumszámítási algoritmus
kvantumlágyítás
Algoritmikus hűtés
Kvantumalgoritmus lineáris egyenletrendszer megoldására
Amplitúdó erősítés

Kvantumkomplexitás elmélet

Turing kvantumgép
EQP
BQP
QMA
PostBQP
QIP

Kvantum számítástechnikai modellek

kvantumkör
- kvantumkapu
Egyoldalas kvantumszámítógép
- fürt
Adiabatikus kvantumszámítás
Topológiai kvantumszámítógép

Dekoherencia megelőzés

Kvantumhibák korrekciója
Stabilizációs kódok
Stabilizációs formalizmus
Kvantumkonvolúciós kód

Fizikai megvalósítások

kvantumoptika	Kavitációs kvantumelektrodinamika Kontúrkvantumelektrodinamika Lineáris optikán alapuló kvantumszámítás KLM protokoll Bozonikus mintavétel
szuperhideg atomok	Elnyelt ion kvantumszámítógép Optikai rács
hát alapú	Mágneses magrezonancián alapuló kvantumszámítógép Kane kvantumszámítógépe Veszteséges kvantumszámítógép - DiVincenzo NV központ
Szupravezető kvantumszámítógépek	töltés qubit streaming qubit Fázis qubit Transmon