Passeio Aleatório Quântico

Clássico vs quântico: mesmo passeio, propagação radicalmente diferente

Exemplo resolvido — Passeio Aleatório Quântico

Razão quântico/clássico	2.0775×
Pico quântico	0.2816

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

De passeios aleatórios à busca quântica 🖖

A aceleração quadrática do passeio quântico vem da interferência, não da probabilidade. A cada passo, a porta de Hadamard coloca a moeda em superposição, de modo que o operador de deslocamento move a amplitude para a esquerda e para a direita simultaneamente. Ao longo de muitos passos, a amplitude perto do centro se cancela — as contribuições que se movem para a esquerda e para a direita chegam com fases opostas —, enquanto a amplitude perto de ±N/√2 se reforça construtivamente. É por isso que a distribuição atinge picos nas extremidades em vez de no centro. O mesmo mecanismo impulsiona a busca de Grover (um passeio em um hipercubo) e o percurso de grafos com aceleração exponencial de Childs: os passeios quânticos alcançam nós distantes muito mais rápido do que qualquer processo difusivo conseguiria.

difusão contra um sprint balístico 🖖

Um passeio aleatório é apenas o lançamento repetido de uma moeda: cara, um passo à direita; coroa, um passo à esquerda. Na versão clássica os passos se dissolvem numa curva em sino — após 100 lançamentos raramente você termina a mais de cerca de 10 posições do início, pois a dispersão cresce como √N. Troque a moeda por uma moeda quântica e o caminhante deixa de se mediar: dispara para fora e alcança ~70 posições após esses mesmos 100 passos. Os físicos chamam isso de propagação balística: cresce linearmente com N, não como sua raiz quadrada.

um passeio quântico nunca esquece 🖖

Um passeio aleatório clássico é um processo de Markov: perde aos poucos o rastro de onde começou, e só com a nuvem final não dá para reconstruir o ponto de partida. O passeio quântico é unitário, portanto cada passo é perfeitamente reversível. Rode ao contrário a sequência exata de Hadamard e deslocamento e toda aquela amplitude espalhada volta a convergir num único pico na origem — nenhuma informação se perde, e o passeio não tem nenhuma distribuição de equilíbrio para a qual relaxar. A difusão apaga a história; um passeio quântico apenas a esconde.

Problema resolvido na íntegra

Dispersões para 2 caminhantes ao longo de 10 passos 9 passos
10 passos, 2 caminhantes. Um lança uma moeda equilibrada em cada passo e desloca-se ±1. O outro começa no estado de moeda |0⟩ e tem a porta de Hadamard aplicada à sua moeda antes de cada movimento. Calcule ambas as dispersões exatamente e, em seguida, determine de quantos passos o caminhante clássico precisa para cobrir a mesma distância.
1. Os passos clássicos são independentes e cada um contribui com uma variância de exatamente 1, pelo que as variâncias se somam. Essa única linha é toda a resposta clássica — e é a razão pela qual o painel acima apresenta uma raiz quadrada em vez de uma simulação.
  
  $σ_{c}^{2} = 10 1 + 1 + \dots + 1 = 10 ⟹ σ_{c} = 10 = 3.1623$
2. O caminhante quântico nunca escolhe um ramo. Mantêm-se 2 amplitudes em cada posição, uma por valor da moeda; a Hadamard substitui-as pela sua soma e pela sua diferença, e depois a metade |0⟩ move-se para a esquerda enquanto a metade |1⟩ se move para a direita. Uma posição pode receber de ambos os vizinhos, pelo que as amplitudes se somam — e uma diferença pode resultar em 0.
  
  $(a_{0}, a_{1})_{x} ⟶ \frac{a _{0} + a _{1}}{2} (1, 0)_{x - 1} + \frac{a _{0} - a _{1}}{2} (0, 1)_{x + 1}$
