Algoritmus kvantového počítání - Quantum counting algorithm
Algoritmus kvantového počítání je kvantový algoritmus pro efektivní počítání počtu řešení pro daný vyhledávací problém. Algoritmus je založen na algoritmus odhadu kvantové fáze a dál Groverův vyhledávací algoritmus.
Problémy s počítáním jsou běžné v různých oblastech, jako jsou statistické odhady, statistická fyzika, vytváření sítí atd kvantové výpočty, je potřeba efektivně provádět kvantové počítání, aby bylo možné použít Groverův vyhledávací algoritmus (protože spuštění Groverova vyhledávacího algoritmu vyžaduje vědět, kolik řešení existuje). Tento algoritmus navíc řeší problém kvantové existence (jmenovitě rozhodování, zda žádný řešení) jako zvláštní případ.
Algoritmus vymyslel Gilles Brassard, Peter Høyer a Alain Tapp v roce 1998.
Problém
Zvažte konečnou množinu velikosti a sada "řešení" (to je podmnožina ). Definovat:
Jinými slovy, je funkce indikátoru z .
Vypočítejte počet řešení .[1]
Klasické řešení
Bez jakýchkoli předchozích znalostí o souboru řešení (nebo struktura funkce ), klasické deterministické řešení nemůže fungovat lépe než , protože všechny prvky musí být zkontrolováno (zvažte případ, kdy posledním prvkem, který se má zkontrolovat, je řešení).
Algoritmus

Založit
Vstup se skládá ze dvou registry (jmenovitě dvě části): horní qubits zahrnují první registracea nižší qubits jsou druhý registr.
Vytvořte superpozici
Počáteční stav systému je . Po použití více bitů Provoz brány Hadamard u každého z registrů samostatně stav první registrace je
a stav druhý registr je
rovný superpozice stav ve výpočetní bázi.
Operátor Grover
Protože velikost prostoru je a počet řešení je , můžeme definovat normalizované stavy:[2]:252
Všimněte si, že
což je stav druhý registr po Hadamardově transformaci.
Geometrická vizualizace Groverova algoritmu ukazuje, že v dvourozměrném prostoru překlenutém o a , operátor Grover je a otáčení proti směru hodinových ručiček; lze jej tedy vyjádřit jako
v ortonormální základ .[2]:252[3]:149
Z vlastnosti rotačních matic víme, že je unitární matice s těmi dvěma vlastní čísla .[2]:253
Odhad hodnoty
Od této chvíle následujeme algoritmus odhadu kvantové fáze schéma: použijeme kontrolovaný Grover operace následované inverzí kvantová Fourierova transformace; a podle analýza, najdeme to nejlepší -bitová aproximace k reálné číslo (patřící k vlastním číslům Groverova operátora) s pravděpodobností vyšší než .[4]:348[3]:157
Všimněte si, že druhý registr je ve skutečnosti v a superpozice z vlastní vektory Groverova operátoru (zatímco v původním algoritmu odhadu kvantové fáze je druhý registr požadovaným vlastním vektorem). To znamená, že s určitou pravděpodobností se přibližujeme as určitou pravděpodobností se přibližujeme ; tyto dvě aproximace jsou ekvivalentní.[2]:224–225
Analýza
Za předpokladu, že velikost prostoru je alespoň dvojnásobný počet řešení (konkrétně za předpokladu, že ), výsledkem analýzy Groverova algoritmu je:[2]:254
Pokud tedy najdeme , můžeme také najít hodnotu (protože je známo).
Chyba
je určena chybou při odhadu hodnoty . Algoritmus odhadu kvantové fáze shledává s vysokou pravděpodobností nejlepší -bitová aproximace ; to znamená, že pokud je dostatečně velký, budeme mít , proto .[2]:263
Použití
Groverův vyhledávací algoritmus pro původně neznámý počet řešení
V Groverově vyhledávacím algoritmu je počet iterací, které je třeba provést .[2]:254 [3]:150
Pokud tedy je známo a se počítá algoritmem kvantového počítání, lze snadno vypočítat počet iterací pro Groverův algoritmus.
Urychlení NP-úplných problémů
Algoritmus kvantového počítání lze použít k urychlení řešení problémů, které jsou NP-kompletní.
Příkladem NP-úplného problému je Hamiltoniánský cyklus, což je problém určení, zda a graf má Hamiltonovský cyklus.
Jednoduchým řešením problému Hamiltonovského cyklu je kontrola pro každé uspořádání vrcholů , ať už jde o hamiltonovský cyklus nebo ne. Prohledávání všech možných uspořádání vrcholů grafu lze provést kvantovým počítáním následovaným Groverovým algoritmem, čímž se dosáhne zrychlení druhé odmocniny, podobně jako Groverův algoritmus.[2]:264 Tento přístup najde Hamiltonovský cyklus (pokud existuje); pro určení, zda existuje Hamiltonovský cyklus, je dostatečný samotný algoritmus kvantového počítání (a postačuje i algoritmus kvantové existence, popsaný níže).
Problém kvantové existence
Problém kvantové existence je speciální případ kvantového počítání, kde nechceme vypočítat jeho hodnotu , ale my bychom jen chtěli vědět, zda Triviální řešení tohoto problému je přímo pomocí algoritmu kvantového počítání: algoritmus se získá , takže kontrolou, zda dostaneme odpověď na existenční problém. Tento přístup zahrnuje některé režijní informace, protože nás nezajímá hodnota .
Použití nastavení s malým počtem qubitů v horním registru nepřinese přesný odhad hodnoty , ale bude stačit k určení, zda se rovná nule nebo ne.[2]:263
Viz také
Reference
- ^ Brassard, Gilles; Hoyer, Peter; Tapp, Alain (13. – 17. Července 1998). Automaty, jazyky a programování (25. mezinárodní kolokvium ed.). ICALP'98 Aalborg, Dánsko: Springer Berlin Heidelberg. 820–831. arXiv:quant-ph / 9805082. doi:10.1007 / BFb0055105. ISBN 978-3-540-64781-2.CS1 maint: umístění (odkaz)
- ^ A b C d E F G h i Chuang, Michael A. Nielsen a Isaac L. (2001). Kvantové výpočty a kvantové informace (Repr. Ed.). Cambridge [u.a.]: Cambridge Univ. Lis. ISBN 978-0521635035.
- ^ A b C Benenti, Guiliano; Strini, Giulio Casati, Giuliano (2004). Principy kvantového výpočtu a informací (Přetištěno, ed.). New Jersey [USA]: World Scientific. ISBN 978-9812388582.
- ^ Cleve, R .; Ekert, A .; Macchiavello, C .; Mosca, M. (8. ledna 1998). "Kvantové algoritmy znovu navštíveny". Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 454 (1969). arXiv:quant-ph / 9708016. Bibcode:1998RSPSA.454..339C. doi:10.1098 / rspa.1998.0164.