Uma string secreta $s$ de $n$ bits está escondida dentro de uma caixa-preta, o oráculo. Sua missão é descobrir todos os bits de $s$ fazendo o menor número possível de perguntas.

A caixa carrega uma única promessa: dado um $x$, devolve $f(x)=s\cdot x(\mathrm{mod}2)$, o produto interno bit a bit entre $s$ e $x$ colapsado num único bit (par → 0, ímpar → 1). Cada consulta custa uma query, unidade fundamental do modelo de query complexity em que Bernstein e Vazirani formularam o problema em 1993.

A pergunta central é econômica, não algorítmica: quantas consultas até recuperar $s$? A resposta clássica é linear em $n$. A resposta quântica é exatamente 1. Essa separação motiva toda a página.

Oráculo é caixa-preta. Você não pode abrir e ler $s$ diretamente, só fazer perguntas na forma de estados de entrada e observar a resposta. Uma consulta por chamada.

Formalmente, $U_f$ é uma porta unitária (reversível) que age como $|x⟩|y⟩\to |x⟩|y\oplus f(x)⟩$. Preserva o registrador de entrada e combina a ancila $y$ com $f(x)$ via XOR. Nenhum custo interno é contabilizado, só o número de invocações.

É o mesmo modelo em que vivem Deutsch-Jozsa (função constante ou balanceada?), Grover (busca desordenada) e Simon (período escondido). O que muda entre eles é a estrutura da função escondida. A definição de query segue igual.

Clássico determinístico precisa de $n$ consultas (uma por bit). Clássico probabilístico também precisa de $\Omega (n)$. Quântico exige 1 consulta, resultado exato com probabilidade 1.

A prova clássica é elementar: consulte $f(e_i)$ com $e_i$ sendo a string com 1 só na posição $i$ e você obtém $s_i$ imediatamente. $n$ queries e pronto.

A prova de otimalidade probabilística é teoria da informação: cada query devolve 1 bit. Para recuperar $n$ bits com erro $\epsilon <1/2$, você precisa de pelo menos $\Omega (n)$ queries. Aleatoriedade não salva. A vantagem quântica de $n\to 1$ é separação linear em queries. Se considerarmos informação extraída por chamada, exponencial em recursos totais.

Mini-dicionário para não tropeçar em notação. Se um símbolo aparecer sem tradução mais adiante, procure aqui primeiro.

Cada linha do painel é um estado da base computacional, de $|000⟩$ até $|111⟩$. A onda desenhada em cima é a amplitude. Altura é magnitude, cor é sinal.

Dourado quente = amplitude positiva. Rosé = amplitude negativa. Cinza-terroso = amplitude zero. A onda oscila no tempo só para dar textura visual. O que importa é a envoltória (altura da onda em relação à base) e a cor (sinal).

Ao avançar passo a passo, o painel congela cada etapa: estado inicial (só $|000⟩$ ativo), Hadamard (8 ondas de altura igual), oráculo (mesma altura, sinais trocados), Hadamard final (uma onda sobrevive), medição (colapso). Cada quadro é o mesmo objeto matemático que a álgebra descreve, renderizado como ondas em vez de somatório abstrato de kets.

A ancila, preparada em $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$, absorve a operação do oráculo. Mas o sinal $(-1{)}^{f(x)}$ é chutado de volta para o registrador principal.

Formalmente, $U_f|x⟩|-⟩=(-1{)}^{f(x)}|x⟩|-⟩$. A ancila fica inalterada. O registrador principal ganha uma fase relativa que carrega $f(x)$ em cada posição da diagonal. É o recuo de fase (phase kickback), o mesmo mecanismo que Grover usa para marcar o alvo da busca desordenada.

O mesmo processo aparece em diagrama de circuito: 3 fios do registrador principal + 1 fio da ancila, com portas atuando da esquerda para a direita: Hadamard, oráculo, Hadamard, medição.

Convenção universal. Cada linha horizontal é um qubit; o tempo corre à direita. Caixas $H$ são Hadamards paralelos. O oráculo $U_f$ é implementado como conjunto de CNOTs, uma controlada em cada posição onde $s$ tem bit 1, todas atuando na ancila. A ancila é descartada antes da medição.

Ler o circuito é traduzir sequência de operações unitárias. É o mesmo objeto matemático que o painel de ondas anima, só que comprimido e simbólico enquanto o outro é lento e visual. Ambos descrevem o mesmo estado a cada instante.

Bernstein-Vazirani é raro. Cada qubit se mantém em estado puro (sem entrelaçamento com os outros) durante toda a execução, e cada um revela um bit de $s$ de forma independente.

Trajetória de cada qubit da entrada: $|0⟩$ (polo norte) $\stackrel{H}{\to }$ $|+⟩$ (eixo +x) $\stackrel{\text{oraˊculo}}{\to }$ $|+⟩$ ou $|-⟩$ (eixo $\pm x$, dependendo do bit de $s$) $\stackrel{H}{\to }$ $|0⟩$ ou $|1⟩$. O qubit $i$ termina exatamente em $|s_i⟩$.

O Hadamard final é a Transformada de Walsh-Hadamard, versão discreta de Fourier sobre ${\mathbb{Z}}_2^n$. Ela interfere todas as fases carimbadas pelo oráculo.

Após o oráculo, o registrador é uma superposição uniforme com sinais $(-1{)}^{s\cdot x}$ distribuídos pelos $2^n$ estados. O segundo $H^{\otimes n}$ reorganiza essa nuvem de fases. Só a componente $|s⟩$ acumula amplitudes que se somam construtivamente. Todas as outras $2^n-1$ componentes cancelam por interferência destrutiva perfeita.

Bernstein e Vazirani apresentaram este algoritmo no STOC 1993, no artigo Quantum Complexity Theory, o mesmo que define formalmente a classe BQP. É o predecessor direto de Simon (1994) e Shor (1994).

O paper faz três coisas ao mesmo tempo: formaliza a Máquina de Turing Quântica que Deutsch esboçara em 1985; introduz a Transformada de Fourier Quântica sobre ${\mathbb{Z}}_2^n$; e apresenta o primeiro problema com separação provável (relativizada) entre BQP e BPP.

Um ano depois, Simon usa a mesma arquitetura de sanduíche ($H^{\otimes n}\to U_f\to H^{\otimes n}$) e obtém separação exponencial em queries. Poucos meses adiante, Shor generaliza a QFT de ${\mathbb{Z}}_2^n$ para ${\mathbb{Z}}_N$. Nasce o algoritmo de fatoração que motivaria a criptografia pós-quântica.