Problema de Bernstein-Vazirani

Hide code cell source

 
!pip install ket-lang
!pip install numpy
import numpy as np
import math
from ket import *

Referências

Material extraído do TCC Computação Quântica: Uma abordagem para estudantes de graduação em Ciências Exatas, de Giovani Goraiebe Pollachini.

O Algoritmo de Bernstein-Vazirani é um algoritmo quântico desenvolvido para resolver o Problema de Bernstein-Vazirani. Embora este problema não possua aplicações práticas diretas de grande relevância, ele serve como um laboratório teórico fundamental para explorar e compreender as capacidades distintivas da Computação Quântica. A principal referência para esta discussão é o livro {cite}nielsen_quantum_2010.

Problema de Bernstein-Vazirani#

Seja \({ f: \{0,1\}^n \to \{0,1\} }\) uma função tal que \({ f(x) = x \cdot s }\), onde “ · “ representa o produto escalar (módulo 2) entre \({x}\) e \({s}\), e \({ s \in \{0,1\}^n }\) é uma string secreta de tamanho \({ n }\). O objetivo é encontrar \({s}\).

Algorítimo clássico#

Agora considere o problema de Bernstein-Vazirani no contexto clássico. A seguir serão vistas brevemente a abordagem clássica para o problema.

Algoritmo Clássico Determinístico#

A Computação Clássica Determinística é um tipo de computação em que se busca algoritmos que não façam uso de recursos probabilísticos para resolver um problema. Os algoritmos determinísticos são tais que, ao serem executados diversas vezes para uma mesma entrada, produz-se sempre a mesma saída. Para que se resolva o problema nesse tipo de computação, é necessário realizar uma verificação de cada bit separadamente, o que equivale a testa uma base da matriz identidade. Desse modo, precisamento realizar uma chamada a função \(n\) vezes, sendo \(n\) o número de bits da string. Por exemplo:

\[\begin{split} \begin{array}{|c|c|} \hline \text{Input} & \text{Output} \\ \hline 000 & 0 \\ 001 & 0 \\ 010 & 1 \\ 011 & 1 \\ 100 & 1 \\ 101 & 1 \\ 110 & 0 \\ 111 & 0 \\ \hline \end{array} \end{split}\]

Para resolver essa série de entradas e saídas devemos realizar o texto para bit específicos, como, nesse exemplo: \({f(001), \space f(010) \space e \space f(100)}\). Sendo assim, temos a seguinte solução

\[\begin{split} \begin{array}{|c|c|} \hline \text{Input} & \text{Output} \\ \hline 001 & 0 \\ 010 & 1 \\ 100 & 1 \\ \hline \end{array} \end{split}\]

Portanto, a resposta para o problema é: \({110}\)

Dessa forma, nota-se que o custo computacional desse algoritmo é de \(n\) aplicações de \(f\).

Algoritmo de Bernstein-Vazirani#

Para resolver o problema de Bernstein-Vazirani com um algoritmo quântico, é necessário ter uma versão quântica da função linear \(f(x) = s \cdot x \mod 2\), fornecida como um oráculo quântico. Considere que \(f\) seja implementada por meio de um oráculo de fase \(U_f\), que atua sobre estados quânticos da seguinte forma:

\({ O_f \ket{x} = (-1)^{f(x)} \ket{x} = (-1)^{s \cdot x} \ket{x} }\)

O algoritmo de Bernstein-Vazirani para determinar a string secreta \({ s \in \{0,1\}^n }\) é dado pelo seguinte procedimento:

Procedimento:

\[\begin{split} \begin{array}{ccc} \text{Etapa 0:} & \ket{0}^{\otimes n}\ket{1} & \text{Preparação do estado inicial} \\ \text{Etapa 1:} & \ket{+}^{\otimes n}\ket{-} & \text{Superposição com } H^{\otimes (n+1)} \\ \text{Etapa 2:} & O_f\ket{+}^{\otimes n}\ket{-} & \text{Aplicação do oráculo } O_f \text{ (fase)} \\ \text{Etapa 3:} & H^{\otimes n}O_f\ket{+}^{\otimes n}\ket{-} & \text{Transformada de Hadamard nos n qubits} \\ \end{array} \end{split}\]

