El algoritmo de Deutsch-Jozsa

El algoritmo de Deutsch supera a todos los algoritmos clásicos para un problema de consultas, pero la ventaja es bastante modesta: una consulta frente a dos. El algoritmo de Deutsch-Jozsa amplía esta ventaja — y, de hecho, puede usarse para resolver un par de problemas de consultas distintos.

A continuación se muestra una descripción del algoritmo de Deutsch-Jozsa en forma de circuito cuántico. También puede ser necesario un paso adicional de posprocesamiento clásico, no mostrado en la figura, dependiendo del problema específico que se resuelva.

Por supuesto, todavía no hemos explicado qué problemas resuelve este algoritmo; eso se hace en las dos secciones siguientes.

El problema de Deutsch-Jozsa

Comenzaremos con el problema de consultas que el algoritmo de Deutsch-Jozsa fue diseñado originalmente para resolver, conocido como el problema de Deutsch-Jozsa.

La función de entrada para este problema tiene la forma $f:\Sigma^n \rightarrow \Sigma$ para un entero positivo arbitrario $n.$ Al igual que en el problema de Deutsch, la tarea consiste en devolver $0$ si $f$ es constante y $1$ si $f$ es balanceada, lo que significa que el número de cadenas de entrada en las que la función toma el valor $0$ es igual al número de cadenas de entrada en las que la función toma el valor $1$.

Observa que, cuando $n$ es mayor que $1,$ existen funciones de la forma $f:\Sigma^n \rightarrow \Sigma$ que no son ni constantes ni balanceadas. Por ejemplo, la función $f:\Sigma^2\rightarrow\Sigma$ definida como

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

no pertenece a ninguna de estas dos categorías. Para el problema de Deutsch-Jozsa, simplemente ignoramos funciones como esta — se consideran entradas "irrelevantes". Es decir, para este problema tenemos la promesa de que $f$ es constante o balanceada.

Problema de Deutsch-Jozsa

Entrada: una función $f:\{0,1\}^n\rightarrow\{0,1\}$
Promesa: $f$ es constante o balanceada
Salida: $0$ si $f$ es constante, $1$ si $f$ es balanceada

El algoritmo de Deutsch-Jozsa, con su única consulta, resuelve este problema en el siguiente sentido: si todos y cada uno de los $n$ resultados de medición son $0,$ entonces la función $f$ es constante; de lo contrario, si al menos uno de los resultados de medición es $1,$ entonces la función $f$ es balanceada. Otra forma de expresarlo es que el circuito descrito anteriormente va seguido de un paso de posprocesamiento clásico en el que se calcula el OR de los resultados de medición para producir la salida.

Análisis del algoritmo

Para analizar el rendimiento del algoritmo de Deutsch-Jozsa aplicado al problema de Deutsch-Jozsa, conviene comenzar pensando en la acción de una sola capa de puertas Hadamard. Una operación Hadamard puede expresarse como una matriz de la manera habitual,

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

pero también podemos expresar esta operación en términos de su acción sobre los estados de la base estándar:

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

Estas dos ecuaciones pueden combinarse en una sola fórmula,

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

que es válida para ambas opciones de $a\in\Sigma.$

Supongamos ahora que, en lugar de un solo qubit, tenemos $n$ qubits y se aplica una operación Hadamard a cada uno. La operación combinada sobre los $n$ qubits se describe mediante el producto tensorial $H\otimes \cdots \otimes H$ ($n$ veces), que escribimos como $H^{\otimes n}$ por concisión y claridad. Usando la fórmula anterior, y luego expandiendo y simplificando, podemos expresar la acción de esta operación combinada sobre los estados de la base estándar de $n$ qubits de la siguiente manera:

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

Nótese que aquí escribimos cadenas binarias de longitud $n$ como $x_{n-1}\cdots x_0$ e $y_{n-1}\cdots y_0,$ siguiendo la convención de indexación de Qiskit.

Esta fórmula nos proporciona una herramienta útil para analizar el circuito cuántico anterior. Tras aplicar la primera capa de puertas Hadamard, el estado de los $n+1$ qubits (incluido el qubit más a la izquierda/inferior, que se trata de forma independiente del resto) es

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

Al aplicar la operación $U_f$, este estado se transforma 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$$

exactamente mediante el mismo fenómeno de retroceso de fase que vimos en el análisis del algoritmo de Deutsch.

A continuación se aplica la segunda capa de puertas Hadamard, que (según la fórmula anterior) transforma este estado 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.$$

