Algoritmo de Bernstein-Vazirani

El algoritmo de Bernstein-Vazirani es un algoritmo basado en el de Deutsch-Jozsa en el cual se resuelve un problema diferente, llamado problema de Bernstein-Vazirani ó Fourier sampling problem (problema de muestreo de Fourier). Dicho problema presenta una base de un problema más grande, presentado por los mismos autores, llamado recursive Fourier sampling problem (problema de muestreo de Fourier recursivo).

El Problema de Bernstein-Vazirani

La entrada del problema es una función que se define de forma similar al algoritmo de Deutsch-Jozsa:

$$\begin{gather} f: \{0,1\}^n \rightarrow \{0,1\} \end{gather}$$

Difiere en que en este problema la función tiene como precondición que existe una cadena binaria $s=s_{n-1}\ldots s_0$ tal que $f(x)=s\cdot x$ para todo $x\in\{0,1\}^n$.

Como salida se debe obtener la cadena $s$.

Solución

Utiliza el circuito de Deutsch-Jozsa. Varía en su procesamiento desde la etapa $\psi_3$ donde se mide el resultado.

Figura (1): Circuito de Deutsch-Jozsa que resuelve el problema de Bernstein-Vazirani con separadores ante la aplicación de cada puerta.

A continuación se analiza paso a paso el estado de los cubits según los separadores provistos en el gráfico, donde \(\psi_i\) es el estado en el paso \(i\), empezando con \(i=0\) y finalizando con \(i=3\):

$$\begin{align} \psi_0=&\ket{-}\ket{0}^{\otimes n}\\ \psi_1=&\ket{-}H^{\otimes n}\ket{0}^{\otimes n}\\ =&\ket{-}\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n} \ket{x}\\ \psi_2=&\ket{-}U_f\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n} \ket{x}\\ =&\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n} (-1)^{f(x)}\ket{x}\\ \psi_3=&H^{\otimes n}\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n} (-1)^{f(x)}\ket{x}\\ =&\sum_{z\in\{0,1\}^n} \left(\frac{1}{2^n}\sum_{x\in\{0,1\}^n} (-1)^{f(x)+x\cdot z}\right) \ket{z}\\ \end{align}$$

Un desarrollo elaborado de los pasos se puede observar dentro de la explicación paso a paso del algoritmo de Deutsch-Jozsa. Hasta este punto no existen variaciones con el algoritmo previamente mencionado. Luego se reemplaza $f(x)$ con la precondición dada:

$$\begin{align} \psi_3&=\sum_{z\in\{0,1\}^n} \left(\frac{1}{2^n}\sum_{x\in\{0,1\}^n} (-1)^{f(x)+x\cdot z}\right) \ket{z}\\ &=\sum_{z\in\{0,1\}^n} \left(\frac{1}{2^n}\sum_{x\in\{0,1\}^n} (-1)^{s\cdot x+x\cdot z}\right) \ket{z}\\ &=\sum_{z\in\{0,1\}^n} \left(\frac{1}{2^n}\sum_{x\in\{0,1\}^n} (-1)^{(s\oplus z)\cdot x}\right) \ket{z}\\ \end{align}$$

Ahora, se mide la amplitud del estado $\psi_3$, donde $\ket{z}$ es $\ket{s}$:

$$\begin{align} \left|\frac{1}{2^n}\sum_{x\in\{0,1\}^n} (-1)^{(s\oplus s)\cdot x}\right|^2&=\left|\frac{1}{2^n}\sum_{x\in\{0,1\}^n} (-1)^{(0) \cdot x}\right|^2\\ &=\left|\frac{1}{2^n}\sum_{x\in\{0,1\}^n} (-1)^{0}\right|^2\\ &=\left|\frac{1}{2^n}\sum_{x\in\{0,1\}^n} 1\right|^2\\ &=\left|\frac{1}{2^n}\sum_{x\in\{0,1\}^n} 1\right|^2\\ &=\left|\frac{1}{2^n}2^n\right|^2\\ &=1\\ \end{align}$$

Así, el estado final del algoritmo (luego de la medición) es $\ket{s}$, ya que el resto de estados tendrán amplitud 0.

Ejemplos

Sea $s=1010$ la cadena a codificar, se modifica el oráculo con una función que codifica este valor oculto. Se utilizan puertas CNOT para codificar la cadena oculta.

Círculos

Nota

Por cuestiones de legibilidad, para la notación de círculos se buscará la cadena $s=101$ sobre un espacio de búsqueda de tres cubits, sumados al cubit del oráculo.

\(\psi_0\)

Estado inicial del algoritmo $\ket{-000}$

$$\ket{0000}$$

$$\ket{0001}$$

$$\ket{0010}$$

$$\ket{0011}$$

$$\ket{0100}$$

$$\ket{0101}$$

$$\ket{0110}$$

$$\ket{0111}$$

$$\ket{1000}$$

$$\ket{1001}$$

$$\ket{1010}$$

$$\ket{1011}$$

$$\ket{1100}$$

$$\ket{1101}$$

$$\ket{1110}$$

$$\ket{1111}$$

\(\psi_1\)

Aplicación de puertas Hadamard sobre los tres cubits menos significativos.

$$\ket{0000}$$

$$\ket{0001}$$

$$\ket{0010}$$

$$\ket{0011}$$

$$\ket{0100}$$

$$\ket{0101}$$

$$\ket{0110}$$

$$\ket{0111}$$

$$\ket{1000}$$

$$\ket{1001}$$

$$\ket{1010}$$

$$\ket{1011}$$

$$\ket{1100}$$

$$\ket{1101}$$

$$\ket{1110}$$

