Deutsch-Jozsův algoritmus

Deutschův algoritmus překonává všechny klasické algoritmy pro problém dotazování, ale tato výhoda je poměrně skromná: jeden dotaz oproti dvěma. Deutsch-Jozsův algoritmus tuto výhodu rozšiřuje — a ve skutečnosti ho lze použít k řešení několika různých problémů dotazování.

Zde je popis Deutsch-Jozsova algoritmu pomocí kvantového Circuit. Další krok klasického post-processingu, který není na obrázku znázorněn, může být také potřeba v závislosti na konkrétním řešeném problému.

Samozřejmě jsme zatím neprobrali, jaké problémy tento algoritmus řeší; to je obsahem následujících dvou sekcí.

Deutsch-Jozsův problém

Začneme problémem dotazování, pro který byl Deutsch-Jozsův algoritmus původně navržen, a který je známý jako Deutsch-Jozsův problém.

Vstupní funkce tohoto problému má tvar $f:\Sigma^n \rightarrow \Sigma$ pro libovolné kladné celé číslo $n.$ Podobně jako u Deutschova problému je úkolem vypsat $0$, pokud je $f$ konstantní, a $1$, pokud je $f$ vyvážená, což opět znamená, že počet vstupních řetězců, pro které funkce nabývá hodnoty $0$, je roven počtu vstupních řetězců, pro které funkce nabývá hodnoty $1$.

Všimni si, že pokud je $n$ větší než $1,$ existují funkce tvaru $f:\Sigma^n \rightarrow \Sigma$, které nejsou ani konstantní, ani vyvážené. Například funkce $f:\Sigma^2\rightarrow\Sigma$ definovaná jako

$$\begin{aligned} f(00) & = 0 \\ f(01) & = 0 \\ f(10) & = 0 \\ f(11) & = 1 \end{aligned}$$

nespadá do žádné z těchto dvou kategorií. U Deutsch-Jozsova problému se o takové funkce jednoduše nestaráme — považují se za vstupy typu „nezáleží na nich". To znamená, že u tohoto problému máme příslib, že $f$ je buď konstantní, nebo vyvážená.

Deutsch-Jozsův problém

Vstup: funkce $f:\{0,1\}^n\rightarrow\{0,1\}$
Příslib: $f$ je buď konstantní, nebo vyvážená
Výstup: $0$ pokud je $f$ konstantní, $1$ pokud je $f$ vyvážená

Deutsch-Jozsův algoritmus se svým jediným dotazem řeší tento problém následovně: pokud jsou všechny výsledky $n$ měření rovny $0,$ pak je funkce $f$ konstantní; a jinak, pokud je alespoň jeden z výsledků měření roven $1,$ pak je funkce $f$ vyvážená. Jinak řečeno, za Circuit popsaným výše následuje krok klasického post-processingu, ve kterém se z výsledků měření vypočítá operace OR a vytvoří se výstup.

Analýza algoritmu

Pro analýzu výkonu Deutsch-Jozsova algoritmu pro Deutsch-Jozsův problém je užitečné začít úvahou o působení jedné vrstvy Hadamardových Gate. Hadamardovu operaci lze vyjádřit jako matici obvyklým způsobem,

