bernstein-vazirani.ipynb

Kernel: Python 3

Algoritmo Bernstein-Vazirani

En esta sección, primero presentamos el problema de Bernstein-Vazirani, su solución clásica y el algoritmo cuántico para resolverlo. Luego, implementamos el algoritmo cuántico usando Qiskit y lo ejecutamos tanto en un simulador como en un dispositivo.

1. El Algoritmo de Bernstein-Vazirani

El algoritmo de Bernstein-Vazirani, presentado por primera vez en la Referencia [1], puede verse como una extensión del algoritmo de Deutsch-Jozsa que cubrimos en la última sección. Se mostró que puede haber ventajas en el uso de una computadora cuántica como herramienta computacional para problemas más complejos que el problema de Deutsch-Jozsa.

1.1 El Problema de Bernstein-Vazirani

Nuevamente se nos da una función de caja negra $f$, que toma como entrada una cadena de bits ($x$) y devuelve $0$ o $1$, es decir: $$f({x_0,x_1,x_2,...}) \rightarrow 0 \textrm{ o } 1 \textrm{ donde } x_n \textrm{ es }0 \textrm{ o } 1$$

En lugar de que la función sea balanceada o constante como en el problema de Deutsch-Jozsa, ahora se garantiza que la función devolverá el producto bit a bit de la entrada con alguna cadena, $s$. En otras palabras, dada una entrada $x$, $f(x) = s \cdot x , \text{(mod 2)}$. Estamos esperando encontrar $s$. Como circuito reversible clásico, el oráculo de Bernstein-Vazirani se ve así:

1.2 La Solución Clásica

Clásicamente, el oráculo devuelve: $$f_s(x) = s \cdot x \mod 2$$ dada una entrada $x$. Por lo tanto, la cadena de bits oculta $s$ puede revelarse consultando el oráculo con la secuencia de entradas:

Entrada(x) :-: 100...0 010...0 001...0 000...1

Donde cada consulta revela un bit diferente de $s$ (el bit $s_i$). Por ejemplo, con x = 1000...0 uno puede obtener el bit menos significativo de $s$, con x = 0100...0 podemos encontrar el siguiente bit menos significativo, y así sucesivamente. Esto significa que necesitaríamos mandar llamar a la función $f_s(x)$, $n$ veces.

1.3 La Solución Cuántica

Usando una computadora cuántica, podemos resolver este problema con 100% de confianza después de una sola llamada a la función $f(x)$. El algoritmo cuántico de Bernstein-Vazirani para encontrar la cadena de bits oculta es muy simple:

1. Inicializar los qubits de entrada en el estado $|0\rangle^{\otimes n}$ y el qubit de salida en $|{-}\rangle$.

2. Aplicar compuertas Hadamard al registro de entrada

3. Consultar el oráculo

4. Aplicar compuertas Hadamard al registro de entrada

5. Medir

Para explicar el algoritmo, veamos más de cerca lo que sucede cuando aplicamos una compuerta H a cada qubit. Si tenemos un estado de $n$ qubits, $|a\rangle$, y aplicamos las compuertas H, veremos la transformación:

$$|a\rangle \xrightarrow{H^{\otimes n}} \frac{1}{\sqrt{2^n}} \sum_{x\in {0,1}^n} (-1)^{a\cdot x}|x\rangle.$$

Explicación de la Ecuación (Haz clic para ampliar)

Recordamos que Hadamard realiza las siguientes transformaciones en un qubit:

$$H|0\rangle = \tfrac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$$

Usando la notación de suma, podríamos reescribirlo así:

$$H|a\rangle = \frac{1}{\sqrt{2}}\sum_{x\in {0,1}} (-1)^{a\cdot x}|x\rangle.$$

Para dos qubits, aplicar un Hadamard a cada uno realiza las siguientes transformaciones:

$$H^{\otimes 2}|00\rangle = \tfrac{1}{2}(|00\rangle + |01\rangle + |10\rangle + |11\rangle)$$

Podemos expresar esto usando la siguiente suma:

$$H^{\otimes 2}|a\rangle = \frac{1}{2}\sum_{x\in {0,1}^2} (-1)^{a\cdot x}|x\rangle$$

Es de esperar que ahora veas cómo llegamos a la ecuación anterior.

En particular, cuando empezamos con un registro cuántico $|00\dots 0\rangle$ y le aplicamos $n$ compuertas Hadamard, tenemos la superposición cuántica familiar:

$$|00\dots 0\rangle \xrightarrow{H^{\otimes n}} \frac{1}{\sqrt{2^n}} \sum_{x\in {0,1}^n} |x\rangle$$

En este caso, el término de fase $(-1)^{a\cdot x}$ desaparece, ya que $a=0$, y por lo tanto $(-1)^{a\cdot x} = 1$.

