Deutschův algoritmus

Deutschův algoritmus řeší problém parity pro speciální případ, kdy $n = 1.$ V kontextu kvantového počítání se tento problém někdy označuje jako Deutschův problém a v této lekci se budeme držet tohoto pojmenování.

Přesněji řečeno, vstup je reprezentován funkcí $f:\Sigma \rightarrow \Sigma$ z jednoho bitu na jeden bit. Takové funkce existují čtyři:

$$\rule[-10mm]{0mm}{10mm} \begin{array}{c|c} a & f_1(a)\\ \hline 0 & 0\\ 1 & 0 \end{array} \qquad \begin{array}{c|c} a & f_2(a)\\ \hline 0 & 0\\ 1 & 1 \end{array} \qquad \begin{array}{c|c} a & f_3(a)\\ \hline 0 & 1\\ 1 & 0 \end{array} \qquad \begin{array}{c|c} a & f_4(a)\\ \hline 0 & 1\\ 1 & 1 \end{array}$$

První a poslední z těchto funkcí jsou konstantní a prostřední dvě jsou vyvážené (balanced), což znamená, že obě možné výstupní hodnoty funkce se vyskytují stejně často, když procházíme všechny vstupy. Deutschův problém spočívá v určení, do které z těchto dvou kategorií vstupní funkce patří: konstantní nebo vyvážená.

Deutschův problém

Vstup: funkce $f:\{0,1\}\rightarrow\{0,1\}$
Výstup: $0$ pokud je $f$ konstantní, $1$ pokud je $f$ vyvážená

Pokud se na vstupní funkci $f$ v Deutschově problému díváš jako na reprezentaci náhodného přístupu k řetězci, mluvíme o dvoubitovém řetězci: $f(0)f(1).$

$$\begin{array}{cc} \mathsf{function} & \mathsf{string}\\ \hline f_1 & 00 \\ f_2 & 01 \\ f_3 & 10 \\ f_4 & 11 \end{array}$$

Při tomto pohledu Deutschův problém spočívá ve výpočtu parity (nebo ekvivalentně exkluzivního OR) těchto dvou bitů.

Každý klasický dotazovací algoritmus, který správně řeší tento problém, se musí dotázat na oba bity: $f(0)$ a $f(1).$ Pokud se například dozvíme, že $f(1) = 1,$ odpověď může být stále $0$ nebo $1,$ v závislosti na tom, zda $f(0) = 1$ nebo $f(0) = 0.$ Každý další případ je obdobný; znalost pouze jednoho ze dvou bitů neposkytuje vůbec žádnou informaci o jejich paritě. Booleovský obvod popsaný v předchozí části je tedy to nejlepší, čeho můžeme dosáhnout z hlediska počtu dotazů potřebných k vyřešení tohoto problému.

Popis kvantového obvodu

Deutschův algoritmus řeší Deutschův problém pomocí jediného dotazu, a poskytuje tak kvantifikovatelnou výhodu kvantového výpočtu oproti klasickému. Může to být skromná výhoda — jeden dotaz oproti dvěma — ale někde začít musíme. Vědecký pokrok má někdy zdánlivě skromné počátky.

Zde je kvantový obvod, který popisuje Deutschův algoritmus:

Analýza

Pro analýzu Deutschova algoritmu projdeme působení výše uvedeného obvodu a identifikujeme stavy qubitů v časech naznačených tímto obrázkem:

Počáteční stav je $\vert 1\rangle \vert 0 \rangle$ a dvě Hadamardovy operace na levé straně obvodu transformují tento stav na

$$\vert \pi_1 \rangle = \vert - \rangle \vert + \rangle = \frac{1}{2} \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \vert 0\rangle + \frac{1}{2} \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \vert 1\rangle.$$

(Jak vždy, dodržujeme konvenci řazení qubitů v Qiskitu, která umísťuje horní qubit doprava a dolní qubit doleva.) Může se zdát neintuitivní zapsat tento produktový stav částečně rozepsaný (ponechat stavy qubitu 1 vytažené před závorku), ale díky tomu budou naše pozdější výrazy kompaktnější.

Dále se provede hradlo $U_f.$ Podle definice hradla $U_f$ se hodnota funkce $f$ pro klasický stav horního/pravého qubitu XORuje na dolní/levý qubit, čímž se $\vert \pi_1\rangle$ transformuje do stavu

$$\vert \pi_2 \rangle = \frac{1}{2} \bigl( \vert 0 \oplus f(0) \rangle - \vert 1 \oplus f(0) \rangle \bigr) \vert 0 \rangle + \frac{1}{2} \bigl( \vert 0 \oplus f(1) \rangle - \vert 1 \oplus f(1) \rangle \bigr) \vert 1 \rangle.$$

Tento výraz můžeme zjednodušit pozorováním, že vzorec

$$\vert 0 \oplus a\rangle - \vert 1 \oplus a\rangle = (-1)^a \bigl( \vert 0\rangle - \vert 1\rangle \bigr)$$