$$H = \begin{pmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\[2mm] \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{pmatrix},$$

ale tuto operaci můžeme také vyjádřit pomocí jejího působení na stavy standardní báze:

$$\begin{aligned} H \vert 0\rangle & = \frac{1}{\sqrt{2}} \vert 0 \rangle + \frac{1}{\sqrt{2}} \vert 1 \rangle\\[3mm] H \vert 1\rangle & = \frac{1}{\sqrt{2}} \vert 0 \rangle - \frac{1}{\sqrt{2}} \vert 1 \rangle. \end{aligned}$$

Tyto dvě rovnice lze spojit do jednoho vzorce,

$$H \vert a \rangle = \frac{1}{\sqrt{2}} \vert 0 \rangle + \frac{1}{\sqrt{2}} (-1)^a \vert 1 \rangle = \frac{1}{\sqrt{2}} \sum_{b\in\{0,1\}} (-1)^{ab} \vert b\rangle,$$

který platí pro obě volby $a\in\Sigma.$

Nyní předpokládejme, že místo jednoho Qubit máme $n$ Qubitů a na každém se provede Hadamardova operace. Kombinovaná operace na $n$ Qubitech je popsána tenzorovým součinem $H\otimes \cdots \otimes H$ ($n$-krát), který pro stručnost a přehlednost zapisujeme jako $H^{\otimes n}$. Pomocí výše uvedeného vzorce, po rozepsání a následném zjednodušení, můžeme vyjádřit působení této kombinované operace na stavy standardní báze $n$ Qubitů takto:

$$\begin{aligned} & H^{\otimes n} \vert x_{n-1} \cdots x_1 x_0 \rangle \\ & \qquad = \bigl(H \vert x_{n-1} \rangle \bigr) \otimes \cdots \otimes \bigl(H \vert x_{0} \rangle \bigr) \\ & \qquad = \Biggl( \frac{1}{\sqrt{2}} \sum_{y_{n-1}\in\Sigma} (-1)^{x_{n-1} y_{n-1}} \vert y_{n-1} \rangle \Biggr) \otimes \cdots \otimes \Biggl( \frac{1}{\sqrt{2}} \sum_{y_{0}\in\Sigma} (-1)^{x_{0} y_{0}} \vert y_{0} \rangle \Biggr) \\ & \qquad = \frac{1}{\sqrt{2^n}} \sum_{y_{n-1}\cdots y_0 \in \Sigma^n} (-1)^{x_{n-1}y_{n-1} + \cdots + x_0 y_0} \vert y_{n-1} \cdots y_0 \rangle. \end{aligned}$$

Mimochodem, binární řetězce délky $n$ zde zapisujeme jako $x_{n-1}\cdots x_0$ a $y_{n-1}\cdots y_0,$ podle konvence indexování v Qiskitu.

Tento vzorec nám poskytuje užitečný nástroj pro analýzu výše uvedeného kvantového Circuit. Po provedení první vrstvy Hadamardových Gate je stav $n+1$ Qubitů (včetně nejlevějšího/spodního Qubit, který je ošetřen odděleně od ostatních)

$$\bigl( H \vert 1 \rangle \bigr) \bigl( H^{\otimes n} \vert 0 \cdots 0 \rangle \bigr) = \vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} \vert x_{n-1} \cdots x_0 \rangle.$$

Když se provede operace $U_f$, tento stav se transformuje na

$$\vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} (-1)^{f(x_{n-1}\cdots x_0)} \vert x_{n-1} \cdots x_0 \rangle$$

prostřednictvím přesně stejného jevu fázového zpětného rázu, který jsme viděli v analýze Deutschova algoritmu.

Poté se provede druhá vrstva Hadamardových Gate, která (podle výše uvedeného vzorce) transformuje tento stav na

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} \sum_{y_{n-1}\cdots y_0 \in \Sigma^n} (-1)^{f(x_{n-1}\cdots x_0) + x_{n-1}y_{n-1} + \cdots + x_0 y_0} \vert y_{n-1} \cdots y_0 \rangle.$$

Tento výraz vypadá poněkud komplikovaně a bez dalších znalostí o funkci $f$ nelze o pravděpodobnostech získání různých výsledků měření příliš mnoho usoudit.

Naštěstí vše, co potřebujeme znát, je pravděpodobnost, že každý z výsledků měření bude $0$ — protože to je pravděpodobnost, že algoritmus určí, že $f$ je konstantní. Tato pravděpodobnost má jednoduchý vzorec.

$$\Biggl\vert \frac{1}{2^n} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} (-1)^{f(x_{n-1}\cdots x_0)} \Biggr\vert^2 = \begin{cases} 1 & \text{if $f$ is constant}\\[1mm] 0 & \text{if $f$ is balanced} \end{cases}$$

Podrobněji, pokud je $f$ konstantní, pak buď $f(x_{n-1}\cdots x_0) = 0$ pro každý řetězec $x_{n-1}\cdots x_0,$ v tom případě je hodnota součtu $2^n,$ nebo $f(x_{n-1}\cdots x_0) = 1$ pro každý řetězec $x_{n-1}\cdots x_0,$ v tom případě je hodnota součtu $-2^n.$ Vydělením $2^n$ a umocněním absolutní hodnoty na druhou získáme $1.$

