Laboratório · Bernstein–Vazirani

O algoritmo Bernstein-Vazirani

Escolha o segredo s, avance passo a passo e veja as 8 amplitudes de |x⟩ evoluírem sob Hadamard → oráculo → Hadamard até uma consulta bastar para descobri-lo.

Autor Paulo H. Bruce

Revisão técnica Prof. Dr. Júlio César da Silva em revisão

Antes de começar · roteiro editorial

Roteiro guiado do zero ao Bernstein-Vazirani em 10 paradas

Primeiro contato com algoritmo quântico? Comece por aqui. Cada parada é um mini-capítulo autocontido. Leia o resumo, expanda pro conteúdo estendido se quiser aprofundar. Concluídas as 10, o vocabulário e a intuição estão prontos pra navegar o resto da página sem tropeçar em notação.

Expandir roteiro completo · 10 paradas Colapsar roteiro

01
O problema em uma frase

~2 mindefinição

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.

Aprofundar

A caixa carrega uma única promessa. Dado um x, devolve f(x) = s · x (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.
02
O que é o oráculo

~2 minmodelo de custo

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.

Aprofundar

Formalmente, Uf é uma porta unitária (reversível) que age como |x⟩|y⟩ → |x⟩|y ⊕ 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.
03
Clássico versus quântico

~3 minseparação

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

Aprofundar

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 ε < 1/2, você precisa de pelo menos Ω(n) queries¹. Aleatoriedade não salva. A vantagem quântica de n → 1 é separação linear em queries. Se considerarmos "informação extraída por chamada", exponencial em recursos totais.
04
Símbolos e notação

~3 minglossário

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 um tem uma leitura em voz alta.

Aprofundar

|0⟩ "ket zero", qubit no estado zero. |1⟩ "ket um", qubit no estado um. |ψ⟩ "ket psi", nome genérico de estado quântico. ⟨ψ| "bra psi", dual do ket, útil para produtos internos.

⊗ tensor, empilha dois sistemas quânticos num só. ⊕ XOR bit a bit. 1/√2 aparece como amplitude de superposições balanceadas. H = Hadamard, cria superposição uniforme. X = Pauli-X, o NOT quântico. U_f = oráculo.

Para a lista completa com exemplos em código, o Glossário de Notações Matemáticas do vault cobre o vocabulário inteiro do curso: ITQ, ACC e ALC.
05
Como ler o painel de ondas

~2 minvisualização

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

Aprofundar

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 clicar em próximo 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.
06
Recuo de fase, o coração do algoritmo

~4 minmecanismo central

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

Aprofundar

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³.

A metáfora é coice de arma. A bala sai (a ancila age), mas a força volta para o ombro do atirador (a fase reflui para o registrador de entrada). Sem esse mecanismo, o oráculo só escreveria bits na ancila e o algoritmo colapsaria em algo trivial. Toda a vantagem quântica de BV vive nesse instante. Daí o nome do fenômeno: recuo de fase, ou phase kickback em inglês.
07
O circuito quântico como notação padrão

~3 mindiagrama

Adiante, 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.

Aprofundar

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.
08
Cada qubit na esfera de Bloch

~4 minseparabilidade

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.

Aprofundar

Trajetória de cada qubit da entrada: |0⟩ (polo norte) → H → |+⟩ (eixo +x) → oráculo → |+⟩ ou |−⟩ (eixo ±x, dependendo do bit de s) → H → |0⟩ ou |1⟩. O qubit i termina exatamente em |s_i⟩.

Isso é raro. Algoritmos quânticos normalmente criam entrelaçamento denso e nenhum qubit individual carrega informação (pense em Grover, Shor, teleporte)⁴. Em BV, a estrutura de produto interno faz com que as fases se distribuam de forma separável. Parte de por que BV é o algoritmo mais didático da área.
09
Interferência final

~3 minWalsh–Hadamard

O Hadamard final é a Transformada de Walsh–Hadamard, versão discreta de Fourier sobre Z₂ⁿ. Ela interfere todas as fases carimbadas pelo oráculo.

Aprofundar

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

Metáfora óptica: interferômetro com 2ⁿ fendas em que as fases estão configuradas para que apenas uma saída detecte luz. Todas as outras têm ondas que se anulam exatamente. A borboleta da FWHT (Fast Walsh–Hadamard Transform) é essa mesma operação, o padrão que aparece em códigos de Hamming e processamento de sinais⁵.
10
Contexto histórico e por que importa

~4 min1993 · STOC

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)⁷.

