El algoritmo Deutsch-Jozsa

Para este módulo de Qiskit en las aulas, los estudiantes deben tener un entorno Python en funcionamiento con los siguientes paquetes instalados:

• qiskit v2.1.0 o más reciente
• qiskit-ibm-runtime v0.40.1 o más reciente
• qiskit-aer v0.17.0 o más reciente
• qiskit.visualization
• numpy
• pylatexenc

Para configurar e instalar los paquetes anteriores, consulta la guía Instalar Qiskit. Para ejecutar trabajos en ordenadores cuánticos reales, los estudiantes deberán crear una cuenta en IBM Quantum® siguiendo los pasos de la guía Configure su cuenta IBM Cloud.

Este módulo fue probado y utilizó cuatro segundos de tiempo QPU. Esto es sólo una estimación. Su uso real puede variar.

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

Vea el tutorial del módulo de la Dra. Katie McCormick a continuación, o haga clic aquí para verlo en YouTube.

Intro

A principios de los años 80, los físicos cuánticos y los informáticos tenían la vaga idea de que la mecánica cuántica podía aprovecharse para realizar cálculos mucho más potentes que los de los ordenadores clásicos. Su razonamiento era el siguiente: es difícil para un ordenador clásico simular sistemas cuánticos, pero un ordenador cuántico debería ser capaz de hacerlo de forma más eficiente. Y si un ordenador cuántico podía simular sistemas cuánticos de forma más eficiente, quizá hubiera otras tareas que pudiera realizar de forma más eficiente que un ordenador clásico.

La lógica era sólida, pero quedaban por concretar los detalles. Esto empezó en 1985, cuando David Deutsch describió el primer "ordenador cuántico universal" En este mismo artículo, proporcionó el primer ejemplo de problema para el que un ordenador cuántico podía resolver algo de forma más eficiente que un ordenador clásico. Este primer ejemplo de juguete se conoce ahora como "algoritmo de Deutsch" La mejora del algoritmo de Deutsch fue modesta, pero Deutsch trabajó con Richard Jozsa unos años más tarde para ampliar aún más la brecha entre los ordenadores clásicos y los cuánticos.

Estos algoritmos -el de Deutsch y la extensión Deutsch-Jozsa- no son especialmente útiles, pero siguen siendo muy importantes por varias razones:

1. Históricamente, fueron algunos de los primeros algoritmos cuánticos que demostraron superar a sus homólogos clásicos. Comprenderlos puede ayudarnos a entender cómo ha evolucionado el pensamiento de la comunidad sobre la computación cuántica a lo largo del tiempo.
2. Pueden ayudarnos a comprender algunos aspectos de la respuesta a una pregunta sorprendentemente sutil: ¿Qué confiere a la informática cuántica su potencia? A veces, los ordenadores cuánticos se comparan con procesadores paralelos gigantes de escala exponencial. Pero esto no es del todo correcto. Aunque una parte de la respuesta a esta pregunta reside en el llamado "paralelismo cuántico", extraer la máxima información posible en una sola ejecución es un arte sutil. Los algoritmos Deutsch y Deutsch-Jozsa muestran cómo hacerlo.

En este módulo aprenderemos sobre el algoritmo de Deutsch, el algoritmo de Deutsch-Jozsa y lo que nos enseñan sobre el poder de la computación cuántica.

El paralelismo cuántico y sus límites

Parte de la potencia de la computación cuántica se deriva del "paralelismo cuántico" que es esencialmente la capacidad de realizar operaciones en múltiples entradas al mismo tiempo, ya que los estados de entrada del qubit podrían estar en una superposición de múltiples estados permitidos clásicamente. SIN EMBARGO, aunque un circuito cuántico podría ser capaz de evaluar múltiples estados de entrada a la vez, extraer toda esa información de una sola vez es imposible.

Para ver a qué me refiero, supongamos que tenemos un bit, $x$ y una función aplicada a ese bit, $f(x)$. Hay cuatro posibles funciones binarias que llevan un único bit a otro único bit:

