Klasické výpočty na kvantových počítačích

Nyní obrátíme pozornost k implementaci klasických algoritmů na kvantových počítačích. Uvidíš, že jakýkoli výpočet, který lze provést pomocí klasického Booleovského Circuit, lze provést i kvantovým Circuit s podobnou asymptotickou výpočetní náročností. Navíc to lze udělat „čistým" způsobem, který bude popsán za chvíli, což je důležitý požadavek pro použití těchto výpočtů jako podprogramů uvnitř větších kvantových výpočtů.

Simulace Booleovských Circuit pomocí kvantových Circuit

Booleovské Circuit se skládají z AND, OR, NOT a FANOUT Gate. Abychom mohli simulovat Booleovské Circuit kvantovými Circuit, začneme tím, že ukážeme, jak lze každou z těchto čtyř Gate simulovat kvantovými Gate. Jakmile to bude hotové, převod daného Booleovského Circuit na kvantový Circuit je jednoduchá záležitost simulace jedné Gate po druhé. Budeme potřebovat pouze NOT Gate, controlled-NOT Gate a Toffoliho Gate, které jsou kromě toho, že jsou unitární, také deterministické operace.

Toffoliho Gate

Toffoliho Gate lze alternativně popsat jako controlled-controlled-NOT Gate, jejichž působení na stavy standardní báze je znázorněno na následujícím obrázku.

Mějme na paměti, že používáme konvenci řazení Qiskit, kde jsou Qubit seřazeny podle rostoucí významnosti shora dolů. Maticová reprezentace této Gate je následující.

$$\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{pmatrix}$$

Další způsob, jak přemýšlet o Toffoliho Gate, je ten, že jsou v podstatě dotazovací Gate pro funkci AND, v tom smyslu, že následují vzor, který jsme viděli v předchozí lekci pro unitární implementace dotazovacích Gate libovolných funkcí s binárními řetězcovými vstupy a výstupy.

Toffoliho Gate nejsou součástí výchozí sady Gate diskutované dříve v této lekci, ale je možné sestavit Toffoliho Gate z $H,$ $T,$ $T^{\dagger},$ a CNOT Gate následovně.

Simulace Booleovských Gate pomocí Toffoliho, controlled-NOT a NOT Gate

Jediná Toffoliho Gate v kombinaci s několika NOT Gate může implementovat AND a OR Gate, a FANOUT Gate lze snadno implementovat pomocí controlled-NOT Gate, jak naznačují následující diagramy.

Ve všech třech případech Qubit, na které AND, OR a FANOUT Gate působí, přicházejí zleva jako vstupy, a pro každý z nich také potřebujeme jeden pracovní Qubit inicializovaný do nulového stavu. Tyto pracovní Qubit se objevují uvnitř rámečků reprezentujících implementace Gate, aby naznačily, že jsou nové, a tedy součástí nákladů těchto implementací.

U AND a OR Gate nám také zbudou dva Qubit navíc, kromě výstupního Qubit. Například uvnitř rámečku v diagramu reprezentujícím simulaci AND Gate zůstávají horní dva Qubit ve stavech $\vert a\rangle$ a $\vert b\rangle.$ Tyto Qubit jsou znázorněny jako zůstávající uvnitř rámečků, protože již nejsou potřeba a nejsou součástí výstupu. Prozatím je můžeš ignorovat, i když se k nim brzy vrátíme.

Zbývající Booleovská Gate, NOT Gate, je zahrnuta v naší výchozí sadě kvantových Gate, takže pro ni nepotřebujeme simulaci.

Simulace Booleovských Circuit Gate po Gate

Nyní předpokládejme, že máme obyčejný Booleovský Circuit nazvaný $C,$ složený z AND, OR, NOT a FANOUT Gate, s $n$ vstupními bity a $m$ výstupními bity. Nechť $t = \operatorname{size}(C)$ je počet Gate v $C,$ a funkci, kterou $C$ počítá, nazvěme $f$. Tato funkce má tvar

