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 obvodu, lze provést i kvantovým obvodem 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 obvodů pomocí kvantových obvodů

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

Toffoliho hradlo

Toffoliho hradlo lze alternativně popsat jako controlled-controlled-NOT hradlo, jehož 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 qubity seřazeny podle rostoucí významnosti shora dolů. Maticová reprezentace tohoto hradla 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 hradlu, je ten, že je v podstatě dotazovacím hradlem pro funkci AND, v tom smyslu, že se řídí vzorem, který jsme viděli v předchozí lekci pro unitární implementace dotazovacích hradel libovolných funkcí s binárními řetězcovými vstupy a výstupy.

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

Simulace booleovských hradel pomocí Toffoliho, controlled-NOT a NOT hradel

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

Ve všech třech případech qubity, na které hradla AND, OR a FANOUT 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í qubity se objevují uvnitř rámečků reprezentujících implementace hradel, aby naznačily, že jsou nové, a tedy součástí nákladů těchto implementací.

U hradel AND a OR nám také zbudou dva qubity navíc, kromě výstupního qubitu. Například uvnitř rámečku v diagramu reprezentujícím simulaci hradla AND zůstávají horní dva qubity ve stavech $\vert a\rangle$ a $\vert b\rangle.$ Tyto qubity 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é hradlo, NOT, je zahrnuto v naší výchozí sadě kvantových hradel, takže pro něj nepotřebujeme simulaci.

Simulace booleovských obvodů hradlo po hradlu

Nyní předpokládejme, že máme obyčejný booleovský obvod nazvaný $C,$ složený z hradel AND, OR, NOT a FANOUT, s $n$ vstupními bity a $m$ výstupními bity. Nechť $t = \operatorname{size}(C)$ je počet hradel 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 jedno po druhém hradla AND, OR a FANOUT z $C$ a každé nahradíme odpovídající simulací popsanou výše, včetně přidání potřebných pracovních qubitů. Výsledný obvod nazvěme $R$ a seřaďme qubity v $R$ tak, aby $n$ vstupních bitů $C$ odpovídalo horním $n$ qubitům $R$ a pracovní qubity byly dole.

Zde $k$ je počet potřebných pracovních qubitů — jeden pro každé hradlo AND, OR a FANOUT 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 hradel po proběhnutí $R.$ Na obrázku jsou qubity odpovídající výstupu $f(x)$ nahoře a zbývající qubity uchovávající $g(x)$ dole. Můžeme to vynutit, pokud chceme, přeuspořádáním qubitů pomocí hradel SWAP, která lze implementovat třemi hradly controlled-NOT 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 obvodem $C,$ ale ve skutečnosti se o ni nemusíme příliš starat; nezajímá nás konkrétně, v jakém stavu tyto qubity 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 obvodem $C$ pomocí kvantového obvodu, nemusíme pokračovat dále než k právě popsané simulaci hradlo po hradlu. 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í qubity způsobí problémy. Fenomén interference je pro kvantové algoritmy kriticky důležitý a odpadní qubity 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ý obvod, můžeme ho spustit pozpátku — jednoduše nahradíme každé hradlo jeho inverzí a aplikujeme je v obráceném pořadí, čímž získáme kvantový obvod pro operaci $R^{\dagger}.$ Toffoliho hradlo, CNOT a NOT jsou ve skutečnosti vlastními inverzemi, takže spuštění $R$ pozpátku je opravdu jen otázka aplikace hradel v obráceném pořadí — ale obecněji lze jakýkoli kvantový obvod 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í hradel CNOT zkopírovat výstup $R$ na tyto qubity a obrátit $R$ pro úklid odpadu. Následující obrázek ilustruje výsledný obvod a popisuje jeho působení na stavy standardní báze.

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

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

Pokud nebereme v úvahu $k$ dodatečných pracovních qubitů, máme obvod $Q$, který funguje přesně jako dotazovací hradlo 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$ qubitech — 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ý obvod, který počítá vstupní funkci, můžeme každé dotazovací hradlo nahradit jeho implementací obvodem a dotazovací algoritmus bude fungovat správně.

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

Implementace invertibilních funkcí

Právě popsaná konstrukce nám umožňuje simulovat jakýkoli booleovský obvod kvantovým obvodem bez odpadu. Pokud $C$ je booleovský obvod implementující funkci $f:\Sigma^n \rightarrow \Sigma^m,$ pak získáme kvantový obvod $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ý obvod 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í qubity, $U$ se liší od operace, kterou implementuje obvod $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í qubity a kromě booleovského obvodu, 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 obvodů, $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$ hradly swap, přičemž $k$ je maximum z počtů pracovních qubitů požadovaných $Q_f$ a $Q_{f^{-1}}.$