Nos gustaría saber cuál de estas funciones (1-4) es nuestra $f(x)$. Clásicamente, tendríamos que ejecutar la función dos veces - una para $x=0$, otra para $x=1$. Pero veamos si podemos hacerlo mejor con un circuito cuántico. Podemos conocer la función con la siguiente puerta:

Aquí, la puerta $U_f$ calcula $f(x)$, donde $x$ es el estado del qubit 0, y lo aplica al qubit 1. Así, el estado resultante, $|x\rangle|y\oplus f(x)\rangle$, simplemente se convierte en $|x\rangle|f(x)\rangle$ cuando $|y\rangle = |0\rangle$. Esto contiene toda la información que necesitamos para conocer la función $f(x)$ : el qubit 0 nos dice qué es $x$, y el qubit 1 nos dice qué es $f(x)$. Así, si inicializamos $|x\rangle = \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$, entonces el estado final de ambos qubits será: $|y\rangle|x\rangle = \frac{1}{\sqrt{2}}(|f(0)\rangle|0\rangle+|f(1)\rangle|1\rangle)$. Pero, ¿cómo accedemos a esa información?

2.1. Pruébalo en Qiskit:

Utilizando Qiskit seleccionaremos al azar una de las cuatro funciones posibles anteriores y ejecutaremos el circuito. A continuación, su tarea consiste en utilizar las mediciones del circuito cuántico para aprender la función en el menor número de ejecuciones posible.

En este primer experimento y a lo largo de todo el módulo, utilizaremos un marco para la computación cuántica conocido como "patrones Qiskit", que divide los flujos de trabajo en los siguientes pasos:

• Paso 1: Asignar entradas clásicas a un problema cuántico
• Paso 2: Optimizar el problema para la ejecución cuántica
• Paso 3: Ejecutar utilizando Qiskit Runtime Primitives
• Etapa 4: Tratamiento posterior y análisis clásico

Empecemos cargando algunos paquetes necesarios, incluidas las primitivas Qiskit Runtime. También seleccionaremos el ordenador cuántico menos ocupado de que dispongamos.

A continuación encontrará un código para guardar sus credenciales la primera vez que las utilice. Asegúrate de borrar esta información del cuaderno después de guardarlo en tu entorno, para que tus credenciales no se compartan accidentalmente cuando compartas el cuaderno. Consulte Configurar su cuenta IBM Cloud e Inicializar el servicio en un entorno no fiable para obtener más orientación.

# Load the Qiskit Runtime service
from qiskit_ibm_runtime import QiskitRuntimeService
 
# Load the Runtime primitive and session
from qiskit_ibm_runtime import SamplerV2 as Sampler
 
# Syntax for first saving your token.  Delete these lines after saving your credentials.
# QiskitRuntimeService.save_account(channel='ibm_quantum_platform', instance = '<YOUR_IBM_INSTANCE_CRN>', token='<YOUR_API_KEY>', overwrite=True, set_as_default=True)
# service = QiskitRuntimeService(channel='ibm_quantum_platform')
 
# Load saved credentials
service = QiskitRuntimeService()
 
# Use the least busy backend, or uncomment the loading of a specific backend like "ibm_brisbane".
# backend = service.least_busy(operational=True, simulator=False, min_num_qubits = 127)
backend = service.backend("ibm_brisbane")
print(backend.name)
 
 
sampler = Sampler(mode=backend)

Output:

ibm_brisbane

La celda de abajo te permitirá cambiar entre usar el simulador o el hardware real a lo largo del cuaderno. Recomendamos ejecutarlo ahora:

# Load the backend sampler
from qiskit.primitives import BackendSamplerV2
 
# Load the Aer simulator and generate a noise model based on the currently-selected backend.
from qiskit_aer import AerSimulator
from qiskit_aer.noise import NoiseModel
 