Aprofundar

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 Z₂ⁿ; 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^⊗n → U_f → H^⊗n) e obtém separação exponencial em queries⁶. Poucos meses adiante, Shor generaliza a QFT de Z₂ⁿ para Z_N. Nasce o algoritmo de fatoração que motivaria a criptografia pós-quântica⁹.

Cadeia formal de contenções: P ⊆ BPP ⊆ BQP ⊆ PP ⊆ PSPACE. BV é o primeiro teste de que essas inclusões não colapsam¹. Umesh Vazirani recebeu o Turing Award em 2024 por essa e outras contribuições posteriores.

Dica de leitura. Não é preciso expandir todas as paradas na primeira passada. Leia os 10 resumos em sequência para formar uma imagem mental do pipeline completo. Depois volte e aprofunde as paradas onde ainda tiver dúvida. As seções interativas abaixo já assumem que você tem esse mapa.

0estado inicial 1H^⊗n 2U_f (oráculo) 3H^⊗n 4medição

segredo s

Antes de olhar as 8 ondas · registrador × amplitude

Registrador é hardware, qubits físicos que você toca. O BV tem 2 registradores: o principal (3 qubits) e a ancila (1 qubit). Total de 4 qubits.

Amplitude é a descrição matemática do estado do registrador, um número complexo por configuração possível. Um registrador de n qubits tem 2ⁿ amplitudes⁴.

Registrador principal (3 qubits) = 8 amplitudes. São essas as 8 linhas empilhadas na animação a seguir. A ancila (1 qubit) = 2 amplitudes, mostrada à direita como o par (+|0⟩ − |1⟩)/√2 = |−⟩.

Superposição · soma coerente

Interferência das amplitudes

As 8 amplitudes vistas no mesmo eixo. A curva dourada em brilho é a soma coerente, o que restaria se cada amplitude fosse uma onda física real emergindo do mesmo ponto.

espaço

fase +

fase −

soma coerente

Notação padrão · diagrama de circuito

O mesmo processo em circuito

Cada linha é um qubit ao longo do tempo. Portas atuam da esquerda pra direita.

preparação medição REGISTRADOR PRINCIPAL 3 qubits \cdot 8 amps ANCILA 1 qubit \cdot 2 amps TEMPO \to preparação H\otimesn Uf H\otimesn medição |0⟩ |0⟩ |0⟩ |0⟩ REGISTRADOR PRINCIPAL ANCILA H H H H X H H H (descartada) s₀ s₁ s₂

portas H e oráculo Uf

pulso de estado (ancila e qubits principais)

medição · saída clássica

(rosé reservado para amplitude negativa nas ondas)

Estrutura matemática exata · Butterfly FWHT

O Hadamard visto por dentro

FWHT é a sigla de Fast Walsh–Hadamard Transform — o algoritmo que decompõe H⊗n em n estágios sequenciais de O(N) operações, análogo à FFT (Fast Fourier Transform) mas sobre a base Z₂ⁿ. Cada estágio mistura pares de amplitudes com (a+b)/√2 e (a−b)/√2. Aqui aparecem os 3 estágios para 3 qubits, um por qubit — é assim que um circuito quântico implementa H⊗n.

Cada estágio mistura os pares que diferem só no bit indicado entrada após H no bit 0 após H no bit 1 após H no bit 2 (bit 0 = LSB) (bit 1 = meio) (bit 2 = MSB)

Como ler este diagrama

1 Cada coluna é um instante no tempo

Da esquerda pra direita: entrada → 3 aplicações de H → saída. O Hadamard acontece em 3 estágios, um por qubit.
2 Cada linha horizontal é um estado

|000⟩ em cima, |111⟩ embaixo. Cada linha traça a evolução da amplitude daquele estado nos estágios sucessivos.
3 Cada bolinha é uma amplitude

Dourado = valor positivo, rosé = negativo, círculo vazio = zero.
Tamanho da bolinha = magnitude do valor. Número dentro = valor exato.
4 Cada estágio junta pares específicos

