Algoritmo de Bernstein–Vazirani

Dado um oráculo que implementa uma função f : { 0 , 1 } n → { 0 , 1 } {\displaystyle f\colon \{0,1\}^{n}\rightarrow \{0,1\}} na qual é prometido que f ( x ) {\displaystyle f(x)} é o produto escalar entre x {\displaystyle x} e uma string secreta s ∈ { 0 , 1 } n {\displaystyle s\in \{0,1\}^{n}} módulo 2, f ( x ) = x ⋅ s = x 1 s 1 ⊕ x 2 s 2 ⊕ ⋯ ⊕ x n s n {\displaystyle f(x)=x\cdot s=x_{1}s_{1}\oplus x_{2}s_{2}\oplus \cdots \oplus x_{n}s_{n}} , encontre s {\displaystyle s} .

Classicamente, o método mais eficiente para encontrar a string secreta é avaliar a função n {\displaystyle n} vezes com os valores de entrada x = 2 i {\displaystyle x=2^{i}} para todos i ∈ { 0 , 1 , … , n − 1 } {\displaystyle i\in \{0,1,\dots ,n-1\}} : Em contraste com a solução clássica, que precisa de pelo menos n {\displaystyle n} consultas à função para encontrar s {\displaystyle s} , apenas uma consulta é necessária usando computação quântica. O algoritmo quântico é o seguinte: Aplique uma transformada de Hadamard ao estado de n {\displaystyle n} qubits | 0 ⟩ ⊗ n {\displaystyle |0\rangle ^{\otimes n}} para obter Em seguida, aplique o oráculo U f {\displaystyle U_{f}} que transforma | x ⟩ → ( − 1 ) f ( x ) | x ⟩ {\displaystyle |x\rangle \to (-1)^{f(x)}|x\rangle } . Isto pode ser simulado através do oráculo padrão que transforma | b ⟩ | x ⟩ → | b ⊕ f ( x ) ⟩ | x ⟩ {\displaystyle |b\rangle |x\rangle \to |b\oplus f(x)\rangle |x\rangle } aplicando este oráculo a | 0 ⟩ − | 1 ⟩ 2 | x ⟩ {\displaystyle {\frac {|0\rangle -|1\rangle }{\sqrt {2}}}|x\rangle } . ( ⊕ {\displaystyle \oplus } denota adição módulo dois.) Isto transforma a superposição em

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 O ( 1 ) {\displaystyle O(1)} consultas ao oráculo do problema, mas para o qual qualquer algoritmo de Máquina de Turing probabilística (PTM) deve fazer Ω ( n ) {\displaystyle \Omega (n)} 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 O ( n ) {\displaystyle O(n)} consultas ao oráculo do problema, enquanto uma PTM deve fazer Ω ( n log ⁡ n ) {\displaystyle \Omega (n^{\log n})} consultas para resolver o mesmo problema. Portanto, Bernstein-Vazirani fornece uma separação super-polinomial entre BPP e BQP.

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.