El algoritmo de Deutsch-Jozsa

Para este módulo de Qiskit en el aula, los estudiantes deben tener un entorno Python funcional 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 computadoras cuánticas reales, los estudiantes necesitarán crear una cuenta en IBM Quantum® siguiendo los pasos de la guía Configura tu cuenta de IBM Cloud.

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

# Added by doQumentation — required packages for this notebook
!pip install -q numpy qiskit qiskit-aer qiskit-ibm-runtime

# 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'

Mira el recorrido del módulo a cargo de la Dra. Katie McCormick a continuación, o haz clic aquí para verlo en YouTube.

---

Introducción

A principios de la década de 1980, físicos cuánticos e informáticos tenían una noción vaga de que la mecánica cuántica podía aprovecharse para realizar computaciones mucho más poderosas que las que pueden hacer las computadoras clásicas. Su razonamiento era el siguiente: es difícil para una computadora clásica simular sistemas cuánticos, pero una computadora cuántica debería poder hacerlo de manera más eficiente. Y si una computadora cuántica pudiera simular sistemas cuánticos con mayor eficiencia, quizás hubiera otras tareas que también pudiera realizar más eficientemente que una computadora clásica.

La lógica era sólida, pero los detalles aún debían desarrollarse. Esto comenzó en 1985, cuando David Deutsch describió la primera "computadora cuántica universal." En ese mismo artículo, proporciónó el primer ejemplo de un problema para el cual una computadora cuántica podía resolver algo de manera más eficiente que una computadora clásica. Este primer ejemplo de juguete es ahora conocido como "el algoritmo de Deutsch." La mejora en el algoritmo de Deutsch fue modesta, pero Deutsch trabajó con Richard Jozsa unos años después para ampliar aún más la brecha entre las computadoras clásicas y las cuánticas.

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

1. Históricamente, fueron algunos de los primeros algoritmos cuánticos que demostraron superar a sus contrapartes clásicas. Entenderlos puede ayudarnos a comprender cómo ha evolucionado el pensamiento de la comunidad sobre la computación cuántica a lo largo del tiempo.
2. Pueden ayudarnos a entender algunos aspectos de la respuesta a una pregunta sorprendentemente sutil: ¿Qué le da su poder a la computación cuántica? A veces, las computadoras cuánticas se comparan con enormes procesadores paralelos de escala exponencial. Pero esto no es del todo correcto. Si bien parte de la respuesta a esta pregunta radica en el llamado "paralelismo cuántico", extraer la mayor cantidad de información posible en una sola ejecución es un arte sutil. Los algoritmos de Deutsch y Deutsch-Jozsa muestran cómo se puede lograr esto.

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 del poder de la computación cuántica proviene del "paralelismo cuántico", que es esencialmente la capacidad de realizar operaciones sobre múltiples entradas al mismo tiempo, ya que los estados de entrada de los qubits pueden estar en una superposición de múltiples estados clásicamente permitidos. Sin embargo, aunque un Circuit cuántico puede evaluar múltiples estados de entrada a la vez, extraer toda esa información de una sola vez es imposible.

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

$x$	$f_1(x)$	$f_2(x)$	$f_3(x)$	$f_4(x)$
0	0	0	1	1
1	0	1	0	1

Nos gustaría saber cuál de estas funciones (1-4) es nuestra $f(x)$. De forma clásica, necesitaríamos ejecutar la función dos veces: una para $x=0$ y otra para $x=1$. Pero veamos si podemos hacerlo mejor con un Circuit cuántico. Podemos aprender sobre la función con la siguiente Gate:

Aquí, la Gate $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 cuál es $x$, y el Qubit 1 nos dice cuál es $f(x)$. Entonces, si inicializamos $|x\rangle = \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$, 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:

Usando Qiskit, seleccionaremos aleatoriamente una de las cuatro funciones posibles anteriores y ejecutaremos el Circuit. Luego, tu tarea es usar las mediciones del Circuit cuántico para aprender la función en el menor número de ejecuciones posible.

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