# Alternatively, load a fake backend with generic properties and define a simulator.
 
 
noise_model = NoiseModel.from_backend(backend)
 
# Define a simulator using Aer, and use it in Sampler.
backend_sim = AerSimulator(noise_model=noise_model)
sampler_sim = BackendSamplerV2(backend=backend_sim)
 
# You could also define a simulator-based sampler using a generic backend:
# backend_gen = GenericBackendV2(num_qubits=18)
# sampler_gen = BackendSamplerV2(backend=backend_gen)

Ahora que hemos cargado los paquetes necesarios, podemos proceder con el flujo de trabajo de los patrones Qiskit. En el siguiente paso de mapeo, primero hacemos una función que selecciona entre las cuatro posibles funciones que llevan un único bit a otro único bit.

# Step 1: Map
 
from qiskit import QuantumCircuit
 
qc = QuantumCircuit(2)
 
 
def twobit_function(case: int):
    """
    Generate a valid two-bit function as a `QuantumCircuit`.
    """
    if case not in [1, 2, 3, 4]:
        raise ValueError("`case` must be 1, 2, 3, or 4.")
 
    f = QuantumCircuit(2)
    if case in [2, 3]:
        f.cx(0, 1)
    if case in [3, 4]:
        f.x(1)
    return f
 
 
# first, convert oracle circuit (above) to a single gate for drawing purposes. otherwise, the circuit is too large to display
# blackbox = twobit_function(2).to_gate()  # you may edit the number inside "twobit_function()" to select among the four valid functions
# blackbox.label = "$U_f$"
 
qc.h(0)
qc.barrier()
qc.compose(twobit_function(2), inplace=True)
qc.measure_all()
 
 
qc.draw("mpl")

Output:

En el circuito anterior, la puerta Hadamard "H" lleva el qubit 0, que se encuentra inicialmente en el estado $|0\rangle$, al estado de superposición $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$. A continuación, $U_f$ evalúa la función $f(x)$ y la aplica al qubit 1.

A continuación tenemos que optimizar y transpilar el circuito para que funcione en el ordenador cuántico:

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager
 
target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
 
qc_isa = pm.run(qc)

Por último, ejecutamos nuestro circuito transpilado en el ordenador cuántico y visualizamos nuestros resultados:

# Step 3: Run the job on a real quantum computer
 
job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.meas.get_counts()

# Step 4: Visualize and analyze results
 
## Analysis
from qiskit.visualization import plot_histogram
 
plot_histogram(counts)

Output:

Arriba se muestra un histograma de nuestros resultados. Dependiendo del número de disparos que elijas para ejecutar el circuito en el paso 3 anterior, podrías ver una o dos barras, representando los estados medidos de los dos qubits en cada disparo. Como siempre con Qiskit y en este cuaderno, utilizamos notación "little endian", lo que significa que los estados de los qubits 0 a n se escriben en orden ascendente de derecha a izquierda, por lo que el qubit 0 siempre está más a la derecha.

Así, como el qubit 0 estaba en un estado de superposición, el circuito evaluó la función tanto para $x=0$ como para $x=1$ al mismo tiempo, ¡algo que los ordenadores clásicos no pueden hacer! Pero la trampa viene cuando queremos aprender sobre la función $f(x)$ - cuando medimos los qubits, colapsamos su estado. Si selecciona "disparos = 1" para ejecutar el circuito una sola vez, sólo verá una barra en el histograma de arriba, y su información sobre la función estará incompleta.

Compruebe su comprensión

Lee las preguntas siguientes, piensa tu respuesta y haz clic en el triángulo para descubrir la solución.

Así pues, aunque el paralelismo cuántico puede ser potente si se utiliza de la forma adecuada, no es correcto afirmar que un ordenador cuántico funciona igual que un procesador paralelo masivo clásico. El acto de medir colapsa los estados cuánticos, por lo que sólo podemos acceder a un único resultado del cálculo.

Algoritmo de Deutsch

