El algoritmo Deutsch-Jozsa

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

Aquí tienes una descripción del circuito cuántico del algoritmo Deutsch-Jozsa. También puede ser necesario un paso clásico adicional de postprocesamiento, que no se muestra en la figura, dependiendo del problema específico que se esté resolviendo.

Por supuesto, no hemos discutido qué problemas resuelve este algoritmo; esto se hace en las dos secciones siguientes.

El problema Deutsch-Jozsa

Empezaremos con el problema de consulta que el algoritmo Deutsch-Jozsa pretendía resolver originalmente, que se conoce como el problema 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 obtener $0$ si $f$ es constante y $1$ si $f$ es equilibrado, lo que de nuevo 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$ .

Obsérvese que, cuando $n$ es mayor que $1,$ existen funciones de la forma $f:\Sigma^n \rightarrow \Sigma$ que no son ni constantes ni equilibradas. 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 Deutsch-Jozsa, simplemente no nos preocupamos por funciones como ésta, ya que se consideran entradas "no importantes". Es decir, para este problema tenemos la promesa de que $f$ es constante o equilibrado.

Deutsch-Jozsa problem

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

El algoritmo de Deutsch-Jozsa, con su única consulta, resuelve este problema en el siguiente sentido: si todos y cada uno de los resultados de la medición $n$ son $0,$ , entonces la función $f$ es constante; y, en caso contrario, si al menos uno de los resultados de la medición es $1,$ , entonces la función $f$ es equilibrada. Otra forma de expresarlo es que al circuito descrito anteriormente le sigue una etapa clásica de posprocesamiento en la que se calcula la operación OR de los resultados de las mediciones para obtener el bit de salida del problema de Deutsch-Jozsa.

Análisis de algoritmos

Para analizar el rendimiento del algoritmo Deutsch-Jozsa para el problema Deutsch-Jozsa, es útil empezar pensando en la acción de una sola capa de puertas Hadamard. Una operación Hadamard puede expresarse como una matriz de la forma 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 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,

lo que es cierto para ambas opciones de $a\in\Sigma.$

Supongamos ahora que en lugar de un único qubit tenemos $n$ qubits, y que se realiza una operación Hadamard en cada uno de ellos. La operación combinada en los qubits $n$ se describe mediante el producto tensorial $H\otimes \cdots \otimes H$ ( $n$ veces), que escribimos como $H^{\otimes n}$ para mayor concisión y claridad. Utilizando la fórmula anterior, expandiéndola y simplificándola, podemos expresar la acción de esta operación combinada sobre los estados base estándar de los qubits de $n$ 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}