H no bit 0 junta pares que diferem só no bit menos significativo:
(|000⟩,|001⟩) · (|010⟩,|011⟩) · (|100⟩,|101⟩) · (|110⟩,|111⟩)
H no bit 1 junta pares que diferem só no bit do meio:
(|000⟩,|010⟩) · (|001⟩,|011⟩) · (|100⟩,|110⟩) · (|101⟩,|111⟩)
H no bit 2 junta pares que diferem só no bit mais significativo:
(|000⟩,|100⟩) · (|001⟩,|101⟩) · (|010⟩,|110⟩) · (|011⟩,|111⟩)
5 A regra que age em cada par

Se um par tem valores (a, b) num estágio, no próximo eles viram:
nova bolinha do índice menor = (a + b) / √2
nova bolinha do índice maior = (a − b) / √2

Exemplo. Par (+0.35, −0.35) vira (0, +0.50). A soma cancela, a diferença dobra.
6 Por que só uma bolinha sobrevive no fim

Em cada estágio, pares com mesmo sinal se somam (crescem) e pares com sinais opostos se cancelam. Depois de 3 estágios, a maioria dos caminhos cancela e só o caminho que corresponde a |s⟩ acumula tudo em +1.00.
7 Em que linha o resultado vai parar

Cada par tem uma bolinha de cima (índice menor) e uma de baixo (índice maior). A operação é fixa:

bolinha em cima = (a + b) / √2
bolinha embaixo = (a − b) / √2
Regra visual rápida:
· Cores iguais (dourado+dourado ou rosé+rosé) → resultado fica em cima
· Cores diferentes (dourado+rosé) → resultado fica embaixo
8 Por que algumas linhas atravessam bolinhas vazias

A distância entre os elementos do par dobra a cada estágio (bit 0 → distância 1, bit 1 → distância 2, bit 2 → distância 4). Então:
Estágio 1: pares vizinhos, linhas curtas.
Estágio 2: pares separados por 1 linha, a conexão cruza essa linha do meio.
Estágio 3: pares separados por 3 linhas, a conexão cruza 3 linhas intermediárias.
Quanto mais adiante o estágio, mais inclinadas ficam as linhas.

Interferência · fenda óctupla quântica

Ondas interferindo

Analogia com a fenda dupla de Young, mas com 8 fontes. Cada fonte carrega a fase (−1)^s·x. Escolha o formato (linear ou radial) e veja onde as ondas se somam ou se cancelam.

Hardware físico

Cada fonte é uma amplitude α_x do registrador conjunto (não um qubit individual). O tamanho reflete |α_x|, a cor reflete o sinal.

As 8 amplitudes abaixo descrevem o estado conjunto dos 4 qubits físicos acima. O substrato pode ser qualquer tecnologia (transmon supercondutor, íon aprisionado, fóton). A matemática das amplitudes e a interferência resultante são invariantes¹⁰.

Esfera de Bloch · estado de cada qubit

Trajetória de cada qubit na esfera de Bloch

Detalhe raro do BV. Cada qubit permanece sempre em estado puro, nunca fica emaranhado. Cada um percorre uma rota própria.

qubit 0 (principal · s₀)

|0⟩

qubit 1 (principal · s₁)

|0⟩

qubit 2 (principal · s₂)

|0⟩

ancila (recuo de fase)

|1⟩

Física do hardware · rotações reais

Anatomia de uma porta quântica

Portas quânticas não são operações instantâneas. Cada uma é um pulso eletromagnético que faz o qubit girar continuamente na esfera de Bloch¹¹. Escolha uma porta e veja a rotação real.

P(|0⟩) em gold, P(|1⟩) em rose. A oscilação entre as duas é a oscilação de Rabi.

Hardware · pulso ressonante

Onde a porta acontece no chip

No hardware real, uma porta é um pulso de micro-ondas na frequência de ressonância do qubit. O sistema absorve energia e oscila entre os dois níveis. Isso é uma oscilação de Rabi¹¹.

Analogia. Átomo absorvendo fóton na frequência exata da transição eletrônica. O elétron oscila entre orbital fundamental e excitado. Em supercondutores (transmon), o mesmo princípio com micro-ondas em vez de fótons visíveis¹¹.

Analogia mecânica · ressonância clássica

A mesma matemática, em ondas mecânicas