$$\ket{1111}$$

\(\psi_2\)

Aplicación del oráculo. En este ejemplo, el oráculo está implementado con dos puertas $CNOT$. La primera tiene al cubit menos significativo como control y la segunda al tercer cubit menos significativo. En ambos casos, el cubit objetivo es el del oráculo (el más significativo).

$$\ket{0000}$$

$$\ket{0001}$$

$$\ket{0010}$$

$$\ket{0011}$$

$$\ket{0100}$$

$$\ket{0101}$$

$$\ket{0110}$$

$$\ket{0111}$$

$$\ket{1000}$$

$$\ket{1001}$$

$$\ket{1010}$$

$$\ket{1011}$$

$$\ket{1100}$$

$$\ket{1101}$$

$$\ket{1110}$$

$$\ket{1111}$$

\(\psi_3\)

Se aplica Hadamard sobre los cubits que no son del oráculo (todos excepto el más significativo). Así se obtiene la respuesta final.

$$\ket{0000}$$

$$\ket{0001}$$

$$\ket{0010}$$

$$\ket{0011}$$

$$\ket{0100}$$

$$\ket{0101}$$

$$\ket{0110}$$

$$\ket{0111}$$

$$\ket{1000}$$

$$\ket{1001}$$

$$\ket{1010}$$

$$\ket{1011}$$

$$\ket{1100}$$

$$\ket{1101}$$

$$\ket{1110}$$

$$\ket{1111}$$

Ignorando el estado del cubit del oráculo (el cubit más significativo), la probabilidad de obtener $\ket{s} = \ket{101}$ es del $100\%$.

Quirk

Nota

El resultado de la medición representa con valores “On” aquellos valores que son $1$ y los que son “Off” los valores que son $0$, formando la cadena $1010$ si se lee de arriba hacia abajo.

Qiskit

Código

from qiskit import QuantumCircuit
from algorithms import run_circuit, circuit_deutsch_jozsa
import sys

def bv_function(s):
    """
    Crea una función Bernstein-Vazirani desde una cadena de 1s y 0s.
    """
    qc = QuantumCircuit(len(s) + 1)
    qc.barrier()
    for index, bit in enumerate(s):
        if bit == "1":
            qc.cx(index, len(s))
    qc.barrier()
    return qc

def analyze_bv_results(results):
    counts = results.get_counts()
    return counts

s_string = "1010"
if len(sys.argv) >= 2:
    s_string = sys.argv[1] # permite utilizar cadena por parametro
print("Cadena secreta 's':", s_string)
print("Oráculo:")
oracle = bv_function(s_string) # codifica la función secreta con 's'
print(oracle.draw())
print("Bernstein-Vazirani con circuito Deutsch-Jozsa:")
bv_circuit = circuit_deutsch_jozsa(oracle)
print(bv_circuit.draw())
print("Corriendo el circuito Bernstein-Vazirani:")
print(analyze_bv_results(run_circuit(bv_circuit) ))

Resultado

Cadena secreta 's': 1010
Oráculo:
      ░            ░
q_0: ─░───■────────░─
      ░   │        ░
q_1: ─░───┼────────░─
      ░   │        ░
q_2: ─░───┼────■───░─
      ░   │    │   ░
q_3: ─░───┼────┼───░─
      ░ ┌─┴─┐┌─┴─┐ ░
q_4: ─░─┤ X ├┤ X ├─░─
      ░ └───┘└───┘ ░
Bernstein-Vazirani con circuito Deutsch-Jozsa:
     ┌───┐      ░            ░ ┌───┐┌─┐
q_0: ┤ H ├──────░───■────────░─┤ H ├┤M├─────────
     ├───┤      ░   │        ░ ├───┤└╥┘┌─┐
q_1: ┤ H ├──────░───┼────────░─┤ H ├─╫─┤M├──────
     ├───┤      ░   │        ░ ├───┤ ║ └╥┘┌─┐
q_2: ┤ H ├──────░───┼────■───░─┤ H ├─╫──╫─┤M├───
     ├───┤      ░   │    │   ░ ├───┤ ║  ║ └╥┘┌─┐
q_3: ┤ H ├──────░───┼────┼───░─┤ H ├─╫──╫──╫─┤M├
     ├───┤┌───┐ ░ ┌─┴─┐┌─┴─┐ ░ └───┘ ║  ║  ║ └╥┘
q_4: ┤ X ├┤ H ├─░─┤ X ├┤ X ├─░───────╫──╫──╫──╫─
     └───┘└───┘ ░ └───┘└───┘ ░       ║  ║  ║  ║
c: 4/════════════════════════════════╩══╩══╩══╩═
                                     0  1  2  3
Corriendo el circuito Bernstein-Vazirani:
{'0101': 1024}

Librería común

from qiskit import QuantumCircuit
from qiskit_aer import QasmSimulator
from qiskit import transpile

def run_circuit(qc: QuantumCircuit):
    sim = QasmSimulator()
    transpiled = transpile(qc)
    result = sim.run(transpiled).result()
    return result

def circuit_deutsch_jozsa(function: QuantumCircuit):
    """
    Compila un circuito para usarlo en el algoritmo de Deutsch-Jozsa.
    """
    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

Más información

Bibliografía:

Recomendada

Alternativa

Opcional

Libro

Capítulo 7.4.3, Introduction to Classical and Quantum Computing (Thomas G. Wong) [Inglés]

Video

Quantum Computing Course: 3.5 Bernstein-Vazarani Algorithm (Quantum Soar) [Inglés]

Video

Quantum Query Algorithms | Understanding Quantum Information & Computation - Lesson 05 (Qiskit) [Inglés]