Aunque el paralelismo cuántico por sí solo no nos da ventaja sobre los ordenadores clásicos, podemos combinarlo con otro fenómeno cuántico, la interferencia, para conseguir una mayor velocidad. El algoritmo ahora conocido como "algoritmo de Deutsch" es el primer ejemplo de un algoritmo que logra esto.

El problema

Aquí estaba el problema:

Dado un bit de entrada, $x = \{0,1\}$, y una función de entrada $f(x) = \{0,1\}$, determine si la función es equilibrada o constante. Es decir, si está equilibrada, la salida de la función es 0 la mitad del tiempo y 1 la otra mitad. Si es constante, entonces la salida de la función es siempre 0 o siempre 1. Recordemos la tabla de las cuatro funciones posibles que llevan un único bit a otro único bit:

La primera y la última función, $f_1(x)$ y $f_4(x)$, son constantes, mientras que las dos del medio, $f_2(x)$ y $f_3(x)$, están equilibradas.

El algoritmo

La forma en que Deutsch abordó este problema fue a través del "modelo de consulta" En el modelo de consulta, la función de entrada ( $f_i(x)$ arriba) está contenida en una "caja negra" - no tenemos acceso directo a su contenido, pero podemos consultar la caja negra y nos dará la salida de la función. A veces decimos que un "oráculo" proporciona esta información. Ver Lección 1: Algoritmos Cuánticos de Consulta del curso Fundamentos de Algoritmos Cuánticos para más información sobre el modelo de consulta.

Para determinar si un algoritmo cuántico es más eficiente que un algoritmo clásico en el modelo de consulta, podemos simplemente comparar el número de consultas que necesitamos hacer a la caja negra en cada caso. En el caso clásico, para saber si la función contenida en la caja negra era equilibrada o constante, tendríamos que consultar la caja dos veces para obtener tanto $f(0)$ como $f(1)$.

Sin embargo, el algoritmo cuántico de Deutsch encontró la forma de obtener la información con una sola consulta Hizo un ajuste en el circuito de "paralelismo cuántico" anterior, de modo que preparó un estado de superposición en ambos qubits, en lugar de sólo en el qubit 0. Entonces las dos salidas de la función, $f(0)$ y $f(1)$ interferían para devolver 0 si eran ambas 0 o ambas 1 (la función era constante), y devolvían 1 si eran diferentes (la función era equilibrada). De este modo, Deutsch podía diferenciar entre una constante y una función equilibrada con una sola consulta.

Aquí tienes un esquema del algoritmo de Deutsch:

Para entender cómo funciona este algoritmo, observemos los estados cuánticos de los qubits en los tres puntos señalados en el diagrama anterior. Intenta resolver los estados por ti mismo antes de hacer clic para ver las respuestas:

Compruebe su comprensión

Lee las preguntas siguientes, piensa tus respuestas y haz clic en los triángulos para descubrir las soluciones.

Al repasar tus respuestas a las preguntas anteriores, observa que ocurre algo un poco sorprendente. Aunque $U_f$ no hace nada explícitamente al estado del qubit 0, debido a que cambia el qubit 1 basándose en el estado del qubit 0, puede ocurrir que esto provoque un desplazamiento de fase en el qubit 0. Esto se conoce como el fenómeno de "retroceso de fase" y se analiza con más detalle en la Lección 1: Algoritmos de consulta cuántica del curso Fundamentos de algoritmos cuánticos.

Ahora que entendemos cómo funciona este algoritmo, vamos a implementarlo con Qiskit.

## Deutsch's algorithm:
 
## Step 1: Map the problem
 
# first, convert oracle circuit (above) to a single gate for drawing purposes. otherwise, the circuit is too large to display
blackbox = twobit_function(
    3
).to_gate()  # you may edit the number (1-4) inside "twobit_function()" to select among the four valid functions
blackbox.label = "$U_f$"
 
 
qc_deutsch = QuantumCircuit(2, 1)
 
qc_deutsch.x(1)
qc_deutsch.h(range(2))
 
