thumb|400x400px|Aplicar a função usando o oráculo a uma superposição de estados e determinar a string secreta através da medição
O algoritmo de Bernstein–Vazirani, que resolve o problema de Bernstein–Vazirani, é um algoritmo quântico inventado por Ethan Bernstein e Umesh Vazirani em 1997. É uma versão restrita do algoritmo de Deutsch–Jozsa, onde, em vez de distinguir entre duas classes diferentes de funções, ele tenta aprender uma string codificada em uma função. O algoritmo de Bernstein–Vazirani foi projetado para provar uma separação de oráculo entre as classes de complexidade BQP e BPP.
Enunciado do problema Dado um oráculo que implementa uma função na qual é prometido que é o produto escalar entre e uma string secreta módulo 2, , encontre .
Algoritmo
Classicamente, o método mais eficiente para encontrar a string secreta é avaliar a função vezes com os valores de entrada para todos :
Em contraste com a solução clássica, que precisa de pelo menos consultas à função para encontrar , apenas uma consulta é necessária usando computação quântica. O algoritmo quântico é o seguinte:
Aplique uma transformada de Hadamard ao estado de qubits para obter
Em seguida, aplique o oráculo que transforma . Isto pode ser simulado através do oráculo padrão que transforma aplicando este oráculo a . ( denota adição módulo dois.) Isto transforma a superposição em
Outra transformada de Hadamard é aplicada a cada qubit, o que faz com que, para qubits onde , seu estado seja convertido de para e, para qubits onde , seu estado seja convertido de para . Para obter , é realizada uma medição na base computacional () dos qubits.
Graficamente, o algoritmo pode ser representado pelo seguinte diagrama, onde denota a transformada de Hadamard em qubits:
A razão pela qual o último estado é é porque, para um determinado ,
Uma vez que é verdadeiro apenas quando , isso significa que a única amplitude não nula está em . Portanto, medir a saída do circuito na base computacional produz a string secreta .
Uma generalização do problema de Bernstein–Vazirani foi proposta, envolvendo encontrar uma ou mais chaves secretas usando um oráculo probabilístico. Este é um problema interessante para o qual um algoritmo quântico pode fornecer soluções eficientes com certeza ou com um alto grau de confiança, enquanto algoritmos clássicos falham completamente em resolver o problema no caso geral.
Complexidade clássica vs. quântica
O problema de Bernstein-Vazirani é geralmente apresentado em sua versão não-decisão. Nesta forma, é um exemplo de problema solucionável por uma Máquina de Turing quântica (QTM) com consultas ao oráculo do problema, mas para o qual qualquer algoritmo de Máquina de Turing probabilística (PTM) deve fazer consultas.
Para fornecer uma separação entre BQP e BPP, o problema deve ser remodelado em um problema de decisão (já que essas classes de complexidade se referem a problemas de decisão). Isso é realizado com uma construção recursiva e a inclusão de um segundo oráculo aleatório. O problema de decisão resultante é solucionável por uma QTM com consultas ao oráculo do problema, enquanto uma PTM deve fazer consultas para resolver o mesmo problema. Portanto, Bernstein-Vazirani fornece uma separação super-polinomial entre BPP e BQP.
Implementação do algoritmo Bernstein-Vazirani em Qiskit O circuito quântico mostrado aqui é de um exemplo simples de como o algoritmo de Bernstein-Vazirani pode ser implementado em Python usando Qiskit, uma estrutura de desenvolvimento de software de computação quântica de código aberto da IBM.
thumb|Circuito quântico de Bernstein-Vazirani
Ver também Problema da função linear oculta Problema de Simon
Referências
Categoria:Algoritmos quânticos Categoria:Teoria da complexidade quântica Categoria:Teoria da complexidade computacional