Saída: A probabilidade da medida de \(\ket{\psi_3}\) resultar em \(\ket{0}^{\otimes n}\) é

\[\begin{split} \begin{cases} 1 & \text{se } s = 0^n \\ 0 & \text{se } s \neq 0^n \end{cases} \end{split}\]

A medida de \(\ket{\psi_3}\) resulta deterministicamente no estado \(\ket{s}\) com probabilidade 1, revelando exatamente a string secreta \(s\).

Circuito Notação compacta:

bv_notacao_compacta

Notação expandida:

bv_notacao_expandida

Análise detalhada do algoritmo:

Na etapa 1, aplica-se \(H\) para cada qubit de entrada, resultando em:

\[\begin{split} \begin{split} \ket{\psi_1} &= H^{\otimes (n+1)} \ket{\psi_0} \\ &= H^{\otimes n} \ket{0}^{\otimes n} \otimes H \ket{1} \\ &= \ket{+}^{\otimes n} \otimes \ket{-} \\ &= \left(\frac{\ket{0} + \ket{1}}{\sqrt{2}} \right)^{\otimes n} \otimes \left(\frac{\ket{0} - \ket{1}}{\sqrt{2}} \right) \\ &= \frac{1}{\sqrt{2^n}} \sum_{x \in \mathbb{B}_n} \ket{x} \otimes \frac{\ket{0} - \ket{1}}{\sqrt{2}} \end{split} \end{split}\]

em que \(\mathbb{B}_n\) representa o conjunto de todas as palavras de \(n\) bits. Isto é,

A segunda etapa é caracterizada pela aplicação do oráculo de fase, fornecendo:

\[\begin{split} \begin{split} \ket{\psi_2} &= O_f \ket{\psi_1} \\ &= \frac{1}{\sqrt{2^n}} \sum_{x \in \mathbb{B}_n} O_f \left( \ket{x} \otimes \frac{\ket{0} - \ket{1}}{\sqrt{2}} \right) \\ &= \frac{1}{\sqrt{2^n}} \sum_{x \in \mathbb{B}_n} (-1)^{f(x)} \ket{x} \otimes \frac{\ket{0} - \ket{1}}{\sqrt{2}} \\ &= \frac{1}{\sqrt{2^n}} \sum_{x \in \mathbb{B}_n} (-1)^{s \cdot x} \ket{x} \otimes \frac{\ket{0} - \ket{1}}{\sqrt{2}} \end{split} \end{split}\]

Por final, a aplicação de \(H\) nos qubits resulta em:

\[\begin{split} \begin{split} \ket{\psi_3} &= (H^{\otimes n} \otimes I) \ket{\psi_2} \\ &= \frac{1}{\sqrt{2^n}} \sum_{x \in \mathbb{B}_n} (-1)^{s \cdot x} H^{\otimes n} \ket{x} \otimes \frac{\ket{0} - \ket{1}}{\sqrt{2}} \\ &= \frac{1}{\sqrt{2^n}} \sum_{x \in \mathbb{B}_n} (-1)^{s \cdot x} \left( \frac{1}{\sqrt{2^n}} \sum_{z \in \mathbb{B}_n} (-1)^{x \cdot z} \ket{z} \right) \otimes \frac{\ket{0} - \ket{1}}{\sqrt{2}} \\ &= \frac{1}{2^n} \sum_{z \in \mathbb{B}_n} \left( \sum_{x \in \mathbb{B}_n} (-1)^{x \cdot (s \oplus z)} \right) \ket{z} \otimes \frac{\ket{0} - \ket{1}}{\sqrt{2}} \end{split} \end{split}\]

Simplificação usando propriedade de ortogonalidade $\( \sum_{x \in \mathbb{B}_n} (-1)^{x \cdot (s \oplus z)} = \begin{cases} 2^n & \text{se } s \oplus z = 0^n \\ 0 & \text{caso contrário} \end{cases} \)$

Portanto: $\( \ket{\psi_3} = \ket{s} \otimes \frac{\ket{0} - \ket{1}}{\sqrt{2}} \)$

Comparação de desempenho#

A tabela abaixo traz a comparação entre o desempenho dos algoritmos clássico e quântico.