funguje pro obě možné hodnoty $a\in\Sigma.$ Konkrétněji, oba případy vypadají následovně.

$$\begin{aligned} \vert 0 \oplus 0\rangle - \vert 1 \oplus 0\rangle & = \vert 0 \rangle - \vert 1 \rangle = (-1)^0 \bigl( \vert 0\rangle - \vert 1\rangle \bigr)\\ \vert 0 \oplus 1\rangle - \vert 1 \oplus 1\rangle & = \vert 1 \rangle - \vert 0\rangle = (-1)^1 \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \end{aligned}$$

Takže můžeme alternativně vyjádřit $\vert\pi_2\rangle$ takto:

$$\begin{aligned} \vert\pi_2\rangle & = \frac{1}{2} (-1)^{f(0)} \bigl( \vert 0 \rangle - \vert 1 \rangle \bigr) \vert 0 \rangle + \frac{1}{2} (-1)^{f(1)} \bigl( \vert 0 \rangle - \vert 1 \rangle \bigr) \vert 1 \rangle \\ & = \vert - \rangle \biggl( \frac{(-1)^{f(0)} \vert 0\rangle + (-1)^{f(1)} \vert 1\rangle}{\sqrt{2}}\biggr). \end{aligned}$$

Právě se stalo něco zajímavého! Ačkoli působení hradla $U_f$ na standardní bázové stavy ponechává horní/nejpravější qubit beze změny a XORuje hodnotu funkce na spodní/nejlevější qubit, zde vidíme, že se stav horního/nejpravějšího qubitu (obecně) změnil, zatímco stav spodního/nejlevějšího qubitu zůstal stejný — konkrétně ve stavu $\vert - \rangle$ před i po provedení hradla $U_f$. Tento jev je známý jako phase kickback (fázový zpětný ráz) a za chvíli si o něm řekneme víc.

S jedním posledním zjednodušením, kterým je vytažení faktoru $(-1)^{f(0)}$ před součet, získáme tento výraz stavu $\vert\pi_2\rangle$:

$$\begin{aligned} \vert\pi_2\rangle & = (-1)^{f(0)} \vert - \rangle \biggl( \frac{\vert 0\rangle + (-1)^{f(0) \oplus f(1)} \vert 1\rangle}{\sqrt{2}}\biggr) \\ & = \begin{cases} (-1)^{f(0)} \vert - \rangle \vert + \rangle & \text{if $f(0) \oplus f(1) = 0$}\\[1mm] (-1)^{f(0)} \vert - \rangle \vert - \rangle & \text{if $f(0) \oplus f(1) = 1$}. \end{cases} \end{aligned}$$

Všimni si, že v tomto výrazu máme $f(0) \oplus f(1)$ v exponentu $-1$ místo $f(1) - f(0),$ což bychom mohli očekávat z čistě algebraického hlediska, ale výsledek je v obou případech stejný. Je to proto, že hodnota $(-1)^k$ pro libovolné celé číslo $k$ závisí pouze na tom, zda je $k$ sudé nebo liché.

Aplikací posledního Hadamardova hradla na horní qubit získáme stav

$$\vert \pi_3 \rangle = \begin{cases} (-1)^{f(0)} \vert - \rangle \vert 0 \rangle & \text{if $f(0) \oplus f(1) = 0$}\\[1mm] (-1)^{f(0)} \vert - \rangle \vert 1 \rangle & \text{if $f(0) \oplus f(1) = 1$}, \end{cases}$$

což vede ke správnému výsledku s pravděpodobností $1$ při měření pravého/horního qubitu.

Další poznámky k phase kickbacku

Než budeme pokračovat, podívejme se na výše uvedenou analýzu z mírně odlišného úhlu, který může osvětlit jev phase kickbacku.

Nejprve si všimni, že následující vzorec platí pro všechny volby bitů $b,c\in\Sigma.$

$$\vert b \oplus c\rangle = X^c \vert b \rangle$$

To lze ověřit kontrolou pro dvě možné hodnoty $c = 0$ a $c = 1$:

$$\begin{aligned} \vert b \oplus 0 \rangle & = \vert b\rangle = \mathbb{I} \vert b \rangle = X^0 \vert b \rangle\\ \vert b \oplus 1 \rangle & = \vert \neg b\rangle = X \vert b \rangle = X^1 \vert b \rangle. \end{aligned}$$

Pomocí tohoto vzorce vidíme, že

$$U_f \bigl(\vert b\rangle \vert a \rangle\bigr) = \vert b \oplus f(a) \rangle \vert a \rangle = \bigl(X^{f(a)}\vert b \rangle\bigr) \vert a \rangle$$

pro každou volbu bitů $a,b\in\Sigma.$ Protože tento vzorec platí pro $b=0$ a $b=1,$ z linearity vyplývá, že

$$U_f \bigl( \vert \psi \rangle \vert a \rangle \bigr) = \bigl(X^{f(a)}\vert \psi \rangle\bigr) \vert a \rangle$$

