Kvantová Fourierova transformace - Quantum Fourier transform - Wikipedia

v kvantové výpočty, kvantová Fourierova transformace (zkráceně: QFT) je a lineární transformace na kvantové bity, a je kvantovým analogem inverzní diskrétní Fourierova transformace. Kvantová Fourierova transformace je součástí mnoha kvantové algoritmy, zejména Shorův algoritmus pro factoring a výpočet diskrétní logaritmus, algoritmus odhadu kvantové fáze pro odhad vlastní čísla a nečleněný operátor a algoritmy pro skrytý problém s podskupinou. Kvantovou Fourierovu transformaci vynalezl Don Coppersmith.^[1]

Kvantovou Fourierovu transformaci lze efektivně provádět na kvantovém počítači se zvláštním rozkladem na produkt jednoduššího unitární matice. Pomocí jednoduchého rozkladu se diskrétní Fourierova transformace zapne ${ displaystyle 2 ^ {n}}$ amplitudy lze implementovat jako a kvantový obvod skládající se pouze z ${ displaystyle O (n ^ {2})}$ Hadamardovy brány a kontrolované brány fázového posuvu, kde ${ displaystyle n}$ je počet qubitů.^[2] To lze srovnat s klasickou diskrétní Fourierovou transformací, která trvá ${ displaystyle O (n2 ^ {n})}$ brány (kde ${ displaystyle n}$ je počet bitů), což je exponenciálně více než ${ displaystyle O (n ^ {2})}$ . 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í.^{[Citace je zapotřebí ]}

Nejlepší známé kvantové algoritmy Fourierovy transformace (od konce roku 2000) vyžadují pouze ${ displaystyle O (n log n)}$ brány k dosažení efektivní aproximace.^[3]

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

The klasická Fourierova transformace působí na a vektor ${ displaystyle (x_ {0}, x_ {1}, ldots, x_ {N-1}) in mathbb {C} ^ {N}}$ a mapuje to na vektor ${ displaystyle (y_ {0}, y_ {1}, ldots, y_ {N-1}) in mathbb {C} ^ {N}}$ podle vzorce:

{ 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 ${ displaystyle omega _ {N} = e ^ { frac {2 pi i} {N}}}$ a ${ displaystyle omega _ {N} ^ {n}}$ je N^th kořen jednoty.

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

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

Od té doby ${ displaystyle omega _ {N} ^ {n}}$ je rotace, inverzní kvantová Fourierova transformace jedná podobně, ale s:

{ displaystyle x_ {n} = { frac {1} { sqrt {N}}} součet _ {k = 0} ^ {N-1} y_ {k} omega _ {N} ^ {- nk }, quad n = 0,1,2, ldots, N-1,}

V případě že ${ displaystyle | x rangle}$ je základní stav, lze kvantovou Fourierovu transformaci vyjádřit také jako mapu

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

Ekvivalentně lze kvantovou Fourierovu transformaci považovat za jednotnou matici (nebo a kvantová brána, podobně jako booleovský logická brána pro klasické počítače) působící na vektory kvantového stavu, kde je jednotná matice ${ displaystyle F_ {N}}$ darováno

{ 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 ${ displaystyle omega = omega _ {N}}$ . Dostaneme například v případě ${ displaystyle N = 4 = 2 ^ {2}}$ a fáze ${ displaystyle omega = i}$ transformační matice

{ 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

Jednotnost

Většina vlastností kvantové Fourierovy transformace vyplývá ze skutečnosti, že jde o a unitární transformace. To lze zkontrolovat provedením násobení matic a zajištění toho vztahu ${ displaystyle FF ^ { dagger} = F ^ { dagger} F = I}$ drží, kde ${ displaystyle F ^ { dagger}}$ je Hermitian adjoint z ${ displaystyle F}$ . Alternativně lze zkontrolovat ortogonální vektory norma 1 se namapuje na ortogonální vektory normy 1.

Z jednotkové vlastnosti vyplývá, že inverzní funkce kvantové Fourierovy transformace je Hermitian adjoint Fourierovy matice, tedy ${ displaystyle F ^ {- 1} = F ^ { dagger}}$ . Vzhledem k tomu, že existuje efektivní kvantový obvod implementující kvantovou Fourierovu transformaci, může být obvod spuštěn opačně a provést inverzní kvantovou Fourierovu transformaci. Obě transformace lze tedy efektivně provádět na kvantovém počítači.

Implementace obvodu

The kvantové brány používané v obvodu jsou Hadamardova brána a kontrolované fázová brána ${ displaystyle R_ {m}}$ , zde z hlediska

{ 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 ^ { frac {2 pi i} {2 ^ {m}}} end {pmatrix}}}

s ${ displaystyle e ^ { frac {2 pi i} {2 ^ {m}}} = omega _ {m} '= omega _ { left (2 ^ {m} right)}}$ primitivní ${ displaystyle 2 ^ {m}}$ -tý kořen jednoty. Obvod se skládá z ${ displaystyle H}$ brány a kontrolované verze ${ displaystyle R_ {m}}$

Všechny kvantové operace musí být lineární, takže stačí popsat funkci v každém ze základních stavů a nechat smíšené stavy definovat linearitou. To je v kontrastu s tím, jak jsou obvykle popsány Fourierovy transformace. Normálně popisujeme Fourierovy transformace, pokud jde o způsob výpočtu složek výsledků na libovolném vstupu. Takto byste vypočítali cesta integrální nebo ukázat BQP je v PP. Ale je zde mnohem jednodušší (a v mnoha případech) pouze vysvětlit, co se stane s konkrétním stavem libovolného základu, a celkový výsledek lze zjistit podle linearity.

Kvantovou Fourierovu transformaci lze přibližně implementovat pro jakoukoli N; implementace však pro případ, kdy N je síla 2 je mnohem jednodušší. Jak již bylo uvedeno, předpokládáme ${ displaystyle N = 2 ^ {n}}$ . Máme ortonormální základ skládající se z vektorů

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

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

{ 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 se zápisem tenzorového produktu ${ displaystyle otimes}$ , ${ displaystyle | x_ {j} rangle}$ naznačuje, že qubit ${ displaystyle j}$ je ve stavu ${ displaystyle x_ {j}}$ , s ${ displaystyle x_ {j}}$ buď 0 nebo 1. Podle konvence index základního stavu ${ displaystyle x}$ objednává možné stavy qubits lexikograficky, tj. převodem z binárního na desítkové takto:

{ displaystyle x = x_ {1} 2 ^ {n-1} + x_ {2} 2 ^ {n-2} + cdots + x_ {n} 2 ^ {0}. quad}

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

{ displaystyle [0.x_ {1} ldots x_ {m}] = součet _ {k = 1} ^ {m} x_ {k} 2 ^ {- k}.}

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

S touto notací 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}}} vlevo (| 0 rangle + e ^ {2 pi i , [0.x_ {n}]} | 1 rangle pravé) otimes levé (| 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

{ displaystyle { text {QFT}} (| x_ {1} x_ {2} ldots x_ {n} rangle) = { frac {1} { sqrt {N}}} vlevo (| 0 rangle + omega _ {1} '^ {[x_ {n}]} | 1 rangle right) otimes left (| 0 rangle + omega _ {2}' ^ {[x_ {n- 1} x_ {n}]} | 1 rangle right) otimes cdots otimes left (| 0 rangle + omega _ {n} '^ {[x_ {1} ... x_ {n- 1} x_ {n}]} | 1 rangle right).}

kde jsme použili:

{ displaystyle [0.x_ {1} x_ {2} ... x_ {m}] = [x_ {1} x_ {2} ... x_ {n}] / 2 ^ {m}}

a

{ displaystyle omega _ {m} '= omega _ { left ({2 ^ {m}} right)} = e ^ {2 pi i / 2 ^ {m}}.}

To lze vidět přepsáním vzorce pro Fourierovu transformaci v binární expanzi:

{ displaystyle { text {QFT}} (| x rangle) = { frac {1} { sqrt {N}}} součet _ {k = 0} ^ {2 ^ {n} -1} omega _ {N} ^ {xk} | k rangle = { frac {1} { sqrt {N}}} sum _ {k_ {1} in {0,1 }} sum _ { k_ {2} in {0,1 }} ldots sum _ {k_ {n} in {0,1 }} omega _ {N} ^ {x sum _ {j = 1 } ^ {n} k_ {j} 2 ^ {nj}} | k_ {1} k_ {2} ldots k_ {n} rangle}

${ displaystyle = { frac {1} { sqrt {N}}} sum _ {k_ {1} in {0,1 }} sum _ {k_ {2} in {0, 1 }} ldots sum _ {k_ {n} in {0,1 }} bigotimes _ {j = 1} ^ {n} omega _ {N} ^ {xk_ {j} 2 ^ {nj}} | k_ {j} rangle = { frac {1} { sqrt {N}}} sum _ {k_ {1} in {0,1 }} sum _ {k_ { 2} in {0,1 }} ldots sum _ {k_ {n} in {0,1 }} omega _ {N} ^ {xk_ {1} 2 ^ {n-1 }} | k_ {1} rangle otimes bigotimes _ {j = 2} ^ {n} omega _ {N} ^ {xk_ {j} 2 ^ {nj}} | k_ {j} rangle}$

${ displaystyle = { frac {1} { sqrt {N}}} vlevo ( sum _ {k_ {1} in {0,1 }} omega _ {N} ^ {xk_ {1 } 2 ^ {n-1}} | k_ {1} rangle right) otimes sum _ {k_ {2} in {0,1 }} ldots sum _ {k_ {n} v {0,1 }} omega _ {N} ^ {xk_ {2} 2 ^ {n-2}} | k_ {2} rangle otimes bigotimes _ {j = 3} ^ {n} omega _ {N} ^ {xk_ {j} 2 ^ {nj}} | k_ {j} rangle}$

${ displaystyle = { frac {1} { sqrt {N}}} vlevo ( sum _ {k_ {1} in {0,1 }} omega _ {N} ^ {xk_ {1 } 2 ^ {n-1}} | k_ {1} rangle right) otimes left ( sum _ {k_ {2} in {0,1 }} omega _ {N} ^ { xk_ {2} 2 ^ {n-2}} | k_ {2} rangle right) otimes sum _ {k_ {3} in {0,1 }} ldots sum _ {k_ { n} in {0,1 }} omega _ {N} ^ {xk_ {3} 2 ^ {n-3}} | k_ {3} rangle otimes bigotimes _ {j = 4} ^ {n} omega _ {N} ^ {xk_ {j} 2 ^ {nj}} | k_ {j} rangle = dots}$

${ displaystyle = { frac {1} { sqrt {N}}} bigotimes _ {j = 1} ^ {n} sum _ {k_ {j} in {0,1 }} omega _ {N} ^ {xk_ {j} 2 ^ {nj}} | k_ {j} rangle = { frac {1} { sqrt {N}}} bigotimes _ {j = 1} ^ {n} left (| 0 rangle + omega _ {N} ^ {x2 ^ {nj}} | 1 rangle right).}$

Nyní:

{ displaystyle omega _ {N} ^ {x2 ^ {nj}} = e ^ {{ frac {2 pi i} {2 ^ {n}}} x2 ^ {nj}} = e ^ {{2 pi i} (x2 ^ {- j})} (2)}

.

Nechat ${ displaystyle f (j) = x2 ^ {- j} = 2 ^ {- j} součet _ {r = 1} ^ {n} x_ {r} 2 ^ {nr} = součet _ {r = 1 } ^ {n} x_ {r} 2 ^ {njr} = sum _ {r = 1} ^ {nj} x_ {r} 2 ^ {njr} + sum _ {r = n-j + 1} ^ {n} x_ {r} 2 ^ {njr} = a (j) + b (j);}$

pak ${ displaystyle a (j) epsilon mathbb {N} _ {0}}$ , protože ${ displaystyle 2 ^ {n-j-r} geq 0}$ , pro ${ displaystyle n-j-r geq 0}$ , a ${ displaystyle b (j) = 0,x_ {n-j + 1} x_ {n-j + 2} tečky x_ {n}}$ , tedy ${ displaystyle (2)}$ se stává:

{ displaystyle e ^ {{2 pi i} f (j)} = e ^ {{2 pi i} (a (j) + b (j))} = e ^ {{2 pi i} a (j)} cdot e ^ {{2 pi i} b (j)} = e ^ {{2 pi i} [0,x_ {n-j + 1} x_ {n-j + 2} cdots x_ {n}]},}

od té doby ${ displaystyle e ^ {{2 pi i} a (j)} = (e ^ {2 pi i}) ^ {a (j)} = 1}$ pro všechny ${ displaystyle j}$ .

Pak můžeme napsat:

{ displaystyle { text {QFT}} (| x_ {1} x_ {2} tečky x_ {n} rangle) = { frac {1} { sqrt {N}}} bigotimes _ {j = 1} ^ {n} left (| 0 rangle + omega _ {N} ^ {x2 ^ {nj}} | 1 rangle right) = { frac {1} { sqrt {N}}} bigotimes _ {j = 1} ^ {n} left (| 0 rangle + e ^ {2 pi i [0.x_ {n-j + 1} x_ {n-j + 2} ldots x_ { n}]} | 1 rangle right)}

${ displaystyle = { frac {1} { sqrt {N}}} vlevo (| 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 dots otimes left (| 0 rangle + e ^ {2 pi i [0.x_ {1} x_ {2} ldots x_ {n}]} | 1 rangle right).}$

Chcete-li získat tento stav z obvodu zobrazeného výše, je třeba provést swapové operace qubits, aby se obrátilo jejich pořadí. Nejvíce ${ displaystyle n / 2}$ swapy jsou povinné, přičemž každý z nich se provádí pomocí tří kontrolováno-NE (C-NOT) brány.^[2]

Po obrácení se n-výstup qubit bude ve stavu superpozice ${ displaystyle | 0 rangle}$ a ${ displaystyle e ^ {2 pi i , [0.x_ {1} ... x_ {n}]} | 1 rangle}$ , a podobně ostatní qubits před tím (druhý pohled na náčrt obvodu výše).

Jinými slovy, diskrétní Fourierova transformace, operace zapnutá n qubits, lze zapracovat do tenzorového produktu n single-qubit operace, což naznačuje, že je snadno reprezentován jako kvantový obvod (až do obrácení objednávky na výstupu). Ve skutečnosti lze každou z těchto operací s jedním qubitem implementovat efektivně pomocí a Hadamardova brána a kontrolované fázové brány. První termín vyžaduje jednu Hadamardovu bránu a ${ displaystyle (n-1)}$ řízené fázové brány, další vyžaduje Hadamardovu bránu a ${ displaystyle (n-2)}$ řízená fázová brána a každý následující termín vyžaduje o jednu méně kontrolovanou fázovou bránu. Součet počtu bran, vyjma těch, které jsou potřebné pro obrácení výstupu, dává ${ Displaystyle n + (n-1) + cdots + 1 = n (n + 1) / 2 = O (n ^ {2})}$ brány, což je kvadratický polynom v počtu qubitů.

Příklad

Zvažte kvantovou Fourierovu transformaci na 3 qubits. 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 ${ displaystyle omega _ {3} '= omega _ { vlevo (2 ^ {3} doprava)}}$ je primitivní osmá kořen jednoty uspokojující ${ displaystyle omega _ {3} '^ {8} = vlevo (e ^ { frac {2 pi i} {2 ^ {3}}} vpravo) ^ {8} = 1}$ (od té doby ${ displaystyle N = 2 ^ {3} = 8}$ ).

Zkrátka nastavení ${ displaystyle omega = omega _ {3} '= omega _ {8}}$ , maticová reprezentace této transformace na 3 qubits je:

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

Mohlo by to být dále zjednodušeno použitím ${ displaystyle omega ^ {4} = - 1}$ , ${ displaystyle omega ^ {2} = i}$ a ${ displaystyle omega ^ {6} = - i}$

a pak ještě více ${ displaystyle omega ^ {5} = - omega}$ , ${ displaystyle omega ^ {3} = i omega}$ a ${ displaystyle omega ^ {7} = - i omega}$ .

3kbitovou kvantovou Fourierovu transformaci lze přepsat jako:

{ displaystyle { text {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

{ displaystyle { text {QFT}} (| x_ {1}, x_ {2}, x_ {3} rangle) = { frac {1} { sqrt {2 ^ {3}}}}} left (| 0 rangle + omega _ {1} '^ {[x_ {3}]} | 1 rangle right) otimes left (| 0 rangle + omega _ {2}' ^ {[ x_ {2} x_ {3}]} | 1 rangle right) otimes left (| 0 rangle + omega _ {3} '^ {[x_ {1} x_ {2} x_ {3}] } | 1 rangle right).}

V případě, že použijeme obvod, získáme faktorizaci v opačném pořadí, jmenovitě

{ displaystyle | x_ {1}, x_ {2}, x_ {3} rangle longmapsto { frac {1} { sqrt {2 ^ {3}}}}} left (| 0 rangle + omega _ {3} '^ {[x_ {1} x_ {2} x_ {3}]} | 1 rangle right) otimes left (| 0 rangle + omega _ {2}' ^ {[ x_ {2} x_ {3}]} | 1 rangle right) otimes left (| 0 rangle + omega _ {1} '^ {[x_ {3}]} | 1 rangle right) .}

Zde jsme použili notace jako:

{ displaystyle [0.x_ {1} x_ {2} x_ {3}] = [x_ {1} x_ {2} x_ {3}] / 2 ^ {3}}

a

{ displaystyle omega _ {m} '= omega _ { left (2 ^ {m} right)} = e ^ {2 pi i / 2 ^ {m}}.}

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

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

Reference

^ Coppersmith, D. (1994). "Přibližná Fourierova transformace užitečná při kvantovém factoringu". Technická zpráva RC19642, IBM.
^ ^A ^b Michael Nielsen a Isaac Chuang (2000). Kvantové výpočty a kvantové informace. Cambridge: Cambridge University Press. ISBN 0-521-63503-9. OCLC 174527496.
^ Hales, L .; Hallgren, S. (12. – 14. Listopadu 2000). "Vylepšený algoritmus a aplikace kvantové Fourierovy transformace". Sborník 41. výroční sympozium o základech informatiky: 515–525. CiteSeerX 10.1.1.29.4161. doi:10.1109 / SFCS.2000.892139. ISBN 0-7695-0850-2. S2CID 424297.

K. R. Parthasarathy, Přednášky o kvantovém výpočtu a kódech pro opravu chyb (Indický statistický institut, Dillí, červen 2001)
John Preskill, Přednášky z fyziky 229: Kvantové informace a výpočet (CIT, září 1998)

externí odkazy

[dc_qft-1] Coppersmith, D. (1994). "Přibližná Fourierova transformace užitečná při kvantovém factoringu". Technická zpráva RC19642, IBM.

[:0-2] A ^b Michael Nielsen a Isaac Chuang (2000). Kvantové výpočty a kvantové informace. Cambridge: Cambridge University Press. ISBN 0-521-63503-9. OCLC 174527496.

[3] Hales, L .; Hallgren, S. (12. – 14. Listopadu 2000). "Vylepšený algoritmus a aplikace kvantové Fourierovy transformace". Sborník 41. výroční sympozium o základech informatiky: 515–525. CiteSeerX 10.1.1.29.4161. doi:10.1109 / SFCS.2000.892139. ISBN 0-7695-0850-2. S2CID 424297.

[1]

[2]

[3]