náhled|350px|Obvod pro kvantovou Fourierovu transformaci na třech qbitech. náhled|350px|Obvod pro KFT na n qbitech (vyjádřeno rekurzivně). Kvantová Fourierova transformace (KFT) je implementací diskrétní Fourierovy transformace (DFT) pro kvantové počítače. Je základem pro celou třídu kvantových algoritmů, které nabízejí urychlení oproti nejrychlejším známým klasickým algoritmům.
Kvantová Fourierova transformace na bázi qbitů je v jistém smyslu stejná, jako diskrétní Fourierova transformace na koeficientech rozvoje do báze. KFT je provedena na amplitudách pravděpodobnosti a není schopna poskytnout urychlení výpočtu na klasických datech. KFT je unitární operací (standardně značené ), a tedy ji lze vyjádřit pomocí unitární matice.
Stejně jako matice reprezentující DFT má i maticové vyjádření KFT stejnou stavbu jako Vandermondova matice. Ve speciálním případě pro 1 qbit je matice reprezentující KFT totožná s Hadamardovou maticí reprezentující Hadamardovo hradlo.
Definice Kvantová Fourierova transformace je definována jako unitární transformace, která zobrazuje bázové stavy podle předpisu ,Višňák, str. 86 kde čísla číslují bázové vektory , a je komplexní jednotka. Definiční předpis je velmi blízký diskrétní Fourierově transformaci značené . Díky tomu lze na KFT, která působí na bázi, nahlížet jako na DFT působící na koeficienty rozvoje stavového vektoru do báze . Lze tak psát ,Višňák, str. 87 kde je vektor definován jako . Při práci s registrem qbitů je obvyklé, že Hilbertův prostor, ve kterém vlnové funkce žijí, nabývá tvaru , kde je počet zúčastněných qbitů (obvykle se tak pracuje s ).
Vlastnosti KFT je unitární, díky čemuž zachovává skalární součin, a zároveň platí .
Zároveň se KFT nedá reprezentovat jako direktní součin operátorů, které jednotlivě působí na menší počet qbitů. Nelze tak uvažovat o akci na několika skupinách qbitů nezávisle na sobě. Nicméně při akci KFT na bázový stav je výsledkem vždy stav produktový, protože výsledné stavy jednotlivých qbitů mezi sebou nejsou provázané. Produktový tvar KFT zní . Tento tvar odpovídá direktnímu součinu jednotlivých qbitů stejně jako při plném rozepsání bázového vektoru do produktového tvaru. , kde jsou číslice binárního rozvoje čísla .
Výpočetní náročnost Pokud je uvažován registr složený celkem z qbitů, má příslušná báze v Hilbertově prostoru celkem bázových vektorů. Když je KFT provedena na hodnotách, pro její provedení je třeba spočíst operací (viz níže), což odpovídá kvadratické asymptotické složitosti v počtu qbitů . Na klasické rychlé Fourierově transformaci by však tato úloha byla proveditelná s rychlostí . KFT tak poskytuje exponenciální urychlení oproti nejrychlejšímu známému klasickému algoritmu.Višňák, str. 91
Konstrukce obvodu Pro přímočarou konstrukci obvodu je výchozím bodem KFT napsaná v produktovém tvaru (jako výše). Když se postupně zapůsobí na první qbit Hadamardovým hradlem a následně se aplikují kontrolované rotace, které zajistí posun mezi fázemi stavů a , je již tento qbit převeden do požadovaného tvaru.
Operace kontrolované rotace se značí a její maticové vyjádření v prostoru pro jeden qbit je zde , Aby se docílilo požadované hodnoty fáze mezi prvním a ostatními qbity, je třeba provést celkem n-1 kontrolovaných rotací. takový způsob konstrukce obvodu vede k rekurzivnímu vztahu, kde se navlas stejný postup aplikuje na zbylých n-1 qbitů (spodní obrázek). Pro celkový počet n qbitů tak zatím vychází celkový počet hradel na . Výsledné fáze v qbitech jsou ale v opačném pořadí, než v jakém jsou požadovány. Jako poslední krok je tak aplikace SWAP hradel, která prohodí "horní" a "dolní" qbity mezi sebou. Celkem je třeba použít nanejvýš SWAPů, čímž celkový počet operací stoupá na .
Aplikace SWAP hradel je však často přeskakována a (stejně jako na obou obrázcích výše) vykresluje se jen "výpočetní část" obvodu. Ať s prohazováním pořadí qbitů nebo bez něj, celkový počet operací je proto asymptoticky .
Odkazy
Poznámky
Reference
Literatura
Související články Shorův algoritmus Deutschův–Jozsův algoritmus Rychlá Fourierova transformace
Kategorie:Kvantové algoritmy