• Paso 1: Mapear las entradas clásicas a un problema cuántico
• Paso 2: Optimizar el problema para la ejecución cuántica
• Paso 3: Ejecutar usando las Primitivas de Qiskit Runtime
• Paso 4: Post-procesamiento y análisis clásico

Comencemos cargando algunos paquetes necesarios, incluidas las primitivas de Qiskit Runtime. También seleccionaremos la computadora cuántica menos ocupada disponible.

A continuación hay código para guardar tus credenciales en el primer uso. Asegúrate de eliminar esta información del notebook después de guardarla en tu entorno, para que tus credenciales no se compartan accidentalmente al compartir el notebook. Consulta Configura tu cuenta de IBM Cloud e Inicializa el servicio en un entorno no confiable para 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)

ibm_brisbane

La celda a continuación te permitirá alternar entre usar el simulador o hardware real a lo largo del notebook. Te recomendamos ejecutarla 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 continuar con el flujo de trabajo de Qiskit patterns. En el paso de mapeo a continuación, primero creamos una función que selecciona entre las cuatro posibles funciones que toman un único bit y producen 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")

En el Circuit anterior, la Gate Hadamard "H" toma el Qubit 0, que inicialmente está en el estado $|0\rangle$, y lo lleva al estado de superposición $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$. Luego, $U_f$ evalúa la función $f(x)$ y la aplica al Qubit 1.

A continuación, necesitamos optimizar y transpilar el Circuit para ejecutarlo en la computadora cuántica:

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

Finalmente, ejecutamos nuestro Circuit transpilado en la computadora cuántica y visualizamos los 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)

Lo anterior es un histograma de nuestros resultados. Dependiendo del número de shots que hayas elegido para ejecutar el Circuit en el paso 3 anterior, podrías ver una o dos barras, que representan los estados medidos de los dos qubits en cada shot. Como siempre en Qiskit y en este notebook, usamos la 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á en el extremo derecho.

Entonces, dado que el Qubit 0 estaba en un estado de superposición, el Circuit evaluó la función para ambos $x=0$ y $x=1$ al mismo tiempo — ¡algo que las computadoras clásicas no pueden hacer! Pero el inconveniente aparece cuando queremos aprender sobre la función $f(x)$ — cuando medimos los qubits, colapsamos su estado. Si seleccionas "shots = 1" para ejecutar el Circuit solo una vez, solo verás una barra en el histograma anterior, y tu información sobre la función estará incompleta.

Comprueba tu comprensión

Lee las preguntas a continuación, piensa en tu respuesta y luego haz clic en el triángulo para revelar la solución.

¿Cuántas veces debemos ejecutar el algoritmo anterior para conocer la función $f(x)$? ¿Es esto mejor que el caso clásico? ¿Preferirías tener una computadora clásica o cuántica para resolver este problema?

Respuesta:

Dado que la medición colapsará la superposición y devolverá solo un valor, necesitamos ejecutar el Circuit al menos dos veces para obtener ambas salidas de la función $f(0)$ y $f(1)$. En el mejor caso, esto funciona igual que el caso clásico, donde calculamos tanto $f(0)$ como $f(1)$ en las primeras dos consultas. Pero existe la posibilidad de que necesitemos ejecutarlo más de dos veces, ya que la medición final es probabilística y podría devolver el mismo valor de $f(x)$ las primeras dos veces. En este caso, preferiría tener una computadora clásica.

Entonces, aunque el paralelismo cuántico puede ser poderoso cuando se usa de la manera correcta, no es correcto decir que una computadora cuántica funciona igual que un enorme procesador paralelo clásico. El acto de medir colapsa los estados cuánticos, por lo que solo podemos acceder a una única salida del cómputo.

El algoritmo de Deutsch

Aunque el paralelismo cuántico por sí solo no nos da una ventaja sobre las computadoras clásicas, podemos combinarlo con otro fenómeno cuántico, la interferencia, para lograr una aceleración. El algoritmo ahora conocido como "el algoritmo de Deutsch" es el primer ejemplo de un algoritmo que logra esto.

El problema

Este era el problema:

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

$x$	$f_1(x)$	$f_2(x)$	$f_3(x)$	$f_4(x)$
0	0	0	1	1
1	0	1	0	1

