Kvantová Fourierova transformace - Quantum Fourier transform

V kvantové práce na počítači je kvantový Fourierova transformace (QFT) je lineární transformace na kvantové bitů , a je kvantový analog inverzní diskrétní Fourierova transformace . Kvantová Fourierova transformace je součástí mnoha kvantových algoritmů , zejména Shorův algoritmus pro factoring a výpočet diskrétní logaritmus , je algoritmus odhadu kvantové fázi pro odhad vlastní hodnoty z k jednotné obsluhy a algoritmů pro skryté podskupiny problému . Kvantovou Fourierovu transformaci objevil Don Coppersmith .

Kvantovou Fourierovu transformaci lze efektivně provést na kvantovém počítači se zvláštním rozkladem na produkt jednodušších unitárních matic . Pomocí jednoduchého rozkladu může být diskrétní Fourierova transformace na amplitudách implementována jako kvantový obvod skládající se pouze z Hadamardových bran a bran s řízeným fázovým posunem , kde je počet qubitů. To lze porovnat s klasickou diskrétní Fourierovou transformací, která bere brány (kde je počet bitů), což je exponenciálně více než . Kvantová Fourierova transformace však působí na kvantový stav, zatímco klasická Fourierova transformace působí na vektor, takže ne každý úkol, který používá klasickou Fourierovu transformaci, může využít tohoto exponenciálního zrychlení. ${\ displaystyle 2^{n}}$${\ displaystyle O (n^{2})}$ ${\ displaystyle n}$${\ Displaystyle O (n2^{n})}$${\ displaystyle n}$${\ displaystyle O (n^{2})}$

Nejlepší známé kvantové Fourierovy transformační algoritmy (ke konci roku 2000) vyžadují k dosažení efektivní aproximace pouze brány. ${\ Displaystyle O (n \ log n)}$

Definice

Kvantová Fourierova transformace je klasická diskrétní Fourierova transformace aplikovaná na vektor amplitud kvantového stavu, kde obvykle uvažujeme vektory délky . ${\ displaystyle N = 2^{n}}$

Klasický Fourierova transformace působí na vektoru a mapuje do vektoru podle vzorce: ${\ 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}}$

${\ 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,}$

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

Podobně kvantová Fourierova transformace působí na kvantový stav a mapuje jej do kvantového stavu podle vzorce: ${\ Displaystyle | x \ rangle = \ sum _ {i = 0}^{N-1} x_ {i} | i \ rangle}$${\ Displaystyle \ sum _ {i = 0}^{N-1} y_ {i} | i \ rangle}$

${\ 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,}$

(Konvence pro znaménko exponentu fázového faktoru se liší; zde používáme konvenci, že kvantová Fourierova transformace má stejný účinek jako inverzní diskrétní Fourierova transformace a naopak.)

Protože jde o rotaci, inverzní kvantová Fourierova transformace působí podobně, ale s: ${\ displaystyle \ omega _ {N}^{n}}$

${\ 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,}$

V případě, že se jedná o základní stav, může být kvantová Fourierova transformace vyjádřena také jako mapa ${\ displaystyle | x \ rangle}$

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

Ekvivalentně na kvantovou Fourierovu transformaci lze pohlížet jako na unitární matici (nebo na kvantovou bránu , podobnou logické bráně pro klasické počítače) působící na kvantové stavové vektory, kde je unitární matice dána vztahem ${\ displaystyle F_ {N}}$

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

kde . Získáme například v případě a fázovou transformační matici ${\ displaystyle \ omega = \ omega _ {N}}$${\ Displaystyle N = 4 = 2^{2}}$${\ Displaystyle \ omega = i}$

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

Vlastnosti

Jednota

Většina vlastností kvantové Fourierovy transformace vyplývá ze skutečnosti, že se jedná o unitární transformaci . To lze zkontrolovat provedením maticové násobení , a zajištění toho, že vztah platí, pokud je sdružený operátor z . Alternativně lze zkontrolovat, zda jsou ortogonální vektory normy 1 mapovány na ortogonální vektory normy 1. ${\ Displaystyle FF^{\ dagger} = F^{\ dagger} F = I}$${\ displaystyle F^{\ dagger}}$${\ displaystyle F}$

Z unitární vlastnosti vyplývá, že převrácenou kvantovou Fourierovou transformací je Hermitův adjunkt Fourierovy matice, tedy . Protože existuje účinný kvantový obvod implementující kvantovou Fourierovu transformaci, obvod může být spuštěn v opačném směru k provedení inverzní kvantové Fourierovy transformace. Obě transformace tedy lze efektivně provádět na kvantovém počítači. ${\ Displaystyle F^{-1} = F^{\ dagger}}$

Implementace obvodu

V kvantové brány použité v obvodu jsou Hadamardova brána a řízené fáze brána , zde z hlediska ${\ displaystyle R_ {m}}$

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