Um oscilador só absorve energia com eficiência quando é chutado na frequência natural dele. Fora dessa frequência, o chute passa e quase nada acontece. Ajuste a frequência do driver e veja o receptor responder ou ignorar. Este mesmo mecanismo é o que faz um pulso de micro-onda excitar um transmon: só se a frequência bater com ω₀₁.

frequência do driver ω = 1.00 ω₀

Paralelo com o pulso quântico. A amplitude que cresce aqui quando o driver bate na frequência natural é matematicamente a mesma da oscilação de Rabi. Trocando "peso na mola" por "estado do qubit" e "amplitude mecânica" por "amplitude quântica de |1⟩", você tem o mecanismo Rabi. Ressonância é universal.

Como cruzar circuito × animação

Cada coluna vertical do circuito corresponde a um passo da animação:

H^⊗n (esquerda) → passo 1 · superposição
U_f (meio) → passo 2 · coice
H^⊗n (direita) → passo 3 · interferência
medição → passo 4 · lemos s = s₀s₁s₂

A ancila não recebe o Hadamard final nem é medida. Cumpriu o papel de habilitar o coice e é descartada. Todo o resultado sai pelo registrador principal.

próximos passos

A cascata continua

Simon (1994)⁶ generaliza o mesmo sanduíche H^⊗n → U_f → H^⊗n e obtém separação exponencial em queries. No mesmo ano, Shor pega esse esqueleto, troca a Walsh–Hadamard pela QFT sobre Z_N e transforma fatoração em problema polinomial⁹. Dois anos depois, Grover (1996)³ reutiliza o recuo de fase para busca não-estruturada.

Referências

Bernstein, E.; Vazirani, U. (1993). Quantum Complexity Theory. Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC), pp. 11-20. doi:10.1145/167088.167097.
Deutsch, D.; Jozsa, R. (1992). Rapid Solution of Problems by Quantum Computation. Proceedings of the Royal Society A, 439(1907), pp. 553-558. doi:10.1098/rspa.1992.0167.
Grover, L. K. (1996). A Fast Quantum Mechanical Algorithm for Database Search. Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC), pp. 212-219. doi:10.1145/237814.237866.
Nielsen, M. A.; Chuang, I. L. (2010). Quantum Computation and Quantum Information, 10th Anniversary Edition. Cambridge University Press. ISBN 978-1107002173.
MacWilliams, F. J.; Sloane, N. J. A. (1977). The Theory of Error-Correcting Codes. North-Holland, Amsterdam. Cap. 14 sobre Walsh-Hadamard, códigos de Reed-Muller e Hamming.
Simon, D. R. (1994). On the Power of Quantum Computation. Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS), pp. 116-123. doi:10.1109/SFCS.1994.365701. Versão jornal: SIAM J. Comput. 26(5), 1474-1483, 1997.
Shor, P. W. (1994). Algorithms for Quantum Computation: Discrete Logarithms and Factoring. Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS), pp. 124-134. doi:10.1109/SFCS.1994.365700.
Deutsch, D. (1985). Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer. Proceedings of the Royal Society A, 400(1818), pp. 97-117. doi:10.1098/rspa.1985.0070.
Shor, P. W. (1997). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing, 26(5), pp. 1484-1509. doi:10.1137/S0097539795293172.
Ladd, T. D.; Jelezko, F.; Laflamme, R.; Nakamura, Y.; Monroe, C.; O'Brien, J. L. (2010). Quantum computers. Nature, 464(7285), pp. 45-53. doi:10.1038/nature08812.
Krantz, P.; Kjaergaard, M.; Yan, F.; Orlando, T. P.; Gustavsson, S.; Oliver, W. D. (2019). A Quantum Engineer's Guide to Superconducting Qubits. Applied Physics Reviews, 6(2), 021318. doi:10.1063/1.5089550.

Discussão

Comentários

Compartilhe dúvidas, correções ou observações. Só quem tá logado consegue escrever, mas qualquer visitante lê.

O algoritmo Bernstein-Vazirani

Roteiro guiado do zero ao Bernstein-Vazirani em 10 paradas

O problema em uma frase

O que é o oráculo

Clássico versus quântico

Símbolos e notação

Como ler o painel de ondas

Recuo de fase, o coração do algoritmo

O circuito quântico como notação padrão

Cada qubit na esfera de Bloch

Interferência final

Contexto histórico e por que importa