Las primeras y últimas funciones, $f_1(x)$ y $f_4(x)$, son constantes, mientras que las dos funciones del medio, $f_2(x)$ y $f_3(x)$, son balanceadas.

El algoritmo

La manera en que Deutsch abordó este problema fue mediante el "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. Consulta la Lección 1: Algoritmos de Consulta Cuántica 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 uno 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 es balanceada o constante, necesitaríamos consultar la caja dos veces para obtener tanto $f(0)$ como $f(1)$.

Sin embargo, en el algoritmo cuántico de Deutsch, encontró una manera de obtener la información con una sola consulta. Hizo un ajuste al Circuit de "paralelismo cuántico" anterior, preparando un estado de superposición en ambos qubits, en lugar de solo en el Qubit 0. Luego, las dos salidas de la función, $f(0)$ y $f(1)$, interfirieron para devolver 0 si ambas eran 0 o ambas eran 1 (la función era constante), y devolvieron 1 si eran diferentes (la función era balanceada). De esta manera, Deutsch podía diferenciar entre una función constante y una balanceada con una sola consulta.

Aquí hay un diagrama de Circuit del algoritmo de Deutsch:

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

Comprueba tu comprensión

Lee las preguntas a continuación, piensa en tus respuestas y luego haz clic en los triángulos para revelar las soluciones.

¿Cuál es el estado $|\pi_1\rangle$?

Respuesta:

Aplicar una Hadamard transforma el estado $|0\rangle$ en $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ y el estado $|1\rangle$ en $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$. Entonces, el estado completo se convierte en: $|\pi_1\rangle = [\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle+|1\rangle}{\sqrt{2}}]$

¿Cuál es el estado $|\pi_2\rangle$?

Respuesta:

Antes de aplicar $U_f$, recuerda lo que hace. Cambiará el estado del Qubit 1 en función del estado del Qubit 0. Por eso, tiene sentido factorizar el estado del Qubit 0: $|\pi_1\rangle = \frac{1}{2} (|0\rangle-|1\rangle)|0\rangle+\frac{1}{2}(|0\rangle-|1\rangle)|1\rangle$. Luego, si $f(0)=f(1)$, los dos términos se transformarán de la misma manera y el signo relativo entre ellos permanece positivo, pero si $f(0)\neq f(1)$, entonces el segundo término adquiere un signo negativo relativo al primero, cambiando el estado del Qubit 0 de $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ a $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$. Entonces:

$$|\pi_2\rangle = \begin{cases} \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle+|1\rangle}{\sqrt{2}}] & \text{si} & f(0) = f(1) \\ \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle-|1\rangle}{\sqrt{2}}] &\text{si} & f(0) \neq f(1) \\ \end{cases}$$

¿Cuál es el estado $|\pi_3\rangle$?

Respuesta:

Ahora, el estado del Qubit 0 es $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ o $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$, dependiendo de la función. Aplicar la Hadamard producirá $|0\rangle$ o $|1\rangle$, respectivamente.

$$|\pi_3\rangle = \begin{cases} \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}]|0\rangle & \text{si} & f(0) = f(1) \\ \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}]|1\rangle &\text{si} & f(0) \neq f(1) \\ \end{cases}$$