Aquí, por cierto, estamos escribiendo cadenas binarias de longitud $n$ como $x_{n-1}\cdots x_0$ y $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. Una vez realizada la primera capa de puertas Hadamard, el estado de los qubits de $n+1$ (incluido el qubit más a la izquierda/abajo, que se trata por separado 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.

Cuando se realiza 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

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

A continuación, se ejecuta la segunda capa de puertas Hadamard, que (mediante 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 demasiado sobre las probabilidades de obtener diferentes resultados de medición sin saber más sobre la función $f.$

Afortunadamente, todo lo que necesitamos saber es la probabilidad de que cada uno de los resultados de la medición sea $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{if $f$ is constant}\\[1mm] 0 & \text{if $f$ is balanced} \end{cases}

Ten en cuenta que estos valores corresponden a la probabilidad de medir el estado $\vert 0^{\otimes n} \rangle$ , y no directamente al bit de salida clásico final del problema de Deutsch-Jozsa. El algoritmo devuelve « $0$ » cuando todos los resultados de las mediciones son « $0$ » (lo que indica que « $f$ » es constante) y, en caso contrario, devuelve « $1$ » (lo que indica que « $f$ » está en equilibrio).

Más en detalle, si $f$ es constante, entonces o bien $f(x_{n-1}\cdots x_0) = 0$ para cada cadena $x_{n-1}\cdots x_0,$ en cuyo caso el valor de la suma es $2^n,$ o $f(x_{n-1}\cdots x_0) = 1$ para cada cadena $x_{n-1}\cdots x_0,$ en cuyo caso el valor de la suma es $-2^n.$ Dividiendo por $2^n$ y tomando el cuadrado del valor absoluto se obtiene $1.$

Si, por el contrario, $f$ está equilibrada, 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 nos quedamos con el valor $0.$

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

Dificultad clásica

El algoritmo Deutsch-Jozsa funciona siempre, nos da siempre la respuesta correcta cuando se cumple la promesa y requiere una única consulta. ¿Qué diferencia hay con los algoritmos de consulta clásicos para el problema Deutsch-Jozsa?

En primer lugar, cualquier algoritmo clásico determinista que resuelva correctamente el problema Deutsch-Jozsa debe realizar exponencialmente muchas consultas: $2^{n-1} + 1$ en el peor de los casos. El razonamiento es que, si un algoritmo determinista consulta $f$ en $2^{n-1}$ o menos cadenas diferentes, y obtiene el mismo valor de función cada vez, entonces ambas respuestas siguen siendo posibles. La función puede ser constante o equilibrada, pero por mala suerte todas las consultas devuelven el mismo valor de función.

La segunda posibilidad puede parecer improbable, pero en los algoritmos deterministas no hay aleatoriedad ni incertidumbre, por lo que fallarán sistemáticamente en determinadas funciones. En este sentido, los algoritmos cuánticos tienen una ventaja significativa sobre los clásicos.

Sin embargo, hay un inconveniente: los algoritmos probabilísticos clásicos pueden resolver el problema Deutsch-Jozsa con una probabilidad muy alta utilizando sólo unas pocas consultas. En concreto, si simplemente elegimos unas cuantas cadenas diferentes de longitud $n$ al azar, y consultamos $f$ sobre esas cadenas, es poco probable que obtengamos el mismo valor de función para todas ellas cuando $f$ esté equilibrado.

En concreto, si elegimos $k$ cadenas de entrada $x^1,\ldots,x^k \in \Sigma^n$ uniformemente al azar, evaluamos $f(x^1),\ldots,f(x^k),$ y respondemos $0$ si los valores de la función son todos iguales, y $1$ en caso contrario, entonces siempre acertaremos cuando $f$ sea constante, y nos equivocaremos en el caso de que $f$ esté equilibrada con probabilidad justo $2^{-k + 1}.$ Si tomamos $k = 11,$ por ejemplo, este algoritmo responderá correctamente con probabilidad mayor que $99.9$ %.

Por esta razón, seguimos teniendo una ventaja bastante modesta de los algoritmos cuánticos sobre los clásicos, pero no deja de ser una ventaja cuantificable que representa una mejora con respecto al algoritmo de Deutsch.

Deutsch-Jozsa con Qiskit

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

Para implementar el algoritmo Deutsch-Jozsa en Qiskit, empezaremos 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 satisface la promesa para el problema Deutsch-Jozsa. Con un 50% de probabilidad, la función es constante, y con un 50% de cambio, la función está equilibrada. Para cada una de esas dos posibilidades, la función se selecciona uniformemente 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 mostrar la implementación del circuito cuántico de la puerta de consulta utilizando el método draw como de costumbre.

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

Output:

A continuación definimos una función que crea el circuito Deutsch-Jozsa, tomando como argumento una implementación de circuito cuántico de 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 una vez el circuito Deutsch-Jozsa.

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 al azar, mostrando la implementación del circuito cuántico de una puerta de consulta para esta función y, a continuación, ejecutando el algoritmo Deutsch-Jozsa en esa función.

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

Output:

'balanced'

El problema de Bernstein-Vazirani

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

En primer lugar, introduzcamos algo de notación. Para dos cadenas binarias cualesquiera $x = x_{n-1} \cdots x_0$ y $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.

Nos referiremos a esta operación como el producto punto binario. Una forma alternativa de definirlo es así.

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}

Observe que se trata de una operación simétrica, lo que significa que el resultado no cambia si intercambiamos $x$ y $y,$ , por lo que somos libres de hacerlo cuando nos convenga. A veces es útil pensar en el producto binario por puntos $x \cdot y$ como la paridad de los bits de $x$ en las posiciones en las que la cadena $y$ tiene un $1,$ o, equivalentemente, la paridad de los bits de $y$ en las posiciones en las que la cadena $x$ tiene un $1.$

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

Bernstein-Vazirani problem

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 cual $f(x) = s\cdot x$ para todas $x\in\Sigma^n$ \ Salida: la cadena $s$

En realidad no necesitamos un nuevo algoritmo cuántico para este problema; el algoritmo Deutsch-Jozsa lo resuelve. En aras de la claridad, vamos a referirnos al circuito cuántico de arriba, que no incluye el paso de post-procesamiento clásico de calcular el OR, como el circuito Deutsch-Jozsa.

Análisis de algoritmos

Para analizar cómo funciona el circuito Deutsch-Jozsa para una función que satisface la promesa para el problema Bernstein-Vazirani, empezaremos con una rápida observación. Utilizando el producto punto binario, podemos describir alternativamente la acción de $n$ puertas Hadamard sobre los estados base estándar de $n$ qubits como sigue.

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$ sólo depende de si $k$ es par o impar.

Volviendo al circuito Deutsch-Jozsa, una vez realizada la primera capa de compuertas Hadamard, el estado de los qubits de $n+1$ es

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

A continuación, se ejecuta la puerta de consulta, que (a través del 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.

Utilizando nuestra fórmula para la acción de una capa de puertas Hadamard, vemos que la segunda capa de puertas Hadamard transforma entonces 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 sustituir la suma por el OR exclusivo, de nuevo porque lo único que importa para un número 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 en realidad no son necesarios porque es convencional tratar el producto binario por puntos como si tuviera mayor precedencia que el exclusivo-OR)

En este punto utilizaremos la siguiente fórmula.

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

Podemos obtener la fórmula mediante una fórmula similar para los bits,

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

junto con una expansión del producto binario por puntos y de la función bitwise exclusive-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}

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