Pokud je naopak $f$ vyvážená, pak $f$ nabývá hodnoty $0$ na polovině řetězců $x_{n-1}\cdots x_0$ a hodnoty $1$ na druhé polovině, takže se členy $+1$ a $-1$ v součtu vzájemně vyruší a zbude nám hodnota $0.$

Docházíme k závěru, že algoritmus funguje správně za předpokladu, že je splněn příslib.

Obtížnost pro klasické algoritmy

Deutsch-Jozsův algoritmus funguje pokaždé, vždy dává správnou odpověď, když je příslib splněn, a vyžaduje jediný dotaz. Jak je to ve srovnání s klasickými dotazovacími algoritmy pro Deutsch-Jozsův problém?

Za prvé, jakýkoli deterministický klasický algoritmus, který správně řeší Deutsch-Jozsův problém, musí provést exponenciálně mnoho dotazů: v nejhorším případě je potřeba $2^{n-1} + 1$ dotazů. Důvod je ten, že pokud deterministický algoritmus dotazuje $f$ na $2^{n-1}$ nebo méně různých řetězcích a pokaždé získá stejnou hodnotu funkce, pak jsou stále možné obě odpovědi. Funkce může být konstantní, nebo může být vyvážená, ale smůlou se stalo, že dotazy všechny vrátily stejnou hodnotu funkce.

Druhá možnost se může zdát nepravděpodobná — ale u deterministických algoritmů neexistuje žádná náhodnost ani nejistota, takže systematicky selžou na určitých funkcích. Máme tedy v tomto ohledu významnou výhodu kvantových algoritmů oproti klasickým.

Je tu však háček, a to ten, že pravděpodobnostní klasické algoritmy dokáží vyřešit Deutsch-Jozsův problém s velmi vysokou pravděpodobností pomocí pouhých několika dotazů. Konkrétně, pokud jednoduše náhodně zvolíme několik různých řetězců délky $n$ a dotážeme se $f$ na tyto řetězce, je nepravděpodobné, že pro všechny získáme stejnou hodnotu funkce, když je $f$ vyvážená.

Přesněji řečeno, pokud zvolíme $k$ vstupních řetězců $x^1,\ldots,x^k \in \Sigma^n$ rovnoměrně náhodně, vyhodnotíme $f(x^1),\ldots,f(x^k)$ a odpovíme $0$, pokud jsou všechny hodnoty funkce stejné, a $1$, pokud ne, pak budeme vždy správně, když je $f$ konstantní, a v případě, že $f$ je vyvážená, se zmýlíme s pravděpodobností pouhých $2^{-k + 1}.$ Pokud vezmeme například $k = 11,$ tento algoritmus odpoví správně s pravděpodobností větší než $99{,}9$%.

Z tohoto důvodu máme stále poměrně skromnou výhodu kvantových algoritmů oproti klasickým — ale přesto jde o kvantifikovatelnou výhodu představující zlepšení oproti Deutschovu algoritmu.

Deutsch-Jozsův algoritmus s Qiskit

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

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator
import numpy as np

Pro implementaci Deutsch-Jozsova algoritmu v Qiskit začneme definováním funkce dj_query, která generuje kvantový Circuit implementující dotazovací Gate pro náhodně zvolenou funkci splňující příslib Deutsch-Jozsova problému. S 50% pravděpodobností je funkce konstantní a s 50% pravděpodobností je funkce vyvážená. Pro každou z těchto dvou možností je funkce zvolena rovnoměrně z funkcí daného typu. Argumentem je počet vstupních bitů funkce.

def dj_query(num_qubits):
    # Create a circuit implementing for a query gate for a random function
    # satisfying the promise for the Deutsch-Jozsa problem.

    qc = QuantumCircuit(num_qubits + 1)

    if np.random.randint(0, 2):
        # Flip output qubit with 50% chance
        qc.x(num_qubits)
    if np.random.randint(0, 2):
        # return constant circuit with 50% chance
        return qc

    # Choose half the possible input strings
    on_states = np.random.choice(
        range(2**num_qubits),  # numbers to sample from
        2**num_qubits // 2,  # number of samples
        replace=False,  # makes sure states are only sampled once
    )

    def add_cx(qc, bit_string):
        for qubit, bit in enumerate(reversed(bit_string)):
            if bit == "1":
                qc.x(qubit)
        return qc

    for state in on_states:
        qc.barrier()  # Barriers are added to help visualize how the functions are created.
        qc = add_cx(qc, f"{state:0b}")
        qc.mcx(list(range(num_qubits)), num_qubits)
        qc = add_cx(qc, f"{state:0b}")

    qc.barrier()

    return qc

