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ý Circuit 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 Circuit

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ý Circuit, který popisuje Deutschův algoritmus:

Analýza

Pro analýzu Deutschova algoritmu projdeme působení výše uvedeného Circuit 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ě Circuit 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 Qubit 1 vytažené před závorku), ale díky tomu budou naše pozdější výrazy kompaktnější.

Dále se provede Gate $U_f.$ Podle definice Gate $U_f$ se hodnota funkce $f$ pro klasický stav horního/pravého Qubit 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.$ Explicitněji, oba případy vypadají následovně. Konkrétněji, tyto dva 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í Gate $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í Gate $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í Hadamardovy Gate 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ý Circuit, který implementuje query Gate 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 query Gate není ve skutečnosti součástí samotného Deutschova algoritmu; zde v podstatě ukazujeme jeden způsob, jak připravit vstup ve formě implementace query Gate jako Circuit.

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ý Circuit vypadá. Tady je Circuit pro funkci $f_3.$

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

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

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 Circuit vypadá, pomocí metody draw.

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

Nakonec vytvoříme funkci, která spustí dříve definovaný Circuit 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'