Esta expresión parece algo complicada, y no se puede concluir mucho sobre las probabilidades de obtener distintos resultados de medición sin conocer más sobre la función $f.$

Afortunadamente, lo único que necesitamos saber es la probabilidad de que todos los resultados de medición sean $0$ — porque esa es la probabilidad de que el algoritmo determine que $f$ es constante. Esta probabilidad tiene una fórmula sencilla.

$$\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{si $f$ es constante}\\[1mm] 0 & \text{si $f$ es balanceada} \end{cases}$$

En detalle, si $f$ es constante, entonces o bien $f(x_{n-1}\cdots x_0) = 0$ para toda cadena $x_{n-1}\cdots x_0,$ en cuyo caso el valor de la suma es $2^n,$ o bien $f(x_{n-1}\cdots x_0) = 1$ para toda cadena $x_{n-1}\cdots x_0,$ en cuyo caso el valor de la suma es $-2^n.$ Al dividir por $2^n$ y tomar el cuadrado del valor absoluto obtenemos $1.$

Si, por otro lado, $f$ es balanceada, entonces $f$ toma el valor $0$ en la mitad de las cadenas $x_{n-1}\cdots x_0$ y el valor $1$ en la otra mitad, por lo que los términos $+1$ y $-1$ de la suma se cancelan y obtenemos el valor $0.$

Concluimos que el algoritmo opera correctamente siempre que se cumpla la promesa.

Dificultad clásica

El algoritmo de Deutsch-Jozsa funciona en todo momento, siempre proporciona la respuesta correcta cuando se cumple la promesa y requiere una única consulta. ¿Cómo se compara esto con los algoritmos de consultas clásicos para el problema de Deutsch-Jozsa?

En primer lugar, cualquier algoritmo clásico determinista que resuelva correctamente el problema de Deutsch-Jozsa debe realizar un número exponencial de consultas: se necesitan $2^{n-1} + 1$ consultas en el peor caso. El razonamiento es que, si un algoritmo determinista consulta $f$ en $2^{n-1}$ o menos cadenas distintas y obtiene el mismo valor de la función en todas ellas, ambas respuestas siguen siendo posibles. La función podría ser constante, o podría ser balanceada pero con mala suerte todas las consultas devuelven el mismo valor de la función.

La segunda posibilidad puede parecer improbable — pero para los algoritmos deterministas no hay aleatoriedad ni incertidumbre, por lo que fallarán sistemáticamente en ciertas funciones. Por lo tanto, tenemos una ventaja significativa de los algoritmos cuánticos sobre los clásicos en este sentido.

Existe, sin embargo, una salvedad: los algoritmos clásicos probabilistas pueden resolver el problema de Deutsch-Jozsa con alta probabilidad usando solo unas pocas consultas. En particular, si simplemente elegimos unas pocas cadenas distintas de longitud $n$ al azar y consultamos $f$ en esas cadenas, es poco probable que obtengamos el mismo valor de la función para todas ellas cuando $f$ es balanceada.

Más concretamente, si elegimos $k$ cadenas de entrada $x^1,\ldots,x^k \in \Sigma^n$ de manera uniforme aleatoria, evaluamos $f(x^1),\ldots,f(x^k),$ y respondemos $0$ si todos los valores de la función son iguales y $1$ si no, siempre acertaremos cuando $f$ es constante, y nos equivocaremos en el caso de que $f$ sea balanceada con probabilidad solo $2^{-k + 1}.$ Si tomamos $k = 11,$ por ejemplo, este algoritmo responderá correctamente con probabilidad superior al $99{,}9$%.

Por esta razón, seguimos teniendo una ventaja más bien modesta de los algoritmos cuánticos sobre los clásicos — pero es, no obstante, una ventaja cuantificable que representa una mejora respecto al algoritmo de 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

Para implementar el algoritmo de Deutsch-Jozsa en Qiskit, comenzaremos definiendo una función dj_query que genera un circuito cuántico que implementa una puerta de consulta, para una función seleccionada aleatoriamente que satisfaga la promesa del problema de Deutsch-Jozsa. Con un 50% de probabilidad la función es constante, y con un 50% la función es balanceada. Para cada una de estas dos posibilidades, la función se selecciona de manera uniforme entre las funciones de ese tipo. El argumento es el número de bits de entrada de la función.

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

Podemos visualizar la implementación en circuito cuántico de la puerta de consulta usando el método draw como de costumbre.

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

A continuación definimos una función que crea el circuito de Deutsch-Jozsa, tomando como argumento un circuito cuántico que implementa una puerta de consulta.

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