Implementaci dotazovací Gate jako kvantového Circuit si můžeme zobrazit pomocí metody draw, jak je obvyklé.

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

Dále definujeme funkci, která vytvoří Deutsch-Jozsův Circuit a jako argument přijímá implementaci dotazovací Gate jako kvantový Circuit.

def compile_circuit(function: QuantumCircuit):
    # Compiles a circuit for use in the Deutsch-Jozsa algorithm.

    n = function.num_qubits - 1
    qc = QuantumCircuit(n + 1, n)
    qc.x(n)
    qc.h(range(n + 1))
    qc.compose(function, inplace=True)
    qc.h(range(n))
    qc.measure(range(n), range(n))
    return qc

Nakonec je definována funkce, která jednou spustí Deutsch-Jozsův Circuit.

def dj_algorithm(function: QuantumCircuit):
    # Determine if a function is constant or balanced.

    qc = compile_circuit(function)

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

Naši implementaci si můžeme otestovat tak, že náhodně zvolíme funkci, zobrazíme kvantovou Circuit implementaci query Gate pro tuto funkci a poté na ni spustíme Deutsch-Jozsův algoritmus.

f = dj_query(3)
display(f.draw("mpl"))
display(dj_algorithm(f))

'balanced'

Bernstein-Vaziraniho problém

Dále si probereme problém známý jako Bernstein-Vaziraniho problém. Říká se mu také problém Fourierova vzorkování, i když existují obecnější formulace tohoto problému, které se také tak nazývají.

Nejprve si zaveďme notaci. Pro libovolné dva binární řetězce $x = x_{n-1} \cdots x_0$ a $y = y_{n-1}\cdots y_0$ délky $n$ definujeme

$$x \cdot y = x_{n-1} y_{n-1} \oplus \cdots \oplus x_0 y_0.$$

Tuto operaci budeme nazývat binární skalární součin. Alternativně ji lze definovat takto.

$$x \cdot y = \begin{cases} 1 & x_{{n-1}} y_{n-1} + \cdots + x_0 y_0 \text{ is odd}\\[0.5mm] 0 & x_{{n-1}} y_{n-1} + \cdots + x_0 y_0 \text{ is even} \end{cases}$$

Všimni si, že jde o symetrickou operaci, což znamená, že výsledek se nezmění, pokud prohodíme $x$ a $y,$ takže to můžeme kdykoli udělat, když se nám to hodí. Někdy je užitečné přemýšlet o binárním skalárním součinu $x \cdot y$ jako o paritě bitů $x$ na pozicích, kde má řetězec $y$ hodnotu $1,$ nebo ekvivalentně o paritě bitů $y$ na pozicích, kde má řetězec $x$ hodnotu $1.$

S touto notací nyní můžeme definovat Bernstein-Vaziraniho problém.

Bernstein-Vaziraniho problém

Vstup: funkce $f:\{0,1\}^n\rightarrow\{0,1\}$
Příslib: existuje binární řetězec $s = s_{n-1} \cdots s_0$ takový, že $f(x) = s\cdot x$ pro všechna $x\in\Sigma^n$
Výstup: řetězec $s$

Pro tento problém vlastně nepotřebujeme nový kvantový algoritmus; řeší ho Deutsch-Jozsův algoritmus. Pro přehlednost budeme kvantový Circuit shora, který nezahrnuje klasický post-processing krok výpočtu OR, nazývat Deutsch-Jozsův Circuit.

Analýza algoritmu

Abychom analyzovali, jak Deutsch-Jozsův Circuit funguje pro funkci splňující příslib Bernstein-Vaziraniho problému, začneme krátkým pozorováním. Pomocí binárního skalárního součinu můžeme alternativně popsat působení $n$ Hadamardových Gate na standardní bázové stavy $n$ Qubitů takto.

$$H^{\otimes n} \vert x \rangle = \frac{1}{\sqrt{2^n}} \sum_{y\in\Sigma^n} (-1)^{x\cdot y} \vert y\rangle$$

Podobně jako při analýze Deutschova algoritmu je to proto, že hodnota $(-1)^k$ pro libovolné celé číslo $k$ závisí pouze na tom, zda je $k$ sudé nebo liché.