$$f:\Sigma^n\rightarrow\Sigma^m$$

pro $\Sigma = \{0,1\}.$

Nyní se podívej, co se stane, když projdeme jednu po druhé AND, OR a FANOUT Gate z $C$ a každou nahradíme odpovídající simulací popsanou výše, včetně přidání potřebných pracovních Qubit. Výsledný Circuit nazvěme $R$ a seřaďme Qubit v $R$ tak, aby $n$ vstupních bitů $C$ odpovídalo horním $n$ Qubit $R$ a pracovní Qubit byly dole.

Zde $k$ je počet potřebných pracovních Qubit — jeden pro každou AND, OR a FANOUT Gate z $C$ — a $g$ je funkce tvaru $g:\Sigma^n \rightarrow \Sigma^{n+k-m}$, která popisuje stavy zbylých Qubit vytvořených simulacemi Gate po proběhnutí $R.$ Na obrázku jsou Qubit odpovídající výstupu $f(x)$ nahoře a zbývající zbylé Qubit uchovávající $g(x)$ dole. Můžeme to vynutit, pokud chceme, přeuspořádáním Qubit pomocí SWAP Gate, které lze implementovat třemi controlled-NOT Gate takto:

Jak uvidíme v další sekci, přeuspořádání výstupních Qubit tímto způsobem není skutečně nezbytné, ale je dostatečně snadné to udělat, pokud se rozhodneme.

Funkce $g$, která popisuje klasické stavy zbylých Qubit, je určena Circuit $C,$ ale ve skutečnosti se o ni nemusíme příliš starat; nezajímá nás konkrétně, v jakém stavu tyto Qubit budou po dokončení výpočtu. Písmeno $g$ následuje po $f,$ takže je to rozumné jméno pro tuto funkci z tohoto důvodu, ale existuje lepší důvod pro volbu názvu $g$ — je to zkratka pro garbage (odpad).

Úklid odpadu

Pokud je naším jediným zájmem vyhodnocení funkce $f$ počítané daným Booleovským Circuit $C$ pomocí kvantového Circuit, nemusíme pokračovat dále než k právě popsané simulaci Gate po Gate. To znamená, že kromě výstupu funkce nám zbude spousta odpadu.

Nicméně to nestačí, pokud chceme provádět klasické výpočty jako podprogramy uvnitř větších kvantových výpočtů, protože tyto odpadní Qubit způsobí problémy. Fenomén interference je pro kvantové algoritmy kriticky důležitý a odpadní Qubit mohou zničit interferenční vzory potřebné k fungování kvantových algoritmů.

Naštěstí není obtížné odpad uklidit, dá se říci. Klíčem je využít skutečnost, že protože $R$ je kvantový Circuit, můžeme ho spustit pozpátku — jednoduše nahradíme každou Gate její inverzí a aplikujeme je v obráceném pořadí, čímž získáme kvantový Circuit pro operaci $R^{\dagger}.$ Toffoliho Gate, CNOT Gate a NOT Gate jsou ve skutečnosti vlastními inverzemi, takže spuštění $R$ pozpátku je opravdu jen otázka aplikace Gate v obráceném pořadí — ale obecněji lze jakýkoli kvantový Circuit obrátit právě popsaným způsobem.

Konkrétně můžeme přidat $m$ dalších Qubit (připomeňme, že funkce $f$ má $m$ výstupních bitů), pomocí CNOT Gate zkopírovat výstup $R$ na tyto Qubit a obrátit $R$ pro úklid odpadu. Následující obrázek ilustruje výsledný Circuit a popisuje jeho působení na stavy standardní báze.

Pokud celý Circuit obalíme rámečkem a nazveme ho $Q,$ vypadá takto:

Vzhledem k tomu, že $C$ má $t$ Gate, Circuit $Q$ bude mít $O(t)$ Gate.