3. Comece na origem com (1, 0) e execute 2 passos. Extraia o fator 1/√2 de cada passo e as amplitudes mantêm-se como números inteiros, pelo que após o passo n os pares abaixo ficam todos divididos por 2^n/2.
  
  $n = 1 : (1, 0)_{- 1}, (0, 1)_{+ 1} n = 2 : (1, 0)_{- 2}, (1, 1)_{0}, (0, - 1)_{+ 2}$
4. O passo 3 é onde a simetria acaba. A posição na origem contém (1, 1): envia 1 + 1 = 2 para a esquerda e 1 − 1 = 0 para a direita. O sinal de menos na linha inferior da Hadamard eliminou a totalidade da contribuição dessa posição para a direita, e x = −1 passa a ter 5 vezes a probabilidade de x = +1.
  
  $n = 3 : (1, 0)_{- 3}, (2, 1)_{- 1}, (- 1, 0)_{+ 1}, (0, 1)_{+ 3} ⟹ p (- 1) = \frac{5}{8}, p (+ 1) = \frac{1}{8}$
5. Continue o processo até ao passo 10. As amplitudes continuam a ser números inteiros sobre 2⁵, pelo que cada probabilidade é um número inteiro sobre 1024 — os 11 numeradores abaixo são exatos e a sua soma é 1024.
  
  $n = 10 : 1024 p (x) = 1, 82, 449, 64, 100, 72, 52, 64, 89, 50, 1 (x = - 10, - 8, \dots, + 10)$
6. Leia o maior numerador diretamente da lista. É 449 e situa-se em x = −6, bem distante quer da origem quer da extremidade oposta.
  
  $x max p_{q} (x) = p_{q} (- 6) = \frac{449}{1024} = 0.4385$
7. A média não é 0. |0⟩ é a metade da moeda que se move para a esquerda e o passo 3 já mostrou que esta fica com a maior parte, pelo que toda a distribuição se inclina nessa direção.
  
  $μ = x \sum x p (x) = - \frac{2512}{1024} = - 2.4531$
8. A variância é a média dos quadrados menos o quadrado da média, e ambas as somas provêm dos mesmos 11 numeradores — não é necessária informação nova.
  
  $σ_{q}^{2} = x \sum x^{2} p (x) - μ^{2} = \frac{30672}{1024} - 6.0177 = 23.935 ⟹ σ_{q} = 4.8924$
9. Divida pela dispersão clássica do passo 1.
  
  $\frac{σ _{q}}{σ _{c}} = \frac{4.8924}{3.1623} = 1.5471$
Resposta

σ_q = 4,8924 contra σ_c = 3,1623 — uma razão de 1,5471 — com o pico quântico em p_q(−6) = 0,4385. Agora interprete essa variância como uma contagem de passos. A dispersão de um caminhante clássico é √M, pelo que igualar 4,8924 exige M = σ_q² = 23,9, digamos 24 passos: 2,4 vezes o trabalho para o mesmo alcance após 10. A contagem de passos clássica é o quadrado da razão de dispersão, e essa é a parte que vale a pena reter — uma vantagem de 2× na dispersão é uma vantagem de 4× nos passos.

$M = σ_{q}^{2} = 23.9 \approx 24, \frac{M}{N} = (\frac{σ _{q}}{σ _{c}})^{2} = 1.547 1^{2} = 2.394$

Referências (2)

Insight block 1 — the coined walk this tool steps through: Y. Aharonov, L. Davidovich and N. Zagury, "Quantum random walks." Physical Review A 48(2), 1687–1690, 1993.
And the exponential separation block 1 names: A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann and D. A. Spielman, "Exponential algorithmic speedup by a quantum walk." Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 59–68, 2003.

Pela equipa 42Math · Atualizado 2026-05-22

Verificado com fontes publicadas. Correções bem-vindas. Política editorial · Correções

Todas as lições de Computação →

Problemas de exemplo

10 passos - 10 passos — picos duplos assimétricos já visíveis
30 passos - 30 passos — dispersão quântica muito mais ampla que a clássica
50 passos - 50 passos — dispersão quântica O(N) vs. clássica O(√N)
Moeda equilibrada - 20 passos, moeda balanceada — distribuição simétrica com dois picos