qc_deutsch.barrier()
qc_deutsch.compose(twobit_function(2), inplace=True)
qc_deutsch.barrier()
 
qc_deutsch.h(0)
qc_deutsch.measure(0, 0)
 
qc_deutsch.draw("mpl")

Output:

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager
 
target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
 
qc_isa = pm.run(qc_deutsch)

# Step 3: Run the job on a real quantum computer
 
job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.c.get_counts()

# Step 4: Visualize and analyze results
 
## Analysis
print(counts)
if "1" in counts:
    print("balanced")
else:
    print("constant")

Output:

{'1': 1}
balanced

El algoritmo Deutsch-Jozsa

El algoritmo de Deutsch fue un primer paso importante para demostrar cómo un ordenador cuántico podría ser más eficiente que uno clásico, pero sólo supuso una modesta mejora: sólo requería una consulta, frente a las dos del caso clásico. En 1992, Deutsch y su colega Richard Jozsa ampliaron el algoritmo original de dos qubits a más qubits. El problema seguía siendo el mismo: determinar si una función es equilibrada o constante. Pero esta vez, la función pasa de $n$ bits a un solo bit. O bien la función devuelve 0 y 1 el mismo número de veces (es equilibrada ) o bien la función devuelve siempre 1 o siempre 0 (es constante ).

Aquí tienes un esquema del algoritmo:

Este algoritmo funciona de la misma manera que el algoritmo de Deutsch: el retroceso de fase permite leer el estado del qubit 0 para determinar si la función es constante o equilibrada. Es un poco más complicado de ver que en el caso del algoritmo de Deutsch de dos qubits, ya que los estados incluirán sumas sobre los $n$ qubits, por lo que la resolución de esos estados se dejará como ejercicio opcional al final del módulo. El algoritmo devolverá una cadena de bits con todos 0 si la función es constante, y una cadena de bits que contiene al menos un 1 si la función es equilibrada.

Para ver cómo funciona el algoritmo en Qiskit, primero, necesitamos generar nuestro oráculo: la función aleatoria que está garantizada para ser constante o equilibrada. El código siguiente generará una función equilibrada el 50% de las veces, y una función constante el 50% de las veces. No se preocupe si no sigue completamente el código: es complicado y no es necesario para nuestra comprensión del algoritmo cuántico.

from qiskit import QuantumCircuit
import numpy as np
 
 
def dj_function(num_qubits):
    """
    Create a random Deutsch-Jozsa function.
    """
 
    qc_dj = QuantumCircuit(num_qubits + 1)
    if np.random.randint(0, 2):
        # Flip output qubits with 50% chance
        qc_dj.x(num_qubits)
    if np.random.randint(0, 2):
        # return constant circuit with 50% chance.
        return qc_dj
 
    # If the "if" statement above was "TRUE" then we've returned the constant
    # function and the function is complete. If not, we proceed in creating our
    # balanced function. Everything below is to produce the balanced function:
 
    # select half of all possible states at random:
    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_dj, bit_string):
        for qubit, bit in enumerate(reversed(bit_string)):
            if bit == "1":
                qc_dj.x(qubit)
        return qc_dj
 
    for state in on_states:
        # qc_dj.barrier()  # Barriers are added to help visualize how the functions are created. They can safely be removed.
        qc_dj = add_cx(qc_dj, f"{state:0b}")
        qc_dj.mcx(list(range(num_qubits)), num_qubits)
        qc_dj = add_cx(qc_dj, f"{state:0b}")
 
    # qc_dj.barrier()
 
    return qc_dj
 
 
n = 3  # number of input qubits
 
oracle = dj_function(n)
 
display(oracle.draw("mpl"))

Output:

Se trata de la función oráculo, que puede ser equilibrada o constante. ¿Puedes ver si la salida en el último qubit depende de los valores introducidos en los primeros $n$ qubits? Si la salida del último qubit depende de los primeros $n$ qubits, ¿se puede saber si esa salida dependiente está equilibrada o no?