Por último, se define una función que ejecuta el circuito de Deutsch-Jozsa una sola vez.

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"

Podemos probar nuestra implementación eligiendo una función aleatoriamente, mostrando la implementación en circuito cuántico de una puerta de consulta para dicha función y ejecutando el algoritmo de Deutsch-Jozsa sobre esa función.

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

'balanced'

El problema de Bernstein-Vazirani

A continuación, hablaremos de un problema conocido como el problema de Bernstein-Vazirani. También se llama problema de muestreo de Fourier, aunque existen formulaciones más generales de este problema que también llevan ese nombre.

Primero, introduzcamos algo de notación. Para cualesquiera dos cadenas binarias $x = x_{n-1} \cdots x_0$ e $y = y_{n-1}\cdots y_0$ de longitud $n,$ definimos

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

Llamaremos a esta operación el producto punto binario. Una forma alternativa de definirlo es la siguiente.

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

Observa que esta es una operación simétrica, lo que significa que el resultado no cambia si intercambiamos $x$ e $y,$ así que podemos hacerlo cuando nos resulte conveniente. A veces es útil pensar en el producto punto binario $x \cdot y$ como la paridad de los bits de $x$ en las posiciones donde la cadena $y$ tiene un $1,$ o de forma equivalente, la paridad de los bits de $y$ en las posiciones donde la cadena $x$ tiene un $1.$

Con esta notación ya podemos definir el problema de Bernstein-Vazirani.

Problema de Bernstein-Vazirani

Entrada: una función $f:\{0,1\}^n\rightarrow\{0,1\}$
Promesa: existe una cadena binaria $s = s_{n-1} \cdots s_0$ para la que $f(x) = s\cdot x$ para todo $x\in\Sigma^n$
Salida: la cadena $s$

En realidad no necesitamos un nuevo algoritmo cuántico para este problema; el algoritmo de Deutsch-Jozsa lo resuelve. Para mayor claridad, llamemos circuito de Deutsch-Jozsa al circuito cuántico descrito anteriormente, que no incluye el paso de posprocesamiento clásico de calcular la OR.

Análisis del algoritmo

Para analizar cómo funciona el circuito de Deutsch-Jozsa con una función que satisface la promesa del problema de Bernstein-Vazirani, comenzaremos con una observación rápida. Usando el producto punto binario, podemos describir de forma alternativa la acción de $n$ puertas Hadamard sobre los estados de la base estándar de $n$ qubits así:

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

De forma similar a lo que vimos al analizar el algoritmo de Deutsch, esto se debe a que el valor $(-1)^k$ para cualquier entero $k$ depende únicamente de si $k$ es par o impar.

Volviendo al circuito de Deutsch-Jozsa, después de que se aplica la primera capa de puertas Hadamard, el estado de los $n+1$ qubits es

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

A continuación se aplica la puerta de consulta, que (mediante el fenómeno de retroceso de fase) transforma el estado en

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

Usando nuestra fórmula para la acción de una capa de puertas Hadamard, vemos que la segunda capa de puertas Hadamard transforma este estado 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.$$

Ahora podemos hacer algunas simplificaciones en el exponente de $-1$ dentro de la suma. Se nos promete que $f(x) = s\cdot x$ para alguna cadena $s = s_{n-1} \cdots s_0,$ por lo que podemos expresar el estado como

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

Dado que $s\cdot x$ y $x\cdot y$ son valores binarios, podemos reemplazar la suma por la OR exclusiva — de nuevo porque lo único que importa para un entero en el exponente de $-1$ es si es par o impar. Haciendo uso de la simetría del producto punto binario, obtenemos esta expresión para el estado:

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

(Se han añadido paréntesis para mayor claridad, aunque no son estrictamente necesarios porque por convención el producto punto binario tiene mayor precedencia que la OR exclusiva.)

En este punto haremos uso de la siguiente fórmula.

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

Podemos obtener la fórmula a partir de una fórmula análoga para bits,

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

junto con una expansión del producto punto binario y la OR exclusiva 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}$$

Esto nos permite expresar el estado del circuito justo antes de las mediciones así:

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

El último paso es hacer uso de otra fórmula más, que es válida para toda cadena 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{si $z = 0^n$}\\ 0 & \text{si $z\neq 0^n$} \end{cases}$$

Aquí usamos una notación sencilla para cadenas que utilizaremos varias veces más en la lección: $0^n$ es la cadena de todos ceros de longitud $n.$