El oráculo clásico $f_s$ devuelve $1$ para cualquier entrada $x$ tal que $s \cdot x\mod 2 = 1$, y de lo contrario devuelve $0$. Si usamos el mismo truco de retroceso de fase del algoritmo Deutsch-Jozsa y actuamos sobre un qubit en el estado $|{-}\rangle$, obtenemos la siguiente transformación:

$$|x \rangle \xrightarrow{f_s} (-1)^{s\cdot x} |x \rangle$$

El algoritmo para revelar la cadena de bits oculta sigue naturalmente consultando el oráculo cuántico $f_s$ con la superposición cuántica obtenida de la transformación de Hadamard de $|00\dots 0\rangle$. A saber,

$$|00\dots 0\rangle \xrightarrow{H^{\otimes n}} \frac{1}{\sqrt{2^n}} \sum_{x\in {0,1}^n} |x\rangle \xrightarrow{f_a} \frac{1}{\sqrt{2^n}} \sum_{x\in {0,1}^n} (-1)^{a\cdot x}|x\rangle$$

Debido a que el inverso de las compuertas Hadamard $n$ es nuevamente las compuertas Hadamard $n$, podemos obtener $a$ con

$$\frac{1}{\sqrt{2^n}} \sum_{x\in {0,1}^n} (-1)^{a\cdot x}|x\rangle \xrightarrow{H^{\otimes n}} |a\rangle$$

2. Ejemplo

Veamos un ejemplo específico para $n=2$ qubits y una cadena secreta $s=11$. Ten en cuenta que estamos siguiendo la formulación en la Referencia [2] que genera un circuito para el oráculo cuántico de Bernstein-Vazirani usando solo un registro.

1. El registro de dos qubits se inicializa en cero:

$$\lvert \psi_0 \rangle = \lvert 0 0 \rangle$$

Aplica una compuerta Hadamard a ambos qubits:

$$\lvert \psi_1 \rangle = \frac{1}{2} \left( \lvert 0 0 \rangle + \lvert 0 1 \rangle + \lvert 1 0 \rangle + \lvert 1 1 \rangle \right)$$

Para la cadena $s=11$, el oráculo cuántico realiza la operación: $$|x \rangle \xrightarrow{f_s} (-1)^{x\cdot 11} |x \rangle.$$

$$\lvert \psi_2 \rangle = \frac{1}{2} \left( (-1)^{00\cdot 11}|00\rangle + (-1)^{01\cdot 11}|01\rangle + (-1)^{10\cdot 11}|10\rangle + (-1)^{11\cdot 11}|11\rangle \right)$$$$\lvert \psi_2 \rangle = \frac{1}{2} \left( \lvert 0 0 \rangle - \lvert 0 1 \rangle - \lvert 1 0 \rangle + \lvert 1 1 \rangle \right)$$

Aplica una compuerta Hadamard a ambos qubits:

$$\lvert \psi_3 \rangle = \lvert 1 1 \rangle$$

Mide para encontrar la cadena secreta $s=11$

Utiliza el widget bv_widget a continuación. Presiona los botones para aplicar los diferentes pasos e intenta seguir el algoritmo. Puedes cambiar la cantidad de qubits de entrada y el valor de la cadena secreta a través de los dos primeros argumentos posicionales.

from qiskit_textbook.widgets import bv_widget
bv_widget(2, "11")

