L'algoritmo di Deutsch-Jozsa

L'algoritmo di Deutsch supera tutti gli algoritmi classici per un problema di query, ma il vantaggio è piuttosto modesto: una query contro due. L'algoritmo di Deutsch-Jozsa estende questo vantaggio — e, in effetti, può essere usato per risolvere un paio di problemi di query diversi.

Ecco una descrizione circuitale quantistica dell'algoritmo di Deutsch-Jozsa. Un ulteriore passo di post-elaborazione classica, non mostrato nella figura, può essere necessario a seconda del problema specifico da risolvere.

Naturalmente, non abbiamo ancora discusso quali problemi risolve questo algoritmo; questo viene fatto nelle due sezioni che seguono.

Il problema di Deutsch-Jozsa

Inizieremo con il problema di query che l'algoritmo di Deutsch-Jozsa era originalmente destinato a risolvere, noto come il problema di Deutsch-Jozsa.

La funzione di input per questo problema ha la forma $f:\Sigma^n \rightarrow \Sigma$ per un intero positivo arbitrario $n.$ Come nel problema di Deutsch, il compito è restituire $0$ se $f$ è costante e $1$ se $f$ è bilanciata, il che significa che il numero di stringhe di input su cui la funzione assume il valore $0$ è uguale al numero di stringhe di input su cui la funzione assume il valore $1$.

Nota che, quando $n$ è maggiore di $1,$ esistono funzioni della forma $f:\Sigma^n \rightarrow \Sigma$ che non sono né costanti né bilanciate. Per esempio, la funzione $f:\Sigma^2\rightarrow\Sigma$ definita come

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

non rientra in nessuna di queste due categorie. Per il problema di Deutsch-Jozsa, semplicemente non ci preoccupiamo di funzioni come questa — sono considerate input "don't care". Cioè, per questo problema abbiamo la promessa che $f$ sia costante o bilanciata.

Problema di Deutsch-Jozsa

Input: una funzione $f:\{0,1\}^n\rightarrow\{0,1\}$
Promessa: $f$ è costante o bilanciata
Output: $0$ se $f$ è costante, $1$ se $f$ è bilanciata

L'algoritmo di Deutsch-Jozsa, con la sua singola query, risolve questo problema nel senso seguente: se tutti gli $n$ risultati di misura sono $0,$ allora la funzione $f$ è costante; altrimenti, se almeno uno dei risultati di misura è $1,$ allora la funzione $f$ è bilanciata. Un altro modo di dirlo è che il circuito descritto sopra è seguito da un passo di post-elaborazione classica in cui viene calcolato l'OR dei risultati di misura per produrre l'output.

Analisi dell'algoritmo

Per analizzare le prestazioni dell'algoritmo di Deutsch-Jozsa sul problema di Deutsch-Jozsa, è utile iniziare pensando all'azione di un singolo strato di gate di Hadamard. Un'operazione di Hadamard può essere espressa come una matrice nel solito modo,

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

ma possiamo anche esprimere questa operazione in termini della sua azione sugli stati della base standard:

$$\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}$$

Queste due equazioni possono essere combinate in un'unica formula,

$$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,$$

che vale per entrambe le scelte di $a\in\Sigma.$

Supponiamo ora che invece di un singolo qubit ne abbiamo $n,$ e che su ciascuno venga eseguita un'operazione di Hadamard. L'operazione combinata sugli $n$ qubit è descritta dal prodotto tensoriale $H\otimes \cdots \otimes H$ ($n$ volte), che scriviamo come $H^{\otimes n}$ per concisione e chiarezza. Usando la formula sopra, seguita dall'espansione e dalla semplificazione, possiamo esprimere l'azione di questa operazione combinata sugli stati della base standard di $n$ qubit così:

$$\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}$$

Qui, tra l'altro, stiamo scrivendo le stringhe binarie di lunghezza $n$ come $x_{n-1}\cdots x_0$ e $y_{n-1}\cdots y_0,$ seguendo la convenzione di indicizzazione di Qiskit.

Questa formula ci fornisce uno strumento utile per analizzare il circuito quantistico sopra descritto. Dopo che viene eseguito il primo strato di gate di Hadamard, lo stato degli $n+1$ qubit (incluso il qubit più a sinistra/in basso, che viene trattato separatamente dagli altri) è

$$\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.$$

Quando viene eseguita l'operazione $U_f,$ questo stato viene trasformato in

$$\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$$

attraverso esattamente lo stesso fenomeno di phase kick-back che abbiamo visto nell'analisi dell'algoritmo di Deutsch.

Poi viene eseguito il secondo strato di gate di Hadamard, che (tramite la formula sopra) trasforma questo stato in