Pokud nebereme v úvahu $k$ dodatečných pracovních Qubit, máme Circuit $Q$, který funguje přesně jako dotazovací Gate pro funkci $f.$ Pokud chceme jednoduše spočítat funkci $f$ pro nějaký řetězec $x,$ můžeme nastavit $y = 0^m$ a výsledná hodnota $f(x)$ se objeví na spodních $m$ Qubit — nebo můžeme do spodních $m$ Qubit přivést jiný stav, pokud chceme (třeba pro využití fázového zpětného rázu, jako v Deutschově nebo Deutsch-Jozsově algoritmu).

To znamená, že pro jakýkoli dotazovací algoritmus, pokud máme Booleovský Circuit, který počítá vstupní funkci, můžeme každou dotazovací Gate nahradit její Circuit implementací a dotazovací algoritmus bude fungovat správně.

Všimni si, že pracovní Qubit jsou potřeba k tomu, aby tento proces fungoval, ale po provedení kombinovaného Circuit se vrátí do svých počátečních stavů. To umožňuje tyto Qubit znovu použít jako pracovní Qubit pro jiné účely. Existují také známé strategie pro snížení počtu potřebných pracovních Qubit (za cenu větších Circuit), ale tyto strategie zde nebudeme probírat.

Implementace invertibilních funkcí

Právě popsaná konstrukce nám umožňuje simulovat jakýkoli Booleovský Circuit kvantovým Circuit bez odpadu. Pokud $C$ je Booleovský Circuit implementující funkci $f:\Sigma^n \rightarrow \Sigma^m,$ pak získáme kvantový Circuit $Q$, který na stavech standardní báze funguje následovně.

$$Q \bigl( \vert y \rangle \vert 0^k \rangle \vert x\rangle\bigr) = \vert y \oplus f(x) \rangle \vert 0^k \rangle \vert x\rangle$$

Číslo $k$ udává, kolik pracovních Qubit je celkem potřeba. To stačí pro účely tohoto kurzu, ale je možné tuto metodologii posunout o krok dále, když je samotná funkce $f$ invertibilní.

Přesněji řečeno, předpokládejme, že funkce $f$ má tvar $f:\Sigma^n \rightarrow \Sigma^n,$ a také předpokládejme, že existuje funkce $f^{-1}$ taková, že $f^{-1}(f(x)) = x$ pro každé $x\in\Sigma^n$ (která je nutně jednoznačná, pokud existuje). To znamená, že operace transformující $\vert x \rangle$ na $\vert f(x) \rangle$ pro každé $x\in\Sigma^n$ je unitární, takže bychom mohli doufat, že sestavíme kvantový Circuit implementující unitární operaci definovanou jako

$$U \vert x \rangle = \vert f(x) \rangle$$

pro každé $x\in\Sigma^n.$

Aby bylo jasno, skutečnost, že jde o unitární operaci, závisí na tom, že $f$ je invertibilní — není unitární, když $f$ není invertibilní. Pokud nebereme v úvahu pracovní Qubit, $U$ se liší od operace, kterou implementuje Circuit $Q$, protože si neponecháváme kopii vstupu a neXORujeme ji s libovolným řetězcem, ale nahrazujeme $x$ hodnotou $f(x).$

Otázka zní: když je $f$ invertibilní, můžeme to udělat?

Odpověď je ano, za předpokladu, že máme povoleno používat pracovní Qubit a kromě Booleovského Circuit, který počítá $f,$ máme také takový, který počítá $f^{-1}.$ Takže to není zkratka pro výpočetní invertování funkcí, když ještě nevíme, jak to udělat! Následující diagram ilustruje, jak to lze provést složením dvou kvantových Circuit, $Q_f$ a $Q_{f^{-1}},$ které jsou jednotlivě získány pro funkce $f$ a $f^{-1}$ metodou popsanou výše, spolu s $n$ swap Gate, přičemž $k$ je maximum z počtů pracovních Qubit požadovaných $Q_f$ a $Q_{f^{-1}}.$