Podemos saber si la función es equilibrada o constante observando el circuito anterior, pero recuerda que, para este problema, pensamos en esta función como una "caja negra" No podemos asomarnos a la caja para ver el esquema del circuito. En su lugar, tenemos que consultar la caja.

Para consultar la caja, utilizamos el algoritmo Deutsch-Jozsa y determinamos si la función es constante o equilibrada:

blackbox = oracle.to_gate()
blackbox.label = "$U_f$"
 
 
qc_dj = QuantumCircuit(n + 1, n)
qc_dj.x(n)
qc_dj.h(range(n + 1))
qc_dj.barrier()
qc_dj.compose(blackbox, inplace=True)
qc_dj.barrier()
qc_dj.h(range(n))
qc_dj.measure(range(n), range(n))
 
qc_dj.decompose().decompose()
 
 
qc_dj.draw("mpl")

Output:

# Step 1: Map the problem
 
qc_dj = QuantumCircuit(n + 1, n)
qc_dj.x(n)
qc_dj.h(range(n + 1))
qc_dj.barrier()
qc_dj.compose(oracle, inplace=True)
qc_dj.barrier()
qc_dj.h(range(n))
qc_dj.measure(range(n), range(n))
 
qc_dj.decompose().decompose()
 
 
qc_dj.draw("mpl")

Output:

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager
 
target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
 
qc_isa = pm.run(qc_dj)

# Step 3: Run the job on a real quantum computer
 
job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.c.get_counts()

# Step 4: Visualize and analyze results
 
## Analysis
print(counts)
 
if (
    "0" * n in counts
):  # The D-J algorithm returns all zeroes if the function was constant
    print("constant")
else:
    print("balanced")  # anything other than all zeroes means the function is balanced.

Output:

{'110': 1}
balanced

Arriba, la primera línea de la salida es la cadena de bits de los resultados de la medición. La segunda línea muestra si la cadena de bits implica que la función era equilibrada o constante. Si la cadena de bits contenía todos ceros, era constante; si no, estaba equilibrada. Así pues, con una sola ejecución del circuito cuántico anterior, ¡podemos determinar si la función es constante o equilibrada!

Compruebe su comprensión

Lee las preguntas siguientes, piensa tus respuestas y haz clic en los triángulos para descubrir las soluciones.

Así, el algoritmo Deutsch-Jozsa demostró un aumento exponencial de la velocidad con respecto a un algoritmo determinista clásico (que devuelve la respuesta con un 100% de certeza), pero no un aumento significativo de la velocidad con respecto a uno probabilista (que devuelve un resultado que probablemente sea la respuesta correcta).

El problema Bernstein - Vazirani

En 1997, Ethan Bernstein y Umesh Vazirani utilizaron el algoritmo Deutsch-Jozsa para resolver un problema más específico y restringido que el problema Deutsch-Jozsa. En lugar de tratar simplemente de distinguir entre dos clases diferentes de funciones, como en el caso D-J, Bernstein y Vazirani utilizaron el algoritmo Deutsch-Jozsa para aprender realmente una cadena codificada en una función. He aquí el problema:

La función $f:\{0,1\}^n \rightarrow \{0,1\}$ sigue tomando una cadena $n$ -bit y emite un único bit. Pero ahora, en lugar de prometer que la función es equilibrada o constante, se nos promete que la función es el producto punto entre la cadena de entrada $x$ y alguna cadena secreta de $n$ -bit $s$, módulo 2. (Este producto punto módulo 2 se denomina "producto punto binario") El problema es averiguar cuál es la cadena secreta, $n$ -bit.

Dicho de otro modo, nos dan una función de caja negra $f: {0,1}^n \rightarrow {0,1}$ que satisface $f(x) = s \cdot x$ para alguna cadena $s$, y queremos aprender la cadena $s$.

Veamos cómo resuelve este problema el algoritmo D-J:

