Passeio Aleatório Quântico

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.

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