Caminata Aleatoria Cuántica

Clásico vs cuántico: misma caminata, propagación radicalmente diferente

Ejemplo resuelto — Caminata Aleatoria Cuántica

Ratio cuántico/clásico	2.0775×
Pico cuántico	0.2816

Estos son los valores que muestra la calculadora al abrir la página. Cambia cualquier entrada de arriba para recalcularlos.

Cargando simulación interactiva...

De caminatas aleatorias a búsqueda cuántica 🖖

La aceleración cuadrática de la caminata cuántica proviene de la interferencia, no de la probabilidad. En cada paso, la puerta de Hadamard coloca la moneda en superposición, de modo que el operador de desplazamiento mueve la amplitud hacia la izquierda y la derecha simultáneamente. Tras muchos pasos, la amplitud cerca del centro se cancela —las contribuciones que se mueven a la izquierda y a la derecha llegan con fases opuestas—, mientras que la amplitud cerca de ±N/√2 se refuerza constructivamente. Por eso la distribución presenta picos en los extremos en lugar de en el centro. El mismo mecanismo impulsa la búsqueda de Grover (una caminata sobre un hipercubo) y el recorrido de grafos con aceleración exponencial de Childs: las caminatas cuánticas alcanzan nodos lejanos mucho más rápido que cualquier proceso difusivo.

difusión frente a un sprint balístico 🖖

Un paseo aleatorio no es más que lanzar una moneda una y otra vez: cara, un paso a la derecha; cruz, a la izquierda. En la versión clásica los pasos se difuminan en una campana de Gauss; tras 100 lanzamientos rara vez acabas a más de unas 10 posiciones del inicio, porque la dispersión crece como √N. Cambia la moneda por una cuántica y el caminante deja de promediarse: se dispara hacia fuera y alcanza unas ~70 posiciones tras esos mismos 100 pasos. Los físicos lo llaman propagación balística: crece linealmente con N, no como su raíz cuadrada.

un paseo cuántico nunca olvida 🖖

Un paseo aleatorio clásico es un proceso de Markov: pierde poco a poco el rastro de dónde empezó, y solo con la nube final no puedes reconstruir el punto de partida. El paseo cuántico es unitario, así que cada paso es perfectamente reversible. Ejecuta hacia atrás la secuencia exacta de Hadamard y desplazamiento y toda esa amplitud dispersa vuelve a converger en un único pico en el origen: no se pierde información, y el paseo no tiene ninguna distribución de equilibrio a la que relajarse. La difusión borra la historia; un paseo cuántico solo la esconde.

Problema resuelto al detalle

Dispersiones para 2 caminantes en 10 pasos 9 pasos
10 pasos, 2 caminantes. Uno lanza una moneda justa en cada paso y se mueve ±1. El otro comienza en el estado de moneda |0⟩ y se le aplica la puerta de Hadamard a su moneda antes de cada movimiento. Calcula ambas dispersiones exactamente y, a continuación, indica cuántos pasos necesita el caminante clásico para recorrer el mismo terreno.
1. Los pasos clásicos son independientes y cada uno aporta una varianza de exactamente 1, por lo que las varianzas se suman. Esa única línea es toda la respuesta clásica, y por eso el panel superior muestra una raíz cuadrada en lugar de una simulación.
  
  $σ_{c}^{2} = 10 1 + 1 + \dots + 1 = 10 ⟹ σ_{c} = 10 = 3.1623$
2. El caminante cuántico nunca elige una rama. Mantén 2 amplitudes en cada sitio, una por cada valor de la moneda; la Hadamard las reemplaza por su suma y su diferencia, y después la mitad |0⟩ se mueve a la izquierda mientras que la mitad |1⟩ se mueve a la derecha. Un sitio puede recibir desde ambos vecinos, de modo que las amplitudes se suman, y una diferencia puede resultar 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. Empieza en el origen con (1, 0) y ejecuta 2 pasos. Extrae el factor 1/√2 de cada paso y las amplitudes seguirán siendo números enteros, por lo que tras el paso n todos los pares siguientes quedan 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. En el paso 3 es donde la simetría desaparece. El sitio en el origen contiene (1, 1): envía 1 + 1 = 2 hacia la izquierda y 1 − 1 = 0 hacia la derecha. El signo menos de la fila inferior de la Hadamard ha borrado toda la contribución hacia la derecha de ese sitio, y x = −1 pasa a tener 5 veces la probabilidad 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. Continúa calculando hasta el paso 10. Las amplitudes siguen siendo números enteros divididos por 2⁵, por lo que cada probabilidad es un número entero partido por 1024; los 11 numeradores siguientes son exactos y suman 1024.
  
  $n = 10 : 1024 p (x) = 1, 82, 449, 64, 100, 72, 52, 64, 89, 50, 1 (x = - 10, - 8, \dots, + 10)$
6. Lee el numerador más grande directamente de la lista. Es 449 y se sitúa en x = −6, bastante lejos tanto del origen como del extremo opuesto.
  
  $x max p_{q} (x) = p_{q} (- 6) = \frac{449}{1024} = 0.4385$
7. La media no es 0. |0⟩ es la mitad de la moneda que se mueve hacia la izquierda, y el paso 3 ya mostró que se llevaba la mayor parte, de modo que toda la distribución se inclina hacia ese lado.
  
  $μ = x \sum x p (x) = - \frac{2512}{1024} = - 2.4531$
8. La varianza es la media del cuadrado menos el cuadrado de la media, y ambas sumas provienen de los mismos 11 numeradores; no se necesita nueva información.
  
  $σ_{q}^{2} = x \sum x^{2} p (x) - μ^{2} = \frac{30672}{1024} - 6.0177 = 23.935 ⟹ σ_{q} = 4.8924$
9. Divide por la dispersión clásica del paso 1.
  
  $\frac{σ _{q}}{σ _{c}} = \frac{4.8924}{3.1623} = 1.5471$
Respuesta

σ_q = 4,8924 frente a σ_c = 3,1623 —una proporción de 1,5471— con el pico cuántico en p_q(−6) = 0,4385. Ahora interpreta esa varianza como un número de pasos. La dispersión de un caminante clásico es √M, por lo que igualar 4,8924 requiere M = σ_q² = 23,9, digamos 24 pasos: 2,4 veces el trabajo para el mismo alcance tras 10. El número de pasos clásico es el cuadrado de la razón de dispersión, y esa es la parte que conviene recordar: una ventaja de 2× en dispersión es una ventaja de 4× en pasos.

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

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

Por el equipo de 42Math · Actualizado 2026-05-22

Contrastado con fuentes publicadas. Se agradecen correcciones. Política editorial · Correcciones

Todas las lecciones de Informática →

Problemas de ejemplo

10 pasos - 10 pasos: ya se ven dos picos asimétricos
30 pasos - 30 pasos: la dispersión cuántica es mucho más amplia que la clásica
50 pasos - 50 pasos: dispersión cuántica O(N) frente a O(√N) clásica
Moneda equilibrada - 20 pasos, moneda equilibrada: distribución simétrica de dos picos