pro všechny stavové vektory qubitu $\vert \psi\rangle,$ a proto

$$U_f \bigl( \vert - \rangle \vert a \rangle \bigr) = \bigl(X^{f(a)} \vert - \rangle \bigr) \vert a \rangle = (-1)^{f(a)} \vert - \rangle \vert a \rangle.$$

Klíčem, díky kterému to funguje, je to, že $X\vert - \rangle = - \vert - \rangle.$ V matematické terminologii je vektor $\vert - \rangle$ vlastním vektorem matice $X$ s vlastním číslem $-1.$

Vlastní vektory a vlastní čísla probereme podrobněji v nadcházející lekci o odhadu fáze a faktorizaci, kde je jev phase kickbacku zobecněn na další unitární operace.

S vědomím, že skaláry volně procházejí tenzorovými součiny, najdeme alternativní způsob uvažování o tom, jak operace $U_f$ transformuje $\vert \pi_1\rangle$ na $\vert \pi_2\rangle$ ve výše uvedené analýze:

$$\begin{aligned} \vert \pi_2 \rangle & = U_f \bigl( \vert - \rangle \vert + \rangle \bigr)\\ & = \frac{1}{\sqrt{2}} U_f \bigl(\vert - \rangle \vert 0\rangle \bigr) + \frac{1}{\sqrt{2}} U_f \bigl(\vert - \rangle \vert 1\rangle \bigr)\\ & = \vert - \rangle \biggl( \frac{(-1)^{f(0)} \vert 0\rangle + (-1)^{f(1)} \vert 1\rangle}{\sqrt{2}}\biggr). \end{aligned}$$

Implementace v Qiskit

Teď se podíváme, jak můžeš implementovat Deutschův algoritmus v Qiskit. Začneme kontrolou verze a poté provedeme importy potřebné výhradně pro tuto implementaci. Pro implementace dalších algoritmů, které následují, provedeme potřebné importy zvlášť kvůli větší modularitě.

# Added by doQumentation — required packages for this notebook
!pip install -q qiskit qiskit-aer

from qiskit import __version__

print(__version__)

2.1.1

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

Nejprve definujeme kvantový obvod, který implementuje dotazovací hradlo pro jednu ze čtyř funkcí $f_1,$ $f_2,$ $f_3,$ nebo $f_4$ z jednoho bitu do jednoho bitu, popsaných dříve. Jak jsme již zmínili, implementace dotazovacího hradla není ve skutečnosti součástí samotného Deutschova algoritmu; zde v podstatě ukazujeme jeden způsob, jak připravit vstup ve formě implementace dotazovacího hradla jako obvod.

def deutsch_function(case: int):
    # This function generates a quantum circuit for one of the 4 functions
    # from one bit to one bit

    if case not in [1, 2, 3, 4]:
        raise ValueError("`case` must be 1, 2, 3, or 4.")

    f = QuantumCircuit(2)
    if case in [2, 3]:
        f.cx(0, 1)
    if case in [3, 4]:
        f.x(1)
    return f

Pomocí metody draw si můžeš prohlédnout, jak každý obvod vypadá. Tady je obvod pro funkci $f_3.$

display(deutsch_function(3).draw(output="mpl"))

Dále vytvoříme samotný kvantový obvod pro Deutschův algoritmus, přičemž dotazovací hradlo nahradíme implementací kvantového obvodu zadanou jako argument. Za chvíli do něj zapojíme jeden ze čtyř obvodů definovaných funkcí deutsch_function, kterou jsme definovali dříve. Bariéry jsou zahrnuty pro vizuální oddělení implementace dotazovacího hradla od zbytku obvodu.

def compile_circuit(function: QuantumCircuit):
    # Compiles a circuit for use in Deutsch's algorithm.

    n = function.num_qubits - 1
    qc = QuantumCircuit(n + 1, n)

    qc.x(n)
    qc.h(range(n + 1))

    qc.barrier()
    qc.compose(function, inplace=True)
    qc.barrier()

    qc.h(range(n))
    qc.measure(range(n), range(n))

    return qc

Opět si můžeš prohlédnout, jak obvod vypadá, pomocí metody draw.

display(compile_circuit(deutsch_function(3)).draw(output="mpl"))

Nakonec vytvoříme funkci, která spustí dříve definovaný obvod jednou a vypíše odpovídající výsledek: „constant" nebo „balanced".

def deutsch_algorithm(function: QuantumCircuit):
    # Determine if a one-bit function is constant or balanced.

    qc = compile_circuit(function)

    result = AerSimulator().run(qc, shots=1, memory=True).result()
    measurements = result.get_memory()
    if measurements[0] == "0":
        return "constant"
    return "balanced"

Teď můžeš spustit Deutschův algoritmus na kteroukoli ze čtyř výše definovaných funkcí.

f = deutsch_function(3)
display(deutsch_algorithm(f))

'balanced'