s primitivním -tým kořenem jednoty. Obvod se skládá z bran a řízené verze${\ Displaystyle e^{2 \ pi i/2^{m}} = \ omega _ {m} '= \ omega _ {\ left (2^{m} \ right)}}$${\ Displaystyle 2^{m}}$${\ displaystyle H}$${\ displaystyle R_ {m}}$

Jak již bylo řečeno, předpokládáme . Máme ortonormální základ sestávající z vektorů ${\ displaystyle N = 2^{n}}$

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

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

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

kde, s tenzor notace produktu , ukazuje, že qubit je ve stavu , s 0 nebo 1. Podle konvence je základem stav index je binární číslo kódovaná , s nejvýznamnějšího bitu. S touto konvencí můžeme kvantovou Fourierovu transformaci zapsat jako: ${\ Displaystyle \ otimes}$${\ displaystyle | x_ {j} \ rangle}$${\ displaystyle j}$${\ displaystyle x_ {j}}$${\ displaystyle x_ {j}}$${\ displaystyle x}$${\ displaystyle x_ {j}}$${\ displaystyle x_ {1}}$

${\ Displaystyle {\ text {QFT}} (| x \ \ rangle) = {\ frac {1} {\ sqrt {N}}} \ bigotimes _ {j = 1}^{n} \ left (| 0 \ rangle +\ omega _ {n} '^{x2^{nj}} | 1 \ rangle \ right).}$

Je také užitečné vypůjčit si zlomkovou binární notaci:

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

S tímto zápisem lze akci kvantové Fourierovy transformace vyjádřit kompaktním způsobem:

${\ displaystyle {\ text {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).}$

K získání tohoto stavu z výše zobrazeného obvodu je třeba provést swapovou operaci qubitů, aby se obrátilo jejich pořadí. Vyžadována je většina swapů. ${\ displaystyle n/2}$

Jinými slovy, diskrétní Fourierova transformace, operace na n qubitech, může být zapracována do tenzorového součinu n jednokqubitových operací, což naznačuje, že je snadno reprezentován jako kvantový obvod (až do obrácení pořadí výstupu). Ve skutečnosti lze každou z těchto operací s jedním qubitem implementovat efektivně pomocí brány Hadamard a řízených fázových bran . První termín vyžaduje jednu bránu Hadamard a brány s řízenou fází, další vyžaduje bránu Hadamard a bránu s řízenou fází a každý následující termín vyžaduje o jednu bránu s řízenou fází méně. Shrnutím počtu bran, s výjimkou těch, které jsou potřebné pro obrácení výstupu, dostaneme brány, což je kvadratický polynom v počtu qubitů. ${\ Displaystyle (n-1)}$${\ Displaystyle (n-2)}$${\ Displaystyle n+(n-1)+\ cdots+1 = n (n+1)/2 = O (n^{2})}$

Příklad

Zvažte kvantovou Fourierovu transformaci na 3 qubitech. Jedná se o následující transformaci:

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

kde (od ) uspokojuje primitivní osmý kořen jednoty . ${\ displaystyle \ omega _ {3} '= \ omega _ {\ left (2^{3} \ right)}}$${\ Displaystyle \ omega _ {3} '^{8} = \ left (e^{\ frac {2 \ pi i} {2^{3}}} \ right)^{8} = 1}$${\ displaystyle N = 2^{3} = 8}$

Stručně řečeno, maticová reprezentace této transformace na 3 qubitech je: ${\ displaystyle \ omega = \ omega _ {3} '= \ omega _ {8}}$

${\ Displaystyle 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} & 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} }.}$

3kvbitovou kvantovou Fourierovu transformaci lze přepsat jako:

${\ displaystyle {\ text {QFT}} (| x_ {1}, x_ {2}, x_ {3} \ rangle) = {\ frac {1} {\ sqrt {2^{3}}}} \ \ vlevo (| 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).}$

V následujícím náčrtu máme příslušný obvod pro (se špatným pořadím výstupních qubitů vzhledem ke správnému QFT): ${\ displaystyle n = 3}$

Jak bylo vypočítáno výše, počet použitých bran je stejný jako pro . ${\ Displaystyle n (n+1)/2}$${\ displaystyle 6}$${\ displaystyle n = 3}$

Vztah ke kvantové Hadamardově transformaci

Pomocí zobecněné Fourierovy transformace na konečných (abelianských) skupinách existují ve skutečnosti dva přirozené způsoby, jak definovat kvantovou Fourierovu transformaci na n-qubitovém kvantovém registru . Výše definovaný QFT je ekvivalentní DFT, který tyto n qubity považuje za indexované cyklickou skupinou . Má však také smysl považovat qubity za indexované booleovskou skupinou a v tomto případě je Fourierova transformace Hadamardovou transformací . Toho je dosaženo paralelním použitím Hadamardovy brány na každý z n qubits. Všimněte si, že Shorův algoritmus používá oba typy Fourierových transformací, jak počáteční Hadamardovu transformaci, tak QFT. ${\ Displaystyle \ mathbb {Z} /2^{n} \ mathbb {Z}}$ ${\ Displaystyle (\ mathbb {Z} /2 \ mathbb {Z})^{n}}$

Reference

• KR Parthasarathy , Přednášky o kvantových výpočtech a opravách kódů kvantových chyb (Indický statistický institut, Dillí centrum, červen 2001)
• John Preskill , Lecture Notes for Physics 229: Quantum Information and Computation (CIT, September 1998)

externí odkazy

• Wolfram Demonstration Project: Quantum Circuit Implementing Grover's Search Algorithm
• Wolfram Demonstration Project: Quantum Circuit Implementing Quantum Fourier Transform
• Quirk kvantová Fourierova transformace online života