Una forma simple de argumentar que esta fórmula es correcta es considerar los dos casos por separado. Si $z = 0^n,$ entonces $z\cdot x = 0$ para toda cadena $x\in\Sigma^n,$ por lo que el valor de cada término de la suma es $1,$ y al sumar y dividir entre $2^n$ obtenemos $1.$ Por otro lado, si alguno de los bits de $z$ es igual a $1,$ entonces el producto punto binario $z\cdot x$ es igual a $0$ para exactamente la mitad de las posibles elecciones de $x\in\Sigma^n$ e igual a $1$ para la otra mitad — porque el valor del producto punto binario $z\cdot x$ cambia (de $0$ a $1$ o de $1$ a $0$) si invertimos cualquier bit de $x$ en una posición donde $z$ tiene un $1.$

Si ahora aplicamos esta fórmula para simplificar el estado del circuito antes de las mediciones, obtenemos

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

dado que $s\oplus y = 0^n$ si y solo si $y = s.$ Así, las mediciones revelan exactamente la cadena $s$ que buscamos.

Dificultad clásica

Mientras que el circuito de Deutsch-Jozsa resuelve el problema de Bernstein-Vazirani con una sola consulta, cualquier algoritmo de consulta clásico debe realizar al menos $n$ consultas para resolver este problema.

Esto puede razonarse mediante un argumento denominado teórico-informacional, que es muy sencillo en este caso. Cada consulta clásica revela un solo bit de información sobre la solución, y hay $n$ bits de información que deben descubrirse — por lo tanto, se necesitan al menos $n$ consultas.

De hecho, es posible resolver el problema de Bernstein-Vazirani de forma clásica consultando la función en cada una de las $n$ cadenas que tienen un único $1$ en cada posición posible y $0$ en todos los demás bits, lo que revela los bits de $s$ de uno en uno. Por lo tanto, la ventaja de los algoritmos cuánticos sobre los clásicos para este problema es de $1$ consulta frente a $n$ consultas.

Bernstein-Vazirani con Qiskit

Ya hemos implementado el circuito de Deutsch-Jozsa anteriormente, y aquí lo usaremos para resolver el problema de Bernstein-Vazirani. Primero definiremos una función que implementa una puerta de consulta para el problema de Bernstein-Vazirani dada cualquier cadena 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"))

Ahora podemos crear una función que ejecute el circuito de Deutsch-Jozsa sobre la función, usando la función compile_circuit que se definió anteriormente.

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'

Observación sobre la nomenclatura

En el contexto del problema de Bernstein-Vazirani, es habitual que el algoritmo de Deutsch-Jozsa se denomine "algoritmo de Bernstein-Vazirani." Esto es algo engañoso, porque el algoritmo es el algoritmo de Deutsch-Jozsa, tal y como Bernstein y Vazirani dejaron muy claro en su trabajo.

Lo que hicieron Bernstein y Vazirani tras demostrar que el algoritmo de Deutsch-Jozsa resuelve el problema de Bernstein-Vazirani (tal como se enuncia más arriba) fue definir un problema mucho más complicado, conocido como el problema de muestreo de Fourier recursivo. Se trata de un problema muy artificial en el que las soluciones a diferentes instancias del problema desbloquean efectivamente nuevos niveles del problema, organizados en una estructura de árbol. El problema de Bernstein-Vazirani es esencialmente el caso base de este problema más complicado.

El problema de muestreo de Fourier recursivo fue el primer ejemplo conocido de un problema de consulta en el que los algoritmos cuánticos tienen una ventaja llamada superpolinomial sobre los algoritmos probabilísticos, superando así la ventaja cuántica sobre la clásica que ofrece el algoritmo de Deutsch-Jozsa. Intuitivamente, la versión recursiva del problema amplifica la ventaja de $1$ frente a $n$ de los algoritmos cuánticos hasta algo mucho mayor.

El aspecto más desafiante del análisis matemático que establece esta ventaja es demostrar que los algoritmos de consulta clásicos no pueden resolver el problema sin realizar muchas consultas. Esto es bastante típico; para muchos problemas puede ser muy difícil descartar enfoques clásicos creativos que los resuelvan de manera eficiente.

El problema de Simon, y el algoritmo para resolverlo descrito en la siguiente sección, sí proporciona un ejemplo mucho más sencillo de una ventaja superpolinomial (y, de hecho, exponencial) de los algoritmos cuánticos sobre los clásicos, por lo que el problema de muestreo de Fourier recursivo se discute con menos frecuencia. No obstante, sigue siendo un problema computacional interesante por derecho propio.