L'algorithme de Deutsch-Jozsa

L'algorithme de Deutsch surpasse tous les algorithmes classiques pour un problème de requête, mais l'avantage est assez modeste : une requête contre deux. L'algorithme de Deutsch-Jozsa étend cet avantage — et, en fait, il peut être utilisé pour résoudre deux problèmes de requête différents.

Voici une description par circuit quantique de l'algorithme de Deutsch-Jozsa. Une étape supplémentaire de post-traitement classique, non représentée dans la figure, peut également être nécessaire selon le problème spécifique à résoudre.

Bien sûr, nous n'avons pas encore évoqué les problèmes que cet algorithme résout ; c'est l'objet des deux sections qui suivent.

Le problème de Deutsch-Jozsa

Nous allons commencer par le problème de requête que l'algorithme de Deutsch-Jozsa était initialement conçu pour résoudre, connu sous le nom de problème de Deutsch-Jozsa.

La fonction d'entrée de ce problème prend la forme $f:\Sigma^n \rightarrow \Sigma$ pour un entier positif arbitraire $n.$ Comme pour le problème de Deutsch, la tâche consiste à produire $0$ si $f$ est constante et $1$ si $f$ est équilibrée, ce qui signifie que le nombre de chaînes d'entrée pour lesquelles la fonction prend la valeur $0$ est égal au nombre de chaînes d'entrée pour lesquelles la fonction prend la valeur $1$.

Remarque : lorsque $n$ est supérieur à $1,$ il existe des fonctions de la forme $f:\Sigma^n \rightarrow \Sigma$ qui ne sont ni constantes ni équilibrées. Par exemple, la fonction $f:\Sigma^2\rightarrow\Sigma$ définie par

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

n'appartient à aucune de ces deux catégories. Pour le problème de Deutsch-Jozsa, on ne se préoccupe tout simplement pas de fonctions comme celle-ci — elles sont considérées comme des entrées « sans importance ». Autrement dit, pour ce problème nous avons une promesse que $f$ est soit constante soit équilibrée.

Problème de Deutsch-Jozsa

Entrée : une fonction $f:\{0,1\}^n\rightarrow\{0,1\}$
Promesse : $f$ est soit constante soit équilibrée
Sortie : $0$ si $f$ est constante, $1$ si $f$ est équilibrée

L'algorithme de Deutsch-Jozsa, avec sa requête unique, résout ce problème de la façon suivante : si chacun des $n$ résultats de mesure vaut $0,$ alors la fonction $f$ est constante ; sinon, si au moins un des résultats de mesure vaut $1,$ alors la fonction $f$ est équilibrée. Une autre façon de le formuler est que le circuit décrit ci-dessus est suivi d'une étape de post-traitement classique dans laquelle le OU des résultats de mesure est calculé pour produire la sortie.

Analyse de l'algorithme

Pour analyser les performances de l'algorithme de Deutsch-Jozsa sur le problème de Deutsch-Jozsa, il est utile de commencer par réfléchir à l'action d'une seule couche de portes Hadamard. Une opération de Hadamard peut être exprimée sous forme de matrice de la manière habituelle,

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

mais on peut aussi exprimer cette opération à travers son action sur les états de la 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}$$

Ces deux équations peuvent être regroupées en une seule formule,

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

qui est valide pour les deux choix de $a\in\Sigma.$

Supposons maintenant qu'au lieu d'un seul qubit on dispose de $n$ qubits, et qu'une opération de Hadamard est appliquée à chacun. L'opération combinée sur les $n$ qubits est décrite par le produit tensoriel $H\otimes \cdots \otimes H$ ($n$ fois), que l'on note $H^{\otimes n}$ par concision et clarté. En utilisant la formule ci-dessus, puis en développant et en simplifiant, on peut exprimer l'action de cette opération combinée sur les états de la base standard de $n$ qubits comme suit :

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

Notons ici que l'on écrit les chaînes binaires de longueur $n$ sous la forme $x_{n-1}\cdots x_0$ et $y_{n-1}\cdots y_0,$ en suivant la convention d'indexation de Qiskit.

Cette formule nous fournit un outil utile pour analyser le circuit quantique ci-dessus. Après l'exécution de la première couche de portes Hadamard, l'état des $n+1$ qubits (y compris le qubit le plus à gauche/bas, traité séparément des autres) est

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

Lorsque l'opération $U_f$ est appliquée, cet état est transformé en

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

par exactement le même phénomène de retour de phase que celui observé dans l'analyse de l'algorithme de Deutsch.