Revisando tus respuestas a las preguntas anteriores, nota que ocurre algo un poco sorprendente. Aunque $U_f$ no hace nada explícitamente al estado del Qubit 0, dado que cambia el Qubit 1 en función del estado del Qubit 0, puede ocurrir que esto cause un desplazamiento de fase en el Qubit 0. Esto se conoce como el fenómeno de "phase-kickback" (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")

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

{'1': 1}
balanced

El algoritmo de Deutsch-Jozsa

El algoritmo de Deutsch fue un primer paso importante para demostrar cómo una computadora cuántica podría ser más eficiente que una clásica, pero supuso solo una mejora modesta: requería una sola consulta, frente a dos en el caso clásico. En 1992, Deutsch y su colega Richard Jozsa extendieron el algoritmo original de dos qubits a más qubits. El problema seguía siendo el mismo: determinar si una función es balanceada o constante. Pero esta vez, la función va de $n$ bits a un solo bit. O bien la función devuelve 0 y 1 la misma cantidad de veces (es balanceada), o bien siempre devuelve 1 o siempre devuelve 0 (es constante).

A continuación se muestra el diagrama del Circuit del algoritmo:

Este algoritmo funciona de la misma manera que el algoritmo de Deutsch: el phase-kickback permite leer el estado del Qubit 0 para determinar si la función es constante o balanceada. Es un poco más difícil 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 eso, calcular esos estados se deja como ejercicio opcional al final del módulo. El algoritmo devolverá una cadena de bits de todos ceros si la función es constante, y una cadena de bits con al menos un 1 si la función es balanceada.

Para ver cómo funciona el algoritmo en Qiskit, primero necesitamos generar nuestro oráculo: la función aleatoria que se garantiza que es constante o balanceada. El código a continuación generará una función balanceada el 50 % de las veces y una función constante el otro 50 %. No te preocupes si no sigues completamente el código — es complejo y no es necesario para entender el 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"))

Esta es la función oráculo, que puede ser balanceada o constante. ¿Puedes ver, mirando el Circuit, si la salida del último Qubit depende de los valores introducidos en los primeros $n$ qubits? Si la salida del último Qubit depende de los primeros $n$ qubits, ¿puedes determinar si esa salida dependiente es balanceada o no?

Podemos saber si la función es balanceada o constante mirando el Circuit anterior, pero recuerda: a efectos de este problema, tratamos la función como una "caja negra". No podemos espiar dentro de la caja para ver el diagrama del Circuit. En cambio, necesitamos consultar la caja.

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

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

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

# 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.

{'110': 1}
balanced

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

Comprueba tu comprensión

Lee las preguntas a continuación, piensa en tus respuestas y luego haz clic en los triángulos para revelar las soluciones.

¿Cuántas consultas necesitaría una computadora clásica para determinar con un 100 % de certeza si una función es constante o balanceada? Recuerda que, de forma clásica, una sola consulta solo permite aplicar la función a una cadena de bits concreta.

Respuesta:

Hay $2^n$ cadenas de bits posibles para comprobar, y en el peor caso habría que probar $2^n/2+1$ de ellas. Por ejemplo, si la función fuera constante y se siguiera midiendo "1" como salida, no se podría tener la certeza de que realmente es constante hasta haber comprobado más de la mitad de los resultados. Antes de ese punto, podría ser que simplemente hubiera mucha mala suerte midiendo "1" en una función balanceada. Es como lanzar una moneda una y otra vez y que siempre salga cara. Es poco probable, pero no imposible.

¿Cómo cambiaría tu respuesta anterior si solo tuvieras que medir hasta que un resultado (equilibrado o constante) sea más probable que el otro? ¿Cuántas consultas harían falta en ese caso?

Respuesta:

En ese caso, bastaría con medir dos veces. Si las dos mediciones son diferentes, sabes que la función es balanceada. Si las dos mediciones son iguales, podría ser balanceada o constante. La probabilidad de que sea balanceada con este conjunto de mediciones es: $\frac{1}{2}\frac{2^n /2 - 1}{2^n-1}$. Esto es menor que 1/2, así que en ese caso es más probable que la función sea constante.

Así pues, el algoritmo de Deutsch-Jozsa demostró una aceleración exponencial sobre un algoritmo clásico determinista (uno que devuelve la respuesta con un 100 % de certeza), pero ninguna aceleración significativa sobre uno probabilístico (uno que devuelve un resultado que es probablemente correcto).

El problema de Bernstein-Vazirani

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

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

Dicho de otra manera, se nos da 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 el algoritmo D-J resuelve este problema:

1. Primero, se aplica una Gate Hadamard a los $n$ qubits de entrada, y una Gate NOT más una Hadamard al Qubit de salida, obteniendo el estado:

$$|\Psi\rangle = |-\rangle_{n} \otimes |+\rangle_{n-1} \otimes |+\rangle_{n-2} \otimes ... \otimes |+\rangle_0$$

El estado de los qubits 1 a $n$ puede escribirse de forma más sencilla como una suma sobre todos los $2^n$ estados de la base de $n$ qubits $|00...00\rangle, |00...01\rangle, |000...11\rangle, ..., |111...11\rangle$. Llamamos $\Sigma^n$ al conjunto de estos estados de la base. (Consulta Fundamentals of Quantum Algorithms para más detalles.)

$$|\Psi\rangle = |-\rangle \otimes \frac{1}{\sqrt{2^n}}\sum\limits_{x \in \Sigma^n}{|x\rangle}$$

2. A continuación, se aplica la Gate $U_f$ a los qubits. Esta Gate toma los primeros $n$ qubits como entrada (que ahora están en una superposición uniforme de todas las cadenas posibles de $n$ bits) y aplica la función $f(x)=s \cdot x$ al Qubit de salida, de modo que este Qubit queda en el estado: $|- \oplus f(x)\rangle$. Gracias al mecanismo de phase kickback, el estado de este Qubit permanece sin cambios, pero algunos de los términos del estado del Qubit de entrada adquieren un signo negativo:

$$|\Psi\rangle = |-\rangle \otimes \frac{1}{\sqrt{2^n}}\sum\limits_{x \in \Sigma^n}{(-1)^{f(x)}|x\rangle}$$

3. Ahora se aplica el siguiente conjunto de Hadamards a los qubits 0 a $n-1$. Llevar la cuenta de los signos negativos en este caso puede ser complicado. Es útil saber que aplicar una capa de Hadamards a $n$ qubits en un estado de la base estándar $|x\rangle$ puede escribirse como:

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

Entonces el estado se convierte en:

$$|\Psi\rangle = |-\rangle \otimes \frac{1}{2^n}\sum\limits_{x \in \Sigma^n}\sum\limits_{y \in \Sigma^n}{(-1)^{(s \cdot x) + (x \cdot y)}|y\rangle}$$

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$, aunque eso dista mucho de ser obvio. Si quieres seguir el desarrollo matemático, consulta el curso Fundamentals of Quantum Algorithms de John Watrous. La clave es que el mecanismo de phase kickback lleva a los qubits de entrada al estado $|s\rangle$. Así que, para averiguar cuál era la cadena secreta $s$, ¡solo tienes que medir los qubits!

Comprueba tu comprensión

Lee las preguntas a continuación, piensa en tus respuestas y luego haz clic en los triángulos para revelar las soluciones.

Verifica que el estado del Paso 3 anterior es efectivamente el estado $|s\rangle$ para el caso especial de $n=1$.

Respuesta:

Cuando escribes explícitamente las dos sumatorias, deberías obtener un estado con cuatro términos (omitamos el estado de salida $|-\rangle$ por ahora):

$$|\Psi\rangle = \frac{1}{2}[|0\rangle + (-1)^s |0\rangle + |1\rangle + (-1)^{(s+1)} |1\rangle]$$

Si $s=0$, los dos primeros términos se suman de forma constructiva y los dos últimos se cancelan, dejándonos $|\Psi\rangle = |0\rangle$. Si $s=1$, los dos últimos términos se suman de forma constructiva y los dos primeros se cancelan, dejándonos $|\Psi\rangle = |1\rangle$. Así que, en ambos casos, $|\Psi\rangle = |s\rangle$. Esperemos que este caso más sencillo te dé una idea de cómo funciona el caso general con $n$ qubits: todos los términos que no son $|s\rangle$ se cancelan por interferencia, dejando únicamente el estado $|s\rangle$.

¿Cómo puede el mismo algoritmo resolver tanto el problema de Bernstein-Vazirani como el de Deutsch-Jozsa? Para entenderlo, piensa en las funciones de Bernstein-Vazirani, que tienen la forma $f(x) = s \cdot x$. ¿Son estas funciones también funciones de Deutsch-Jozsa? Es decir, determina si las funciones de esta forma cumplen la promesa del problema Deutsch-Jozsa: que son constantes o balanceadas. ¿Cómo nos ayuda esto a entender que el mismo algoritmo resuelva dos problemas diferentes?

Respuesta:

Toda función de Bernstein-Vazirani de la forma $f(x) = s \cdot x$ también cumple la promesa del problema Deutsch-Jozsa: si s=00...00, entonces la función es constante (siempre devuelve 0 para cualquier cadena x). Si $s$ es cualquier otra cadena, entonces la función es balanceada. Por tanto, aplicar el algoritmo Deutsch-Jozsa a una de estas funciones resuelve ambos problemas simultáneamente: devuelve la cadena y, si esa cadena es 00...00, sabemos que es constante; si hay al menos un "1" en la cadena, sabemos que es balanceada.

También podemos verificar que este algoritmo resuelve satisfactoriamente el problema de Bernstein-Vazirani poniéndolo a prueba de forma experimental. Primero, 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"))

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

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

{'0000': 1}

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

Conclusión

Esperamos que, al examinar estos ejemplos sencillos, te hayamos dado una mejor intuición sobre cómo las computadoras cuánticas aprovechan la superposición, el entrelazamiento y la interferencia para lograr su ventaja sobre las computadoras clásicas.

El algoritmo de Deutsch-Jozsa tiene una enorme importancia histórica porque fue el primero en demostrar alguna aceleración sobre un algoritmo clásico, aunque fue solo una aceleración polinomial. El algoritmo de Deutsch-Jozsa es solo el comienzo de la historia.

Tras usar el algoritmo para resolver su problema, Bernstein y Vazirani lo utilizaron como base para un problema más complejo y recursivo denominado problema de muestreo de Fourier recursivo. Su solución ofrecía una aceleración superpolinomial sobre los algoritmos clásicos. E incluso antes que Bernstein y Vazirani, Peter Shor ya había desarrollado su famoso algoritmo que permite a las computadoras cuánticas factorizar números grandes exponencialmente más rápido que cualquier algoritmo clásico. Estos resultados, en conjunto, mostraron el emocionante potencial de las futuras computadoras cuánticas e impulsaron a físicos e ingenieros a hacer realidad ese futuro.

Preguntas

Los instructores pueden solicitar versiones de estos cuadernos con claves de respuesta y orientación sobre su integración en planes de estudio habituales completando esta breve encuesta sobre cómo se están utilizando los cuadernos.

Conceptos clave

• Los algoritmos de Deutsch y Deutsch-Jozsa usan el paralelismo cuántico combinado con la interferencia para encontrar la respuesta a un problema más rápido de lo que puede hacerlo una computadora clásica.
• El mecanismo de phase kickback es un fenómeno cuántico contraintuitivo que transfiere operaciones sobre un Qubit a la fase de otro Qubit. Los algoritmos de Deutsch y Deutsch-Jozsa hacen uso de este mecanismo.
• El algoritmo de Deutsch-Jozsa ofrece una aceleración polinomial sobre cualquier algoritmo clásico determinista.
• El algoritmo de Deutsch-Jozsa puede aplicarse a un problema diferente, llamado problema de Bernstein-Vazirani, para encontrar una cadena oculta codificada en una función.

Verdadero/falso

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

Respuesta corta

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

2. ¿Cuánto tiempo tardaría un algoritmo clásico en resolver el problema de Bernstein-Vazirani? ¿Qué aceleración ofrece el algoritmo D-J en este caso?

3. Describe el mecanismo de phase kickback y explica cómo funciona para resolver los problemas de Deutsch-Jozsa y Bernstein-Vazirani.

Problema desafío

1. El algoritmo de Deutsch-Jozsa: Recuerda que arriba tenías una pregunta en la que debías calcular los estados intermedios de qubits $\pi_1$ y $\pi_2$ del algoritmo de Deutsch. Haz lo mismo para los estados intermedios de $n+1$ qubits $\pi_1$ y $\pi_2$ del algoritmo de Deutsch-Jozsa, para el caso específico de $n=2$. Luego, verifica que $\pi_3 = |-\rangle \otimes \sum\limits_{x_0...x_n}(-1)^{f(x_0...x_n)}|x_0 ... x_n\rangle$, nuevamente, para el caso específico de $n=2$.