1. En primer lugar, se aplica una puerta Hadamard a los qubits de entrada $n$, y una puerta NOT más una Hadamard al qubit de salida, formando el estado:

El estado de los qubits 1 a $n$ puede escribirse más sencillamente como una suma sobre todos $2^n$ los estados base $n$ -qubit $|00...00\rangle, |00...01\rangle, |000...11\rangle, ..., |111...11\rangle$. Llamamos al conjunto de estos estados base $\Sigma^n$. (Para más detalles, véase Fundamentos de los algoritmos cuánticos )

2. A continuación, se aplica la puerta $U_f$ a los qubits. Esta puerta tomará los primeros n qubits como entrada (que ahora están en una superposición igual de todas las posibles cadenas de n bits) y aplica la función $f(x)=s \cdot x$ al qubit de salida, de modo que este qubit está ahora en el estado: $|- \oplus f(x)\rangle$. Gracias al mecanismo de retroceso de fase, el estado de este qubit permanece inalterado, pero algunos de los términos del estado del qubit de entrada adquieren un signo menos:

3. Ahora, el siguiente conjunto de Hadamards se aplica a los qubits 0 a $n-1$. No perder de vista los signos menos en este caso puede ser complicado. Es útil saber que la aplicación de una capa de Hadamards a $n$ qubits en un estado de base estándar $|x\rangle$ se puede escribir como:

Así que el estado se convierte:

4. El siguiente paso es medir los primeros $n$ bits. Pero, ¿qué mediremos? Resulta que el estado anterior se simplifica a: $|\Psi\rangle = |-\rangle \otimes |s\rangle$, pero eso está lejos de ser obvio. Si quieres seguir las matemáticas, consulta el curso Fundamentos de los algoritmos cuánticos de John Watrous. La cuestión es, sin embargo, que el mecanismo de contragolpe de fase lleva a que los qubits de entrada estén en el estado $|s\rangle$. Por tanto, para averiguar cuál era la cadena secreta $s$, basta con medir los qubits

Compruebe su comprensión

Lee las preguntas siguientes, piensa tus respuestas y haz clic en los triángulos para descubrir las soluciones.

También podemos verificar que este algoritmo resuelve con éxito el problema Bernstein-Vazirani probándolo experimentalmente. En primer lugar, creamos la función B-V que vive dentro de la caja negra:

# Step 1: Map the problem
 
 
def bv_function(s):
    """
    Create a Bernstein-Vazirani function from a string of 1s and 0s.
    """
    qc = QuantumCircuit(len(s) + 1)
    for index, bit in enumerate(reversed(s)):
        if bit == "1":
            qc.cx(index, len(s))
    return qc
 
 
display(bv_function("1000").draw("mpl"))

Output:

string = "1000"  # secret string that we'll pretend we don't know or have access to
n = len(string)
 
qc = QuantumCircuit(n + 1, n)
qc.x(n)
qc.h(range(n + 1))
qc.barrier()
# qc.compose(oracle, inplace = True)
qc.compose(bv_function(string), inplace=True)
qc.barrier()
qc.h(range(n))
qc.measure(range(n), range(n))
 
qc.draw("mpl")

Output:

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager
 
target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
 
qc_isa = pm.run(qc)

# Step 3: Run the job on a real quantum computer
 
job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.c.get_counts()

# Step 4: Visualize and analyze results
 
## Analysis
print(counts)

Output:

{'0000': 1}

Así, con una sola consulta, el algoritmo Deutsch-Jozsa devolverá la cadena $s$ utilizada en la función: $f(x)=x \cdot s$ cuando lo apliquemos al problema Bernstein-Vazirani. Con un algoritmo clásico, se necesitarían $n$ consultas para resolver el mismo problema.

Conclusión

Esperamos que el examen de estos sencillos ejemplos le haya dado una mejor intuición de cómo los ordenadores cuánticos son capaces de aprovechar la superposición, el entrelazamiento y la interferencia para lograr su poder sobre los ordenadores clásicos.

