Transformată cuantică Fourier

În calculul cuantic , transformata cuantică Fourier (prescurtare din engleză: QFT) este o transformare liniară pe qubits și este analogul cuantic al transformatei Fourier discrete inverse. Transformata Fourier cuantică face parte din mulți algoritmi cuantici , în special algoritmul de factorizare Shor pentru a calcula și calcula logaritmul discret , algoritmul de estimare a fazei cuantice pentru a estima valorile proprii ale unui operator de unitate și algoritmi pentru problema subgrupului ascuns. Transformata cuantică Fourier a fost inventată de Don Coppersmith . ^[1]

Transformarea Fourier cuantică poate fi efectuată eficient pe un computer cuantic, cu o descompunere specială într-un produs de matrice unitare mai simple. Folosind o descompunere simplă, transforma Fourier discretă se aprinde $2^{n}$ ${\ displaystyle 2 ^ {n}}$ $2 ^ {n}$ amplitudinile pot fi implementate ca un circuit cuantic format doar din $O(n^{2})$ ${\ displaystyle O (n ^ {2})}$ $O (n ^ {2})$ Porțile Hadamard și porțile de fază controlate, unde $n$ ${\ displaystyle n}$ $n$ este numărul de qubiți. ^[2] Acest lucru poate fi comparat cu transformata Fourier discretă clasică, care are $O(n2^{n})$ ${\ displaystyle O (n2 ^ {n})}$ ${\ displaystyle O (n2 ^ {n})}$ uși (unde $n$ ${\ displaystyle n}$ $n$ este numărul de biți), care este exponențial mai mare decât $O(n^{2})$ ${\ displaystyle O (n ^ {2})}$ $O (n ^ {2})$ .

Cei mai cunoscuți algoritmi pentru transforma cuantică Fourier (de la sfârșitul anilor 2000) au nevoie doar $O(n\log n)$ ${\ displaystyle O (n \ log n)}$ $O (n \ log n)$ porturi pentru a obține o bună aproximare. ^[3]

Definiție

Transformata Fourier cuantică este transformata Fourier clasică aplicată vectorului de amplitudine al unei stări cuantice, unde vectorii de lungime sunt de obicei considerați $N=2^{n}$ ${\ displaystyle N = 2 ^ {n}}$ ${\ displaystyle N = 2 ^ {n}}$ .

Transformata Fourier clasică acționează asupra unui vector $(x_{0},x_{1},\ldots ,x_{N-1})\in \mathbb {C} ^{N}$ ${\ displaystyle (x_ {0}, x_ {1}, \ ldots, x_ {N-1}) \ in \ mathbb {C} ^ {N}}$ ${\ displaystyle (x_ {0}, x_ {1}, \ ldots, x_ {N-1}) \ in \ mathbb {C} ^ {N}}$ și o mapează la vector $(y_{0},y_{1},\ldots ,y_{N-1})\in \mathbb {C} ^{N}$ ${\ displaystyle (y_ {0}, y_ {1}, \ ldots, y_ {N-1}) \ in \ mathbb {C} ^ {N}}$ ${\ displaystyle (y_ {0}, y_ {1}, \ ldots, y_ {N-1}) \ in \ mathbb {C} ^ {N}}$ conform formulei:

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

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

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

unde este $\omega _{N}=e^{\frac {2\pi i}{N}}$ ${\ displaystyle \ omega _ {N} = e ^ {\ frac {2 \ pi i} {N}}}$ ${\ displaystyle \ omega _ {N} = e ^ {\ frac {2 \ pi i} {N}}}$ Și $\omega _{N}^{n}$ ${\ displaystyle \ omega _ {N} ^ {n}}$ ${\ displaystyle \ omega _ {N} ^ {n}}$ si $Nu.$ ${\ displaystyle N}$ $Nu.$ -rădăcina a unității .