Ensuite, la deuxième couche de portes Hadamard est appliquée, ce qui (d'après la formule ci-dessus) transforme cet état en

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

Cette expression semble assez complexe, et sans mieux connaître la fonction $f,$ on ne peut pas conclure grand-chose sur les probabilités d'obtenir différents résultats de mesure.

Heureusement, tout ce dont on a besoin est la probabilité que chacun des résultats de mesure soit $0$ — car c'est la probabilité que l'algorithme détermine que $f$ est constante. Cette probabilité a une formule simple.

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

Plus en détail, si $f$ est constante, alors soit $f(x_{n-1}\cdots x_0) = 0$ pour toute chaîne $x_{n-1}\cdots x_0,$ auquel cas la valeur de la somme est $2^n,$ soit $f(x_{n-1}\cdots x_0) = 1$ pour toute chaîne $x_{n-1}\cdots x_0,$ auquel cas la valeur de la somme est $-2^n.$ En divisant par $2^n$ et en prenant le carré de la valeur absolue, on obtient $1.$

Si, en revanche, $f$ est équilibrée, alors $f$ prend la valeur $0$ sur la moitié des chaînes $x_{n-1}\cdots x_0$ et la valeur $1$ sur l'autre moitié, donc les termes $+1$ et $-1$ de la somme s'annulent et on obtient la valeur $0.$

On conclut que l'algorithme fonctionne correctement tant que la promesse est respectée.

Difficulté classique

L'algorithme de Deutsch-Jozsa fonctionne à chaque fois, donnant toujours la bonne réponse lorsque la promesse est respectée, et nécessite une seule requête. Comment cela se compare-t-il aux algorithmes de requête classiques pour le problème de Deutsch-Jozsa ?

Premièrement, tout algorithme classique déterministe qui résout correctement le problème de Deutsch-Jozsa doit faire un nombre exponentiel de requêtes : $2^{n-1} + 1$ requêtes sont nécessaires dans le pire des cas. Le raisonnement est le suivant : si un algorithme déterministe interroge $f$ sur $2^{n-1}$ chaînes différentes ou moins, et obtient la même valeur de fonction à chaque fois, les deux réponses restent possibles. La fonction pourrait être constante, ou elle pourrait être équilibrée mais par malchance toutes les requêtes renvoient la même valeur de fonction.

Cette deuxième possibilité peut sembler peu probable — mais pour les algorithmes déterministes il n'y a pas d'aléatoire ni d'incertitude, donc ils échoueront systématiquement sur certaines fonctions. On dispose donc d'un avantage significatif des algorithmes quantiques sur les algorithmes classiques à cet égard.

Il y a cependant un bémol : les algorithmes classiques probabilistes peuvent résoudre le problème de Deutsch-Jozsa avec une très haute probabilité en utilisant seulement quelques requêtes. En particulier, si l'on choisit quelques chaînes différentes de longueur $n$ aléatoirement, et qu'on interroge $f$ sur ces chaînes, il est peu probable d'obtenir la même valeur de fonction pour toutes lorsque $f$ est équilibrée.

Plus précisément, si on choisit $k$ chaînes d'entrée $x^1,\ldots,x^k \in \Sigma^n$ uniformément au hasard, qu'on évalue $f(x^1),\ldots,f(x^k),$ et qu'on répond $0$ si toutes les valeurs de la fonction sont identiques, et $1$ sinon, alors on sera toujours correct lorsque $f$ est constante, et on se trompera dans le cas où $f$ est équilibrée avec une probabilité de seulement $2^{-k + 1}.$ Si l'on prend $k = 11,$ par exemple, cet algorithme répondra correctement avec une probabilité supérieure à $99{,}9$%.

Pour cette raison, l'avantage quantique sur le classique reste assez modeste — mais il n'en représente pas moins un avantage quantifiable qui constitue une amélioration par rapport à l'algorithme de Deutsch.

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

Pour implémenter l'algorithme de Deutsch-Jozsa dans Qiskit, on va d'abord définir une fonction dj_query qui génère un circuit quantique implémentant une porte de requête, pour une fonction sélectionnée aléatoirement respectant la promesse du problème de Deutsch-Jozsa. Avec une probabilité de 50 %, la fonction est constante, et avec 50 % de chance la fonction est équilibrée. Pour chacune de ces deux possibilités, la fonction est choisie uniformément parmi les fonctions de ce type. L'argument est le nombre de bits d'entrée de la fonction.

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

On peut afficher le circuit quantique implémentant la porte de requête en utilisant la méthode draw comme d'habitude.

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

Ensuite, on définit une fonction qui crée le circuit de Deutsch-Jozsa, prenant en argument un circuit quantique implémentant une porte de requête.

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

Enfin, on définit une fonction qui exécute le circuit de Deutsch-Jozsa une seule fois.

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"

On peut tester notre implémentation en choisissant une fonction aléatoirement, en affichant le circuit quantique implémentant la porte de requête pour cette fonction, puis en exécutant l'algorithme de Deutsch-Jozsa sur cette fonction.

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

'balanced'

Le problème de Bernstein-Vazirani

Ensuite, nous allons aborder un problème connu sous le nom de problème de Bernstein-Vazirani. On l'appelle aussi le problème d'échantillonnage de Fourier, bien qu'il existe des formulations plus générales de ce problème qui portent également ce nom.

Commençons par introduire quelques notations. Pour deux chaînes binaires quelconques $x = x_{n-1} \cdots x_0$ et $y = y_{n-1}\cdots y_0$ de longueur $n,$ on définit

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

On appellera cette opération le produit scalaire binaire. Une autre façon de le définir est la suivante.

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

Remarque : il s'agit d'une opération symétrique, ce qui signifie que le résultat ne change pas si on échange $x$ et $y,$ donc on peut le faire librement lorsque c'est pratique. Il est parfois utile de penser au produit scalaire binaire $x \cdot y$ comme à la parité des bits de $x$ aux positions où la chaîne $y$ vaut $1,$ ou de manière équivalente, la parité des bits de $y$ aux positions où la chaîne $x$ vaut $1.$

Avec cette notation, on peut maintenant définir le problème de Bernstein-Vazirani.

Problème de Bernstein-Vazirani

Entrée : une fonction $f:\{0,1\}^n\rightarrow\{0,1\}$
Promesse : il existe une chaîne binaire $s = s_{n-1} \cdots s_0$ telle que $f(x) = s\cdot x$ pour tout $x\in\Sigma^n$
Sortie : la chaîne $s$

On n'a pas besoin d'un nouvel algorithme quantique pour ce problème ; l'algorithme de Deutsch-Jozsa le résout. Par souci de clarté, appelons circuit de Deutsch-Jozsa le circuit quantique ci-dessus, qui n'inclut pas l'étape de post-traitement classique consistant à calculer le OU.

Analyse de l'algorithme

Pour analyser comment le circuit de Deutsch-Jozsa fonctionne pour une fonction respectant la promesse du problème de Bernstein-Vazirani, commençons par une observation rapide. En utilisant le produit scalaire binaire, on peut décrire alternativement l'action de $n$ portes Hadamard sur les états de la base standard de $n$ qubits comme suit.

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

Comme dans l'analyse de l'algorithme de Deutsch, cela s'explique par le fait que la valeur $(-1)^k$ pour tout entier $k$ ne dépend que de la parité de $k.$

En revenant au circuit de Deutsch-Jozsa, après l'exécution de la première couche de portes Hadamard, l'état des $n+1$ qubits est

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

La porte de requête est ensuite appliquée, ce qui (via le phénomène de retour de phase) transforme l'état en

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

En utilisant notre formule pour l'action d'une couche de portes Hadamard, on voit que la deuxième couche de portes Hadamard transforme alors cet état en

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

On peut maintenant faire quelques simplifications dans l'exposant de $-1$ à l'intérieur de la somme. Il nous est promis que $f(x) = s\cdot x$ pour une certaine chaîne $s = s_{n-1} \cdots s_0,$ donc on peut exprimer l'état comme

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

Comme $s\cdot x$ et $x\cdot y$ sont des valeurs binaires, on peut remplacer l'addition par le ou-exclusif — à nouveau parce que la seule chose qui compte pour un entier dans l'exposant de $-1$ est de savoir s'il est pair ou impair. En exploitant la symétrie du produit scalaire binaire, on obtient cette expression pour l'état :

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

(Des parenthèses ont été ajoutées pour la clarté, bien qu'elles ne soient pas strictement nécessaires car il est conventionnel de traiter le produit scalaire binaire comme ayant une priorité plus élevée que le ou-exclusif.)

À ce stade, on va utiliser la formule suivante.

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

On peut obtenir cette formule à partir d'une formule similaire pour les bits,

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

combinée avec un développement du produit scalaire binaire et du ou-exclusif bit à 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}$$

Cela nous permet d'exprimer l'état du circuit juste avant les mesures comme suit :

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

La dernière étape consiste à utiliser encore une autre formule, qui s'applique à toute chaîne binaire $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}$$

Ici on utilise une notation simple pour les chaînes que l'on utilisera plusieurs fois encore dans ce cours : $0^n$ est la chaîne tout-zéro de longueur $n.$

Une façon simple de vérifier que cette formule est correcte est de considérer les deux cas séparément. Si $z = 0^n,$ alors $z\cdot x = 0$ pour toute chaîne $x\in\Sigma^n,$ donc la valeur de chaque terme de la somme est $1,$ et on obtient $1$ en sommant et en divisant par $2^n.$ En revanche, si l'un des bits de $z$ vaut $1,$ alors le produit scalaire binaire $z\cdot x$ est égal à $0$ pour exactement la moitié des choix possibles de $x\in\Sigma^n$ et à $1$ pour l'autre moitié — car la valeur du produit scalaire binaire $z\cdot x$ change (de $0$ à $1$ ou de $1$ à $0$) si on inverse un bit de $x$ à une position où $z$ vaut $1.$

Si on applique maintenant cette formule pour simplifier l'état du circuit avant les mesures, on obtient

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

grâce au fait que $s\oplus y = 0^n$ si et seulement si $y = s.$ Ainsi, les mesures révèlent précisément la chaîne $s$ que l'on cherche.

Difficulté classique

Alors que le circuit de Deutsch-Jozsa résout le problème de Bernstein-Vazirani avec une seule requête, tout algorithme de requête classique doit faire au moins $n$ requêtes pour résoudre ce problème.

On peut le déduire via un argument dit théorique de l'information, qui est très simple dans ce cas. Chaque requête classique révèle un seul bit d'information sur la solution, et il y a $n$ bits d'information à découvrir — donc au moins $n$ requêtes sont nécessaires.

Il est en fait possible de résoudre le problème de Bernstein-Vazirani classiquement en interrogeant la fonction sur chacune des $n$ chaînes ayant un seul $1,$ dans chaque position possible, et $0$ pour tous les autres bits, ce qui révèle les bits de $s$ un par un. Ainsi, l'avantage quantique sur le classique pour ce problème est de $1$ requête contre $n$ requêtes.

Bernstein-Vazirani avec Qiskit

On a déjà implémenté le circuit de Deutsch-Jozsa ci-dessus, et on va l'utiliser ici pour résoudre le problème de Bernstein-Vazirani. On va d'abord définir une fonction qui implémente une porte de requête pour le problème de Bernstein-Vazirani étant donné une chaîne binaire $s$ quelconque.

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"))

On peut maintenant créer une fonction qui exécute le circuit de Deutsch-Jozsa sur la fonction, en utilisant la fonction compile_circuit définie précédemment.

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'

Remarque sur la nomenclature

Dans le contexte du problème de Bernstein-Vazirani, il est courant que l'algorithme de Deutsch-Jozsa soit désigné sous le nom d'« algorithme de Bernstein-Vazirani ». C'est quelque peu trompeur, car l'algorithme est l'algorithme de Deutsch-Jozsa, comme Bernstein et Vazirani l'ont clairement indiqué dans leurs travaux.

Ce que Bernstein et Vazirani ont fait après avoir montré que l'algorithme de Deutsch-Jozsa résout le problème de Bernstein-Vazirani (tel qu'il est énoncé ci-dessus) a été de définir un problème beaucoup plus complexe, connu sous le nom de problème d'échantillonnage de Fourier récursif. Il s'agit d'un problème très artificiel où les solutions à différentes instances du problème débloquent effectivement de nouveaux niveaux du problème organisés en une structure arborescente. Le problème de Bernstein-Vazirani n'est essentiellement que le cas de base de ce problème plus complexe.

Le problème d'échantillonnage de Fourier récursif a été le premier exemple connu d'un problème de requête où les algorithmes quantiques ont un avantage dit super-polynomial sur les algorithmes probabilistes, surpassant ainsi l'avantage quantique sur le classique offert par l'algorithme de Deutsch-Jozsa. Intuitivement, la version récursive du problème amplifie l'avantage de $1$ contre $n$ des algorithmes quantiques à quelque chose de bien plus grand.

L'aspect le plus difficile de l'analyse mathématique établissant cet avantage est de montrer que les algorithmes de requête classiques ne peuvent pas résoudre le problème sans faire beaucoup de requêtes. C'est assez typique ; pour de nombreux problèmes, il peut être très difficile d'exclure des approches classiques créatives qui les résolvent efficacement.

Le problème de Simon, et l'algorithme correspondant décrit dans la section suivante, fournit un exemple bien plus simple d'un avantage super-polynomial (et, en fait, exponentiel) des algorithmes quantiques sur les algorithmes classiques, et c'est pourquoi le problème d'échantillonnage de Fourier récursif est moins souvent discuté. Il représente néanmoins un problème computationnel intéressant en lui-même.