$$\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.$$

Questa espressione sembra piuttosto complicata, e senza sapere di più sulla funzione $f$ non si può concludere molto sulle probabilità di ottenere risultati di misura diversi.

Fortunatamente, tutto ciò che dobbiamo sapere è la probabilità che tutti i risultati di misura siano $0$ — perché questa è la probabilità che l'algoritmo determini che $f$ è costante. Questa probabilità ha una formula semplice.

$$\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}$$

In dettaglio, se $f$ è costante, allora o $f(x_{n-1}\cdots x_0) = 0$ per ogni stringa $x_{n-1}\cdots x_0,$ nel qual caso il valore della somma è $2^n,$ oppure $f(x_{n-1}\cdots x_0) = 1$ per ogni stringa $x_{n-1}\cdots x_0,$ nel qual caso il valore della somma è $-2^n.$ Dividendo per $2^n$ e calcolando il quadrato del valore assoluto si ottiene $1.$

Se invece $f$ è bilanciata, allora $f$ assume il valore $0$ sulla metà delle stringhe $x_{n-1}\cdots x_0$ e il valore $1$ sull'altra metà, quindi i termini $+1$ e $-1$ nella somma si cancellano e rimaniamo con il valore $0.$

Concludiamo che l'algoritmo opera correttamente a condizione che la promessa sia rispettata.

Difficoltà classica

L'algoritmo di Deutsch-Jozsa funziona ogni volta, fornendo sempre la risposta corretta quando la promessa è soddisfatta, e richiede una singola query. Come si confronta questo con gli algoritmi di query classici per il problema di Deutsch-Jozsa?

Innanzitutto, qualsiasi algoritmo classico deterministico che risolve correttamente il problema di Deutsch-Jozsa deve effettuare un numero esponenziale di query: nel caso peggiore sono necessarie $2^{n-1} + 1$ query. Il ragionamento è che, se un algoritmo deterministico interroga $f$ su $2^{n-1}$ o meno stringhe diverse e ottiene ogni volta lo stesso valore della funzione, allora entrambe le risposte sono ancora possibili. La funzione potrebbe essere costante, oppure potrebbe essere bilanciata ma per sfortuna le query restituiscono tutte lo stesso valore della funzione.

La seconda possibilità potrebbe sembrare improbabile — ma per gli algoritmi deterministici non c'è casualità né incertezza, quindi falliranno sistematicamente su certe funzioni. Abbiamo quindi un vantaggio significativo degli algoritmi quantistici rispetto a quelli classici in questo senso.

C'è però un'eccezione: gli algoritmi classici probabilistici possono risolvere il problema di Deutsch-Jozsa con probabilità molto alta usando solo poche query. In particolare, se scegliamo semplicemente alcune stringhe diverse di lunghezza $n$ a caso e interroghiamo $f$ su quelle stringhe, è improbabile che otteniamo lo stesso valore della funzione per tutte quando $f$ è bilanciata.

In dettaglio, se scegliamo $k$ stringhe di input $x^1,\ldots,x^k \in \Sigma^n$ uniformemente a caso, valutiamo $f(x^1),\ldots,f(x^k),$ e rispondiamo $0$ se i valori della funzione sono tutti uguali e $1$ altrimenti, saremo sempre corretti quando $f$ è costante, e sbagliati nel caso in cui $f$ sia bilanciata con probabilità solo $2^{-k + 1}.$ Se prendiamo $k = 11,$ per esempio, questo algoritmo risponderà correttamente con probabilità superiore al $99,9$%.

Per questo motivo, abbiamo ancora un vantaggio piuttosto modesto degli algoritmi quantistici rispetto a quelli classici — ma è comunque un vantaggio quantificabile che rappresenta un miglioramento rispetto all'algoritmo di Deutsch.

Deutsch-Jozsa con 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

Per implementare l'algoritmo di Deutsch-Jozsa in Qiskit, inizieremo definendo una funzione dj_query che genera un circuito quantistico che implementa un gate di query, per una funzione selezionata casualmente che soddisfa la promessa del problema di Deutsch-Jozsa. Con il 50% di probabilità la funzione è costante, e con il 50% di probabilità è bilanciata. Per ciascuna di queste due possibilità, la funzione viene selezionata uniformemente tra le funzioni di quel tipo. L'argomento è il numero di bit di input della funzione.

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

Possiamo mostrare l'implementazione circuitale quantistica del gate di query usando il metodo draw come di consueto.

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

Definiamo poi una funzione che crea il circuito di Deutsch-Jozsa, prendendo come argomento un'implementazione circuitale quantistica di un gate di query.

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

Infine, viene definita una funzione che esegue il circuito di Deutsch-Jozsa una volta sola.

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"