În mod similar, transformata cuantică Fourier acționează asupra unei stări cuantice $|x\rangle =\sum _{i=0}^{N-1}x_{i}|i\rangle$ ${\ displaystyle | x \ rangle = \ sum _ {i = 0} ^ {N-1} x_ {i} | i \ rangle}$ ${\ displaystyle | x \ rangle = \ sum _ {i = 0} ^ {N-1} x_ {i} | i \ rangle}$ și o mapează la o stare cuantică $\sum _{i=0}^{N-1}y_{i}|i\rangle$ ${\ displaystyle \ sum _ {i = 0} ^ {N-1} y_ {i} | i \ rangle}$ ${\ displaystyle \ sum _ {i = 0} ^ {N-1} y_ {i} | i \ rangle}$ conform formulei:

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

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

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

(Convențiile pentru semnul factorului de fază către exponent sunt multiple; aici folosim convenția conform căreia transformarea are același efect ca transformarea inversă și invers.)

De cand $\omega _{N}^{n}$ ${\ displaystyle \ omega _ {N} ^ {n}}$ ${\ displaystyle \ omega _ {N} ^ {n}}$ este o rotație, transformata inversă acționează similar, dar cu:

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

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

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

În cazul în care $|x\rangle$ ${\ displaystyle | x \ rangle}$ ${\ displaystyle | x \ rangle}$ este o stare de bază, transformata cuantică Fourier (QFT) poate fi exprimată ca hartă

{\text{QFT}}:|x\rangle \mapsto {\frac {1}{\sqrt {N}}}\sum _{k=0}^{N-1}\omega _{N}^{xk}|k\rangle .

{\ displaystyle {\ text {QFT}}: | x \ rangle \ mapsto {\ frac {1} {\ sqrt {N}}} \ sum _ {k = 0} ^ {N-1} \ omega _ {N } ^ {xk} | k \ rangle.}

{\ displaystyle {\ text {QFT}}: | x \ rangle \ mapsto {\ frac {1} {\ sqrt {N}}} \ sum _ {k = 0} ^ {N-1} \ omega _ {N } ^ {xk} | k \ rangle.}

În mod echivalent, transformarea poate fi văzută ca o matrice unitară $F_{N}$ ${\ displaystyle F_ {N}}$ ${\ displaystyle F_ {N}}$ (sau o poartă cuantică , similară cu o poartă logică booleană pentru calculatoare clasice), acționând asupra vectorilor de stare cuantică, date de

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

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

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

unde este $\omega =\omega _{N}$ ${\ displaystyle \ omega = \ omega _ {N}}$ ${\ displaystyle \ omega = \ omega _ {N}}$ . În cazul în care $N=4=2^{2}$ ${\ displaystyle N = 4 = 2 ^ {2}}$ ${\ displaystyle N = 4 = 2 ^ {2}}$ și fază $\omega =i$ ${\ displaystyle \ omega = i}$ ${\ displaystyle \ omega = i}$ matricea de transformare devine

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

{\ displaystyle 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}}}

{\ displaystyle 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}}}

Proprietate

Unitate

Majoritatea proprietăților transformatei Fourier cuantice decurg din faptul că este o transformare unitară. Acest lucru poate fi verificat prin multiplicarea matricelor și asigurarea faptului că relația se menține $FF^{\dagger }=F^{\dagger }F=I$ ${\ displaystyle FF ^ {\ dagger} = F ^ {\ dagger} F = I}$ ${\ displaystyle FF ^ {\ dagger} = F ^ {\ dagger} F = I}$ , unde este $F^{\dagger }$ ${\ displaystyle F ^ {\ dagger}}$ ${\ displaystyle F ^ {\ dagger}}$ este adăugarea de $F.$ ${\ displaystyle F}$ $F.$ . Alternativ, se poate vedea că vectorii ortogonali ai normei 1 sunt mapați la vectorii ortogonali ai normei 1.

Din unitaritate rezultă că transformarea inversă este adăugarea matricei Fourier, $F^{-1}=F^{\dagger }$ ${\ displaystyle F ^ {- 1} = F ^ {\ dagger}}$ ${\ displaystyle F ^ {- 1} = F ^ {\ dagger}}$ . Deoarece există circuite care implementează transformarea, aceleași circuite pot fi activate pe căi inversate pentru a efectua transformarea inversă. Deci, ambele transformări pot fi efectuate eficient pe un computer cuantic.

Implementarea într-un circuit