El algoritmo de Deutsch-Jozsa tiene una enorme importancia histórica porque fue el primero en demostrar un aumento de velocidad con respecto a un algoritmo clásico, pero sólo fue un aumento de velocidad polinómico. El algoritmo Deutsch-Jozsa es sólo el principio de la historia.

Después de utilizar el algoritmo para resolver su problema, Bernstein y Vazirani lo utilizaron como base para un problema más complicado y recursivo denominado problema recursivo de muestreo de Fourier. Su solución ofrecía una velocidad superpolinómica con respecto a los algoritmos clásicos. E incluso antes que Bernstein y Vazirani, Peter Shor ya había ideado su famoso algoritmo que permitía a los ordenadores cuánticos factorizar grandes números exponencialmente más rápido de lo que podría hacerlo cualquier algoritmo clásico. Estos resultados, en conjunto, mostraron la emocionante promesa de un futuro ordenador cuántico, y espolearon a físicos e ingenieros para hacer realidad este futuro.

Preguntas

Los profesores pueden solicitar versiones de estos cuadernos con claves de respuestas y orientaciones sobre su colocación en planes de estudios comunes rellenando esta rápida encuesta sobre cómo se están utilizando los cuadernos.

Conceptos críticos

• los algoritmos Deutsch y Deutsch-Jozsa utilizan el paralelismo cuántico combinado con la interferencia para encontrar una respuesta a un problema más rápido de lo que puede hacerlo un ordenador clásico.
• el mecanismo de retroceso de fase es un fenómeno cuántico contraintuitivo que transfiere las operaciones de un qubit a la fase de otro qubit. Los algoritmos Deutsch y Deutsch-Jozsa utilizan este mecanismo.
• El algoritmo Deutsch-Jozsa ofrece una velocidad polinómica superior a la de cualquier algoritmo clásico determinista.
• El algoritmo Deutsch-Jozsa puede aplicarse a un problema diferente, llamado problema Bernstein-Vazirani, para encontrar una cadena oculta codificada en una función.

Verdadero/falso

1. T/F El algoritmo de Deutsch es un caso especial del algoritmo de Deutsch-Jozsa en el que la entrada es un único qubit.
2. T/F Los algoritmos Deutsch y Deutsch-Jozsa utilizan la superposición cuántica y la interferencia para lograr su eficacia.
3. T/F El algoritmo Deutsch-Jozsa requiere múltiples evaluaciones de funciones para determinar si una función es constante o equilibrada.
4. T/F El "algoritmo Bernstein-Vazirani" es en realidad el mismo que el algoritmo Deutsch-Jozsa, aplicado a un problema diferente.
5. T/F El algoritmo Bernstein-Vazirani puede encontrar múltiples cadenas secretas simultáneamente.

Respuesta corta

1. ¿Cuánto tardaría un algoritmo clásico en resolver el problema Deutsch-Jozsa en el peor de los casos?

2. ¿Cuánto tardaría un algoritmo clásico en resolver el problema de Bernstein-Vazirani? ¿Qué aumento de velocidad ofrece el algoritmo DJ en este caso?

3. Describa el mecanismo de retroceso de fase y cómo funciona para resolver los problemas Deutsch-Jozsa y Bernstein-Vazirani.

Challenge problem

1. El algoritmo de Deutsch-Jozsa: Recuerda que tenías una pregunta más arriba en la que se te pedía que calcularas los estados intermedios de los qubits $\pi_1$, y $\pi_2$ del algoritmo de Deutsch. Haga lo mismo para los estados intermedios $n+1$ -qubit $\pi_1$, y $\pi_2$ del algoritmo Deutsch-Jozsa, para el caso específico de que $n=2$. A continuación, verifique que $\pi_3 = |-\rangle \otimes \sum\limits_{x_0...x_n}(-1)^{f(x_0...x_n)}|x_0 ... x_n\rangle$, de nuevo, para el caso específico de que $n=2$.