Possiamo testare la nostra implementazione scegliendo una funzione a caso, visualizzando l'implementazione circuitale quantistica di un gate di query per quella funzione, e poi eseguendo l'algoritmo di Deutsch-Jozsa su quella funzione.

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

'balanced'

Il problema di Bernstein-Vazirani

Successivamente, discuteremo un problema noto come il problema di Bernstein-Vazirani. È chiamato anche problema di campionamento di Fourier, sebbene esistano formulazioni più generali di questo problema che vanno sotto lo stesso nome.

Prima di tutto, introduciamo una notazione. Per due stringhe binarie qualsiasi $x = x_{n-1} \cdots x_0$ e $y = y_{n-1}\cdots y_0$ di lunghezza $n,$ definiamo

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

Ci riferiremo a questa operazione come al prodotto scalare binario. Un modo alternativo di definirlo è il seguente.

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

Nota che questa è un'operazione simmetrica, il che significa che il risultato non cambia se scambiamo $x$ e $y,$ quindi siamo liberi di farlo ogni volta che è conveniente. A volte è utile pensare al prodotto scalare binario $x \cdot y$ come alla parità dei bit di $x$ nelle posizioni in cui la stringa $y$ ha un $1,$ o equivalentemente, come alla parità dei bit di $y$ nelle posizioni in cui la stringa $x$ ha un $1.$

Con questa notazione possiamo ora definire il problema di Bernstein-Vazirani.

Problema di Bernstein-Vazirani

Input: una funzione $f:\{0,1\}^n\rightarrow\{0,1\}$
Promessa: esiste una stringa binaria $s = s_{n-1} \cdots s_0$ tale che $f(x) = s\cdot x$ per ogni $x\in\Sigma^n$
Output: la stringa $s$

In realtà non abbiamo bisogno di un nuovo algoritmo quantistico per questo problema; l'algoritmo di Deutsch-Jozsa lo risolve. Per chiarezza, ci riferiremo al circuito quantistico sopra descritto, che non include il passo di post-elaborazione classica del calcolo dell'OR, come il circuito di Deutsch-Jozsa.

Analisi dell'algoritmo

Per analizzare come funziona il circuito di Deutsch-Jozsa per una funzione che soddisfa la promessa del problema di Bernstein-Vazirani, inizieremo con una rapida osservazione. Usando il prodotto scalare binario, possiamo descrivere in modo alternativo l'azione di $n$ gate di Hadamard sugli stati della base standard di $n$ qubit come segue.

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

Come abbiamo visto nell'analisi dell'algoritmo di Deutsch, questo è valido perché il valore $(-1)^k$ per qualsiasi intero $k$ dipende solo dal fatto che $k$ sia pari o dispari.

Passando al circuito di Deutsch-Jozsa, dopo che viene eseguito il primo strato di gate di Hadamard, lo stato degli $n+1$ qubit è

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

Viene poi eseguito il gate di query, che (attraverso il fenomeno di phase kickback) trasforma lo stato in

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

Usando la nostra formula per l'azione di uno strato di gate di Hadamard, vediamo che il secondo strato di gate di Hadamard trasforma questo stato in

$$\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.$$

Ora possiamo fare alcune semplificazioni nell'esponente di $-1$ all'interno della somma. Ci è promesso che $f(x) = s\cdot x$ per una qualche stringa $s = s_{n-1} \cdots s_0,$ quindi possiamo esprimere lo stato come

$$\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.$$

Poiché $s\cdot x$ e $x\cdot y$ sono valori binari, possiamo sostituire l'addizione con l'OR esclusivo — di nuovo perché l'unica cosa che conta per un intero nell'esponente di $-1$ è se è pari o dispari. Facendo uso della simmetria del prodotto scalare binario, otteniamo questa espressione per lo stato:

$$\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.$$

(Le parentesi sono state aggiunte per chiarezza, anche se non sono strettamente necessarie poiché è convenzione trattare il prodotto scalare binario come avente precedenza più alta rispetto all'OR esclusivo.)

A questo punto useremo la seguente formula.

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

Possiamo ricavare la formula attraverso un'analoga formula per i bit,

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

insieme a un'espansione del prodotto scalare binario e dell'OR esclusivo bit a bit:

$$\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}$$

Questo ci permette di esprimere lo stato del circuito immediatamente prima delle misure così:

$$\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.$$

Il passo finale è fare uso di ancora un'altra formula, che vale per ogni stringa binaria $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}$$

Qui stiamo usando una semplice notazione per le stringhe che useremo ancora diverse volte nella lezione: $0^n$ è la stringa di tutti zeri di lunghezza $n.$