Porțile cuantice utilizate în circuit sunt poarta Hadamard și poarta cu fază controlată $R_{m}$ ${\ displaystyle R_ {m}}$ ${\ displaystyle R_ {m}}$ , definit ca

H={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&1\\1&-1\end{pmatrix}}\qquad {\text{e}}\qquad R_{m}={\begin{pmatrix}1&0\\0&e^{\frac {2\pi i}{2^{m}}}\end{pmatrix}}

{\ displaystyle H = {\ frac {1} {\ sqrt {2}}} {\ begin {pmatrix} 1 & 1 \\ 1 & -1 \ end {pmatrix}} \ qquad {\ text {e}} \ qquad R_ {m} = {\ begin {pmatrix} 1 & 0 \\ 0 & e ^ {\ frac {2 \ pi i} {2 ^ {m}}} \ end {pmatrix}}}

{\ displaystyle H = {\ frac {1} {\ sqrt {2}}} {\ begin {pmatrix} 1 & 1 \\ 1 & -1 \ end {pmatrix}} \ qquad {\ text {e}} \ qquad R_ {m} = {\ begin {pmatrix} 1 & 0 \\ 0 & e ^ {\ frac {2 \ pi i} {2 ^ {m}}} \ end {pmatrix}}}

unde este $e^{\frac {2\pi i}{2^{m}}}=\omega _{m}'=\omega _{\left(2^{m}\right)}$ ${\ displaystyle e ^ {\ frac {2 \ pi i} {2 ^ {m}}} = \ omega _ {m} '= \ omega _ {\ left (2 ^ {m} \ right)}}$ ${\ displaystyle e ^ {\ frac {2 \ pi i} {2 ^ {m}}} = \ omega _ {m} '= \ omega _ {\ left (2 ^ {m} \ right)}}$ si $2^{m}$ ${\ displaystyle 2 ^ {m}}$ ${\ displaystyle 2 ^ {m}}$ -rădăcina a unității. Prin urmare, circuitul este compus din porți $H.$ ${\ displaystyle H}$ $H.$ și versiunea controlată a $R_{m}$ ${\ displaystyle R_ {m}}$ ${\ displaystyle R_ {m}}$

$Circuit cuantic pentru Transformare-Fourier cuantică cu n qubiți (fără a rearanja ordinea stărilor de ieșire). Folosește notația fracției binare introdusă mai jos.$

Notă

^ D. Coppersmith, O transformată Fourier aproximativă utilă în factorizarea cuantică. , în Raportul tehnic RC19642, IBM , 1994.
^ Michael Nielsen și Isaac Chuang, Calcul cuantic și informații cuantice , Cambridge, Cambridge University Press, 2000, ISBN 0-521-63503-9 ,OCLC 174527496 .
^ L. Hales și S. Hallgren, Un algoritm și aplicații îmbunătățite ale transformatei Fourier cuantice , în Proceedings 41st Symposium anual privind fundamentele de informatică , 12-14 noiembrie 2000, pp. 515-525, DOI : 10.1109 / SFCS.2000.892139 , ISBN 0-7695-0850-2 .

KR Parthasarathy, Prelegeri despre calculul cuantic și codurile de corectare a erorilor cuantice (Indian Statistical Institute, Delhi Center, iunie 2001)
John Preskill, Lecture Notes for Physics 229: Quantum Information and Computation (CIT, septembrie 1998)

linkuri externe

[dc_qft-1] D. Coppersmith, O transformată Fourier aproximativă utilă în factorizarea cuantică. , în Raportul tehnic RC19642, IBM , 1994.

[:0-2] Michael Nielsen și Isaac Chuang, Calcul cuantic și informații cuantice , Cambridge, Cambridge University Press, 2000, ISBN 0-521-63503-9 ,OCLC 174527496 .

[3] L. Hales și S. Hallgren, Un algoritm și aplicații îmbunătățite ale transformatei Fourier cuantice , în Proceedings 41st Symposium anual privind fundamentele de informatică , 12-14 noiembrie 2000, pp. 515-525, DOI : 10.1109 / SFCS.2000.892139 , ISBN 0-7695-0850-2 .

[1]

[2]

[3]