HBox(children=(Button(description='H⊗ⁿ', style=ButtonStyle()), Button(description='Oracle', style=ButtonStyle(…

HTMLMath(value='$$ |00\\rangle = |00\\rangle $$')

Image(value=b'\x89PNG\r\n\x1a\n\x00\x00\x00\rIHDR\x00\x00\x00\xce\x00\x00\x00\xcc\x08\x06\x00\x00\x00;\xd7\x9c…

3. Implementación en Qiskit

Ahora veremos la implementación del algoritmo de Bernstein-Vazirani en Qiskit para una función de tres bits con $s=011$.

# inicialización
import matplotlib.pyplot as plt
import numpy as np

# importar Qiskit
from qiskit import IBMQ, Aer
from qiskit.providers.ibmq import least_busy
from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister, transpile

# importar las herramientas básicas para graficar
from qiskit.visualization import plot_histogram

Primero establecemos la cantidad de qubits utilizados en el experimento y la cadena de bits ocultos $s$ que debe encontrar el algoritmo. La cadena de bits ocultos $s$ determina el circuito para el oráculo cuántico.

n = 3 # número de qubits usados para representar s
s = '011'   # la cadena binaria oculta

Luego usamos Qiskit para programar el algoritmo de Bernstein-Vazirani.

# Necesitamos un circuito con n qubits, más un qubit auxiliar
# También necesitamos n bits clásicos para escribir la salida
bv_circuit = QuantumCircuit(n+1, n)

# poner el auxiliar en el estado |->
bv_circuit.h(n)
bv_circuit.z(n)

# Aplicar compuertas Hadamard antes de consultar al oráculo
for i in range(n):
    bv_circuit.h(i)
    
# Aplicar una barrera 
bv_circuit.barrier()

# Aplicar el oráculo del producto interno
s = s[::-1] # reverse s to fit qiskit's qubit ordering
for q in range(n):
    if s[q] == '0':
        bv_circuit.i(q)
    else:
        bv_circuit.cx(q, n)
        
# Aplicar una barrera
bv_circuit.barrier()

#Aplicar compuertas Hadamard después de consultar al oráculo
for i in range(n):
    bv_circuit.h(i)

# Medición
for i in range(n):
    bv_circuit.measure(i, i)

bv_circuit.draw()

3a. Experimenta con Simuladores

Podemos ejecutar el circuito anterior en el simulador.

# usar el simulador local
aer_sim = Aer.get_backend('aer_simulator')
shots = 1024
results = aer_sim.run(bv_circuit).result()
answer = results.get_counts()

plot_histogram(answer)

Podemos ver que el resultado de la medición es la cadena oculta 011.

3b. Experimenta con Dispositivos Reales

Podemos ejecutar el circuito anterior en el simulador.

# Cargar nuestras cuentas IBMQ guardadas y obtener el dispositivo backend menos ocupado con menor que o igual a 5 qubits
IBMQ.load_account()
provider = IBMQ.get_provider(hub='ibm-q')
provider.backends()
backend = least_busy(provider.backends(filters=lambda x: x.configuration().n_qubits <= 5 and
                                   x.configuration().n_qubits >= 2 and
                                   not x.configuration().simulator and x.status().operational==True))
print("least busy backend: ", backend)

least busy backend:  ibmq_quito

# Ejecutar nuestro circuito en el backend menos ocupado. Supervisar la ejecución del trabajo en la fila
from qiskit.tools.monitor import job_monitor

shots = 1024
transpiled_bv_circuit = transpile(bv_circuit, backend)
job = backend.run(transpiled_bv_circuit, shots=shots)

job_monitor(job, interval=2)

Job Status: job has successfully run

# Obtener los resultados del cálculo.
results = job.result()
answer = results.get_counts()

plot_histogram(answer)

Como podemos ver, la mayoría de los resultados son 011. Los otros resultados se deben a errores en el cálculo cuántico.

4. Ejercicios

1. Utiliza el widget a continuación para ver el algoritmo de Bernstein-Vazirani en acción con diferentes oráculos:

from qiskit_textbook.widgets import bv_widget
bv_widget(3, "011", hide_oracle=False)

HBox(children=(Button(description='H⊗ⁿ', style=ButtonStyle()), Button(description='Oracle', style=ButtonStyle(…

HTMLMath(value='$$ |000\\rangle = |000\\rangle $$')

Image(value=b'\x89PNG\r\n\x1a\n\x00\x00\x00\rIHDR\x00\x00\x00\xce\x00\x00\x01\x08\x08\x06\x00\x00\x00\x17\xd9\…

1. La implementación anterior de Bernstein-Vazirani es para una cadena de bits secreta $s = 011$. Modifica la implementación para una cadena secreta $s = 1011$. ¿Los resultados son los que esperas? Explica.

2. La implementación anterior de Bernstein-Vazirani es para una cadena de bits secreta $s = 011$. Modifica la implementación para una cadena secreta $s = 11101101$. ¿Los resultados son los que esperas? Explica.

5. Referencias

1. Ethan Bernstein and Umesh Vazirani (1997) "Quantum Complexity Theory" SIAM Journal on Computing, Vol. 26, No. 5: 1411-1473, doi:10.1137/S0097539796300921.

2. Jiangfeng Du, Mingjun Shi, Jihui Wu, Xianyi Zhou, Yangmei Fan, BangJiao Ye, Rongdian Han (2001) "Implementation of a quantum algorithm to solve the Bernstein-Vazirani parity problem without entanglement on an ensemble quantum computer", Phys. Rev. A 64, 042306, 10.1103/PhysRevA.64.042306, arXiv:quant-ph/0012114.

import qiskit.tools.jupyter
%qiskit_version_table

/usr/local/anaconda3/envs/terra-unstable/lib/python3.9/site-packages/qiskit/aqua/__init__.py:86: DeprecationWarning: The package qiskit.aqua is deprecated. It was moved/refactored to qiskit-terra For more information see <https://github.com/Qiskit/qiskit-aqua/blob/main/README.md#migration-guide>
  warn_package('aqua', 'qiskit-terra')