\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 consiste en utilizar otra fórmula, que funciona para todas las cadenas binarias $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}

Aquí estamos utilizando una notación simple para cadenas que utilizaremos varias veces más en la lección: $0^n$ es la cadena completamente nula de longitud $n.$

Una forma sencilla de argumentar que esta fórmula funciona es considerar los dos casos por separado. Si $z = 0^n,$ entonces $z\cdot x = 0$ para cada cadena $x\in\Sigma^n,$ por lo que el valor de cada término en la suma es $1,$ y obtenemos $1$ sumando y dividiendo por $2^n.$ Por otra parte, si cualquiera de los bits de $z$ es igual a $1,$ entonces el producto binario de puntos $z\cdot x$ es igual a $0$ para exactamente la mitad de las posibles opciones para $x\in\Sigma^n$ y $1$ para la otra mitad - porque el valor del producto binario de puntos $z\cdot x$ se voltea (de $0$ a $1$ o de $1$ a $0$ ) si volteamos 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 medidas, 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,

debido a que $s\oplus y = 0^n$ si y sólo si $y = s.$ Así pues, las mediciones revelan precisamente la cadena $s$ que buscamos.

Dificultad clásica

Mientras que el circuito Deutsch-Jozsa resuelve el problema 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 el llamado argumento de la teoría de la información, que es muy sencillo en este caso. Cada consulta clásica revela un único bit de información sobre la solución, y hay $n$ bits de información que deben ser descubiertos - por lo que se necesitan al menos $n$ consultas.

De hecho, es posible resolver el problema Bernstein-Vazirani de forma clásica consultando la función en cada una de las cadenas $n$ que tienen un único $1,$ en cada posición posible, y $0$ para 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 $1$ consultas frente a $n$ consultas.

Bernstein-Vazirani con Qiskit

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

Output:

Ahora podemos crear una función que ejecute el circuito Deutsch-Jozsa en la función, utilizando 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")))

Output:

'1011'

Observación sobre la nomenclatura

En el contexto del problema Bernstein-Vazirani, es habitual que se haga referencia al algoritmo Deutsch-Jozsa como "algoritmo Bernstein-Vazirani" Esto es ligeramente engañoso, porque el algoritmo es el algoritmo Deutsch-Jozsa, como Bernstein y Vazirani dejaron muy claro en su trabajo.

Lo que hicieron Bernstein y Vazirani después de demostrar que el algoritmo Deutsch-Jozsa resuelve el problema Bernstein-Vazirani (como se ha indicado anteriormente) fue definir un problema mucho más complicado, conocido como el problema de muestreo recursivo de Fourier. Se trata de un problema muy elaborado en el que las soluciones a diferentes instancias del problema desbloquean nuevos niveles del problema dispuestos en una estructura arborescente. El problema Bernstein-Vazirani es esencialmente sólo el caso base de este problema más complicado.

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

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

El problema de Simon, y el algoritmo para él descrito en la siguiente sección, proporciona un ejemplo mucho más simple de una ventaja superpolinómica (y, de hecho, exponencial) de los algoritmos cuánticos sobre los clásicos, y por esta razón el problema de muestreo recursivo de Fourier se discute con menos frecuencia. No obstante, es un problema computacional interesante por derecho propio.

¿Le ha resultado útil esta página?

Informe de un error, de una errata o solicite contenido en GitHub.