Un modo semplice per dimostrare che questa formula funziona è considerare i due casi separatamente. Se $z = 0^n,$ allora $z\cdot x = 0$ per ogni stringa $x\in\Sigma^n,$ quindi il valore di ogni termine nella somma è $1,$ e otteniamo $1$ sommando e dividendo per $2^n.$ Se invece uno qualsiasi dei bit di $z$ è uguale a $1,$ allora il prodotto scalare binario $z\cdot x$ è uguale a $0$ per esattamente metà delle possibili scelte di $x\in\Sigma^n$ e $1$ per l'altra metà — perché il valore del prodotto scalare binario $z\cdot x$ si inverte (da $0$ a $1$ o da $1$ a $0$) se invertiamo qualsiasi bit di $x$ in una posizione in cui $z$ ha un $1.$

Se ora applichiamo questa formula per semplificare lo stato del circuito prima delle misure, otteniamo

$$\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,$$

grazie al fatto che $s\oplus y = 0^n$ se e solo se $y = s.$ Quindi le misure rivelano esattamente la stringa $s$ che stiamo cercando.

Difficoltà classica

Mentre il circuito di Deutsch-Jozsa risolve il problema di Bernstein-Vazirani con una singola query, qualsiasi algoritmo di query classico deve effettuare almeno $n$ query per risolvere questo problema.

Ciò può essere argomentato tramite un cosiddetto argomento teorico dell'informazione, che è molto semplice in questo caso. Ogni query classica rivela un singolo bit di informazione sulla soluzione, e ci sono $n$ bit di informazione da scoprire — quindi sono necessarie almeno $n$ query.

È in effetti possibile risolvere il problema di Bernstein-Vazirani classicamente interrogando la funzione su ciascuna delle $n$ stringhe con un singolo $1$ in ogni possibile posizione e $0$ per tutti gli altri bit, il che rivela i bit di $s$ uno alla volta. Pertanto, il vantaggio degli algoritmi quantistici rispetto a quelli classici per questo problema è di $1$ query contro $n$ query.

Bernstein-Vazirani con Qiskit

Abbiamo già implementato il circuito di Deutsch-Jozsa sopra, e qui lo utilizzeremo per risolvere il problema di Bernstein-Vazirani. Prima definiremo una funzione che implementa un gate di query per il problema di Bernstein-Vazirani data una qualsiasi stringa binaria $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"))

Ora possiamo creare una funzione che esegue il circuito di Deutsch-Jozsa sulla funzione, usando la funzione compile_circuit definita in precedenza.

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'

Nota sulla nomenclatura

Nel contesto del problema di Bernstein-Vazirani, è comune che l'algoritmo di Deutsch-Jozsa venga chiamato "algoritmo di Bernstein-Vazirani." Questo è leggermente fuorviante, perché l'algoritmo è l'algoritmo di Deutsch-Jozsa, come Bernstein e Vazirani hanno chiarito esplicitamente nel loro lavoro.

Ciò che Bernstein e Vazirani fecero dopo aver dimostrato che l'algoritmo di Deutsch-Jozsa risolve il problema di Bernstein-Vazirani (come enunciato sopra) fu definire un problema molto più complicato, noto come il problema ricorsivo di campionamento di Fourier. Questo è un problema altamente artificiato in cui le soluzioni a diverse istanze del problema aprono effettivamente nuovi livelli del problema organizzati in una struttura ad albero. Il problema di Bernstein-Vazirani è essenzialmente solo il caso base di questo problema più complicato.

Il problema ricorsivo di campionamento di Fourier è stato il primo esempio noto di un problema di query in cui gli algoritmi quantistici hanno un vantaggio cosiddetto super-polinomiale rispetto agli algoritmi probabilistici, superando così il vantaggio degli algoritmi quantistici rispetto a quelli classici offerto dall'algoritmo di Deutsch-Jozsa. Intuitivamente, la versione ricorsiva del problema amplifica il vantaggio di $1$ contro $n$ degli algoritmi quantistici a qualcosa di molto più grande.

L'aspetto più impegnativo dell'analisi matematica che stabilisce questo vantaggio è dimostrare che gli algoritmi di query classici non possono risolvere il problema senza effettuare molte query. Questo è abbastanza tipico; per molti problemi può essere molto difficile escludere approcci classici creativi che li risolvono in modo efficiente.

Il problema di Simon, e l'algoritmo per esso descritto nella sezione successiva, fornisce un esempio molto più semplice di un vantaggio super-polinomiale (e, in effetti, esponenziale) degli algoritmi quantistici rispetto a quelli classici, e per questo motivo il problema ricorsivo di campionamento di Fourier viene discusso meno frequentemente. È, tuttavia, un problema computazionale interessante di per sé.