\[\begin{split} \begin{array}{l|l} \text{Algoritmo} & \text{Desempenho } (\# \text{ aplicações de } f) \\ \hline \text{Clássico} & n \\ \text{Quântico} & 1 \end{array} \end{split}\]

A comparação direta entre as complexidades de consulta clássica (Θ(n)) e quântica (Θ(1)) para o problema de Bernstein-Vazirani, embora matematicamente correta, deve ser interpretada com cautela, pois operações em arquiteturas distintas possuem naturezas e custos computacionais fundamentalmente diferentes que não permitem uma equiparação direta. No entanto, como exercício teórico, essa análise revela o potencial da computação quântica para explorar paralelismo e interferência de formas radicalmente novas, oferecendo um vislumbre conceitual de como certos problemas poderiam ser resolvidos de maneira intrinsicamente mais eficiente em princípio, mesmo que desafios práticos de implementação permaneçam.

Em relação ao algoritmo clássico, o algoritmo quântico apresenta ganho exponencial em desempenho.

Simulação do algorítimo de Bernstein-Vazirani#

Para simular o algorítimo de Bernstein-Vazirani usaremos a línguagem Ket de computação quântica, para isso precisamos ter ela instalada, caso não possua o pacote instalado rode o seguinte código:

pip install ket-lang

Com a biblioteca instalada, importa-se para ser usada dentro do seu código:

from ket import *

Exercício:

Antes de implementarmos o algorítmo de Bernstein Vazirani, tente realizar uma versão mais fácil, unicamente para a string \(s = 1010\)

Faremos o mesmo exemplo realizado com o Algoritmo de Bernstein-Vazirani, implementaremos um oráculo que pode ser usada para qualquer string \(s\):

Em seguida, implementaremo ele no algoritmo completo de Bernstein-Vazirani para verificar se o algoritmo consegue retornar a string secreta com uma única chamada ao oráculo

# Exemplo de oráculo
def oracle(qubits, bits):
    for q, b in zip(qubits, bits):
        if b == "1":
            Z(q)

Agora implementaremos o algoritmo de Bernstein-Vazirani, utilizando esses oráculos que criamos

def bernstein_vazirani(bits):
    # Cria um processo quântico
    p = Process()

    # Número de bits na string secreta
    n = len(bits)

    # Aloca n qubits para a entrada e 1 qubit auxiliar
    qubits = p.alloc(n)
    auxiliar = p.alloc()

    # Inicializa o qubit auxiliar no estado |1⟩
    X(auxiliar)

    # Aplica a porta Hadamard a todos os qubits
    H(qubits + auxiliar)
    # Aplica o oráculo
    oracle(qubits, bits)

    # Aplica a porta Hadamard aos qubits de entrada
    H(qubits)

    # Mede os qubits de entrada
    results = [measure(q).get() for q in qubits]

    return results


bernstein_vazirani("1011")  # Exemplo de uso

[1, 0, 1, 1]

Provavel Dúvida:

O algoritmo de Bernstein-Vazirani não recebe a string secreta diretamente como input, mas sim acesso a um oráculo que contém essa string de forma oculta. A string secreta está embutida internamente no oráculo como parte de sua implementação, e o objetivo do algoritmo é descobrir essa string desconhecida analisando o comportamento do oráculo quando consultado com diferentes entradas. A vantagem quântica surge porque o algoritmo consegue extrair todos os bits da string secreta simultaneamente usando superposição quântica, exigindo apenas uma consulta ao oráculo, enquanto abordagens clássicas precisariam de múltiplas consultas sequenciais.

Hide code cell source

 
from ket import ket_version
from IPython.display import HTML

version = f"""
<table>
  <thead>
    <tr>
      <th>{ket_version()[0].split()[0]}</th>
      <th>{ket_version()[0].split()[1]}</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>{ket_version()[1].split()[0].title()}</td>
      <td>{ket_version()[1].split()[1]}</td>
    </tr>
    <tr>
      <td>{ket_version()[2].split()[0].upper()}</td>
      <td>{ket_version()[2].split()[1]}</td>
    </tr>
  </tbody>
</table>
"""
HTML(version)
Ket v0.9.2.8
Libket v0.6.0
KBW v0.4.2
Conteúdo