Přejděme k Deutsch-Jozsovu Circuit. Po první vrstvě Hadamardových Gate je stav $n+1$ Qubitů

$$\vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x \in \Sigma^n} \vert x \rangle.$$

Poté se provede query Gate, která (prostřednictvím jevu fázového zpětného rázu) transformuje stav na

$$\vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x \in \Sigma^n} (-1)^{f(x)} \vert x \rangle.$$

Pomocí našeho vzorce pro působení vrstvy Hadamardových Gate vidíme, že druhá vrstva Hadamardových Gate poté transformuje tento stav na

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{f(x) + x \cdot y} \vert y \rangle.$$

Nyní můžeme provést zjednodušení v exponentu $-1$ uvnitř sumy. Máme příslib, že $f(x) = s\cdot x$ pro nějaký řetězec $s = s_{n-1} \cdots s_0,$ takže stav můžeme vyjádřit jako

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{s\cdot x + x \cdot y} \vert y \rangle.$$

Protože $s\cdot x$ a $x\cdot y$ jsou binární hodnoty, můžeme sčítání nahradit exkluzivním OR -- opět proto, že jediné, na čem u celého čísla v exponentu $-1$ záleží, je to, zda je sudé nebo liché. S využitím symetrie binárního skalárního součinu získáme tento výraz pro stav:

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{(s\cdot x) \oplus (y \cdot x)} \vert y \rangle.$$

(Závorky byly přidány pro přehlednost, i když nejsou nezbytně nutné, protože se konvenčně předpokládá, že binární skalární součin má vyšší prioritu než exkluzivní OR.) V tomto bodě využijeme následující vzorec.

$$(s\cdot x) \oplus (y \cdot x) = (s \oplus y) \cdot x$$

Tento vzorec můžeme odvodit z podobného vzorce pro bity,

$$(a c) \oplus (b c) = (a \oplus b) c,$$

spolu s rozpisem binárního skalárního součinu a bitového exkluzivního OR:

$$\begin{aligned} (s\cdot x) \oplus (y \cdot x) & = (s_{n-1} x_{n-1}) \oplus \cdots \oplus (s_{0} x_{0}) \oplus (y_{n-1} x_{n-1}) \oplus \cdots \oplus (y_{0} x_{0}) \\ & = (s_{n-1} \oplus y_{n-1}) x_{n-1} \oplus \cdots \oplus (s_{0} \oplus y_{0}) x_{0} \\ & = (s \oplus y) \cdot x \end{aligned}$$

To nám umožňuje vyjádřit stav Circuit těsně před měřením takto:

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{(s\oplus y)\cdot x} \vert y \rangle.$$

Posledním krokem je využití ještě dalšího vzorce, který platí pro každý binární řetězec $z = z_{n-1}\cdots z_0.$

$$\frac{1}{2^n} \sum_{x \in \Sigma^n} (-1)^{z \cdot x} = \begin{cases} 1 & \text{if $z = 0^n$}\\ 0 & \text{if $z\neq 0^n$} \end{cases}$$

Zde používáme jednoduchou notaci pro řetězce, kterou v této lekci použijeme ještě několikrát: $0^n$ je samý-nulový řetězec délky $n.$

Jednoduchý způsob, jak zdůvodnit platnost tohoto vzorce, je zvážit oba případy zvlášť. Pokud $z = 0^n,$ pak $z\cdot x = 0$ pro každý řetězec $x\in\Sigma^n,$ takže hodnota každého členu sumy je $1$ a po sečtení a vydělení $2^n$ dostaneme $1.$ Na druhou stranu, pokud je jakýkoli bit $z$ roven $1,$ pak binární skalární součin $z\cdot x$ je roven $0$ pro přesně polovinu možných voleb $x\in\Sigma^n$ a $1$ pro druhou polovinu -- protože hodnota binárního skalárního součinu $z\cdot x$ se překlopí (z $0$ na $1$ nebo z $1$ na $0$), pokud překlopíme jakýkoli bit $x$ na pozici, kde má $z$ hodnotu $1.$

Pokud nyní tento vzorec aplikujeme na zjednodušení stavu Circuit před měřením, získáme

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{(s\oplus y)\cdot x} \vert y \rangle = \vert - \rangle \otimes \vert s \rangle,$$

díky tomu, že $s\oplus y = 0^n$ právě tehdy, když $y = s.$ Měření tedy odhalí přesně řetězec $s,$ který hledáme.

Klasická obtížnost

Zatímco Deutsch-Jozsův Circuit řeší Bernstein-Vaziraniho problém jedním dotazem, jakýkoli klasický dotazovací algoritmus musí k vyřešení tohoto problému provést alespoň $n$ dotazů.

To lze zdůvodnit takzvaným informačně-teoretickým argumentem, který je v tomto případě velmi jednoduchý. Každý klasický dotaz odhalí jeden bit informace o řešení a je třeba odhalit $n$ bitů informace -- takže je potřeba alespoň $n$ dotazů.

Ve skutečnosti je možné vyřešit Bernstein-Vaziraniho problém klasicky dotazováním funkce na každý z $n$ řetězců, které mají jedinou $1$ na každé možné pozici a $0$ na všech ostatních bitech, čímž se bity $s$ odhalují jeden po druhém. Výhoda kvantových algoritmů oproti klasickým je tedy pro tento problém $1$ dotaz versus $n$ dotazů.

Bernstein-Vazirani s Qiskit

Deutsch-Jozsův Circuit jsme již implementovali výše a zde ho využijeme k řešení Bernstein-Vaziraniho problému. Nejprve definujeme funkci, která implementuje query Gate pro Bernstein-Vaziraniho problém pro libovolný binární řetězec $s.$

def bv_query(s):
    # Create a quantum circuit implementing a query gate for the
    # Bernstein-Vazirani problem.

    qc = QuantumCircuit(len(s) + 1)
    for index, bit in enumerate(reversed(s)):
        if bit == "1":
            qc.cx(index, len(s))
    return qc

display(bv_query("1011").draw(output="mpl"))

Nyní můžeme vytvořit funkci, která spustí Deutsch-Jozsův Circuit na funkci pomocí dříve definované funkce compile_circuit.

def bv_algorithm(function: QuantumCircuit):
    qc = compile_circuit(function)
    result = AerSimulator().run(qc, shots=1, memory=True).result()
    return result.get_memory()[0]

display(bv_algorithm(bv_query("1011")))

'1011'

Poznámka k názvosloví

V kontextu Bernstein-Vaziraniho problému se Deutsch-Jozsův algoritmus běžně označuje jako "Bernstein-Vaziraniho algoritmus." To je mírně zavádějící, protože tento algoritmus je Deutsch-Jozsův algoritmus, jak Bernstein a Vazirani ve své práci jasně uvedli.

Co Bernstein a Vazirani udělali poté, co ukázali, že Deutsch-Jozsův algoritmus řeší Bernstein-Vaziraniho problém (jak je formulován výše), bylo definování mnohem složitějšího problému známého jako problém rekurzivního Fourierova vzorkování. Jde o vysoce umělý problém, kde řešení různých instancí problému efektivně odemykají nové úrovně problému uspořádané do stromové struktury. Bernstein-Vaziraniho problém je v podstatě jen základní případ tohoto složitějšího problému.

Problém rekurzivního Fourierova vzorkování byl prvním známým příkladem dotazovacího problému, kde kvantové algoritmy mají takzvanou super-polynomiální výhodu oproti pravděpodobnostním algoritmům, čímž překonávají výhodu kvantového nad klasickým přístupem, kterou nabízí Deutsch-Jozsův algoritmus. Intuitivně řečeno, rekurzivní verze problému zesiluje výhodu $1$ versus $n$ kvantových algoritmů na něco mnohem většího.

Nejnáročnějším aspektem matematické analýzy prokazující tuto výhodu je ukázat, že klasické dotazovací algoritmy nemohou problém vyřešit bez velkého počtu dotazů. To je dost typické; u mnoha problémů může být velmi obtížné vyloučit kreativní klasické přístupy, které je efektivně řeší.

Simonův problém a algoritmus pro něj popsaný v další sekci však poskytují mnohem jednodušší příklad super-polynomiální (a ve skutečnosti exponenciální) výhody kvantových algoritmů oproti klasickým, a proto se problém rekurzivního Fourierova vzorkování diskutuje méně často. Přesto je to sám o sobě zajímavý výpočetní problém.