Simulating discrete-time quantum walk with urn model

Surajit Saha · 2025

Read Simulating discrete-time quantum walk with urn model by Surajit Saha (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-06896.txt.

Introduction

Surajit Saha shows that a quantum walk can be mimed by plain balls in boxes, in a study from 2025. A quantum walk spreads a walker by wave rules and is used far and wide. Wave talk needs odd math; Saha asks if plain chance with chat among balls can fake the same flow.

His stage holds boxes in a row and a heap of balls. At each tick, balls hop by rules that lean on how full each box is. The hop odds are set by the coin and shift of the walk to be mimed. The ball spread then walks the quantum walk, step for step, sans any wave. The frame also grows a spin-like model of keen stuff. A bench-top rig could run it, Saha notes, which ties the quantum trick to plain stuff.

Catalog record

CREATORSurajit Saha
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE29 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-06896

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Simulating discrete-time quantum walk with urn model Surajit Saha Abstract Urn models have long been used to study stochastic processes, probability distributions, and reinforcement dynamics. Meanwhile, discrete time quantum walks (DTQW) serve as fundamental components in quantum computation and quantum information theory. This work explores a novel connection between an urn model and discrete-time quantum walks, focusing on how urn-based stochastic processes can provide insights into quantum state evolution and algorithmic behavior. Importantly, our model operates entirely with real-valued quantities, without relying on complex amplitudes of the quantum walk. Every stochastic rule is derived from urn-based processes, whose parameters are governed by the coin and shift mechanisms of the quantum walk, maintaining the structural dynamics of the QW. Through this interdisciplinary approach, we aim to bridge classical and quantum frameworks, offering new perspectives on both quantum algorithms and stochastic modeling. This work connects the urn model to the broad range of applications where DTQWs are successfully employed. Exploring the dynamics of a physical system often involves identifying suitably engineered dynamics in a potentially very different realm that exhibits analogous behavior. This approach not only enhances our understanding of the physical system but also enriches the dynamics of that different realm, making both perspectives more insightful and beneficial. A classic example emerged in 2002, when Grover’s quantum search algorithm was shown to correspond to the behavior of coupled pendulums grov1 . Recent work gog clarified this connection further. It showed that the dynamics of any classical system of harmonic oscillators can be equivalently understood as the dynamics of a corresponding quantum system of exponentially smaller size. Conversely, every quantum algorithm can be equivalently understood as the propagation of a classical wave in a system of coupled oscillators, albeit one that may involve action at a distance and significant classical resources, which make the latter process impractical. But the important point is that such an analogy led to the discovery of an efficient quantum algorithm to simulate the classical dynamics of coupled oscillators. This duality underscores the importance of systematically studying how useful classical systems—such as coupled oscillators, which can themselves simulate a wide variety of classical dynamics—can reflect the behavior of quantum algorithms. While such classical simulations might incur substantial computational costs or non-local characteristics, they can lead to the development of novel quantum algorithms for simulating intricate classical systems, as well as quantum-inspired classical strategies. In this spirit, we employ discrete-time quantum walks (DTQW) and construct an urn model as the corresponding useful classical system, offering a fresh route to replicate quantum dynamics. Quantum walks on graphs are one of the few established design strategies for quantum algorithms. Despite their simple description, quantum walks are extremely powerful, as they are universal for quantum computation love ; qwu . Owing to their non-classical spreading dynamics, localization property, and potential algorithmic advantages, quantum walks have been extensively explored both theoretically and experimentally Portugal2013 ; Kadian2021 ; Yuan2023 . On the other hand, Urn models—built on the simple act of drawing and replacing colored balls—serve as a versatile framework for modeling both random and self‑reinforcing dynamics across domains as varied as population genetics, network growth, statistical physics, and machine learning Godreche2002 ; Bellina2025 . Replicating quantum phenomena like DTQWs on useful classical platforms is inherently challenging. This difficulty stems from the fact that DTQWs rely on quantum superposition, where evolving states interfere—constructively or destructively—based on their relative phases. As a result, they produce probability distributions that differ from those of classical random walks. A line of research on this topic has approached this challenge by constructing classical random walks (CRWs) tomoki ; yama whose space and time-dependent transition probabilities in each step are extracted from the complex amplitudes of the DTQW. This approach yields a non-homogeneous CRW whose probability distribution replicates that of the corresponding DTQW. Although effective in reproducing certain statistics, these methods necessarily break the spatial and temporal structure of the DTQW and demand access to quantum amplitudes at each step, an approach analogous to Bohmian mechanics durr , where the quantum wave function guides particle trajectories. In contrast, alternative formulations of quantum mechanics—akin to the hydrodynamic approaches of Holland and Poirier holl ; poir ; parl ; shiff ; sebens ; wiseman —eschew direct reliance on the wave function, instead constructing real-valued fields or potentials that reproduce quantum evolution without amplitude-based guidance. Inspired by this distinction, we propose an urn‑model framework for simulating DTQWs that never invokes complex amplitudes. All transition rules arise from real‑valued urn processes whose parameters depend only on the QW’s coin and shift structure. Crucially, our model mirrors the structural properties of the original quantum walk system. When the QW has uniform coin and shift operations, our urn model remains homogeneous in space and time, employing identical urn parameters at each node and time step. If QW coin or shift operations vary across space or time, the corresponding urn model adapts its parameters in the same pattern, preserving the structural variations of QW. This yields two main advantages. First, preserving the structural variations of the QW simplifies both the analysis and the simulation, while allowing our method to be naturally extended to higher-dimensional graphs. Second, by avoiding amplitude-based guidance, the urn model brings into focus a fundamental probabilistic mechanism underlying quantum walk spreading and interference, insights that may carry foundational significance. To define the one-dimensional discrete-time quantum walk we require the coin Hilbert space \mathcal{H}_{c} and the position Hilbert space \mathcal{H}_{p} . The \mathcal{H}_{c} is spanned by the internal basis states of the particle, |0\rangle and |1\rangle , and the \mathcal{H}_{p} is spanned by the position basis states |n\rangle , n\in\mathbb{Z} . The total system is then in the space \mathcal{H}=\mathcal{H}_{c}\otimes\mathcal{H}_{p} . To implement a simple version of the quantum walk, known as the Hadamard walk, one applies the Hadamard operator H=\frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\[4.0pt] 1&-1\end{pmatrix} (1) on \mathcal{H}_{c} , which transforms a particle at the origin in one of the basis states into an equal superposition of \lvert 0\rangle and \lvert 1\rangle . Next, we perform the conditional shift S=\bigl(\lvert 0\rangle\langle 0\rvert\otimes\sum_{n=-\infty}^{\infty}\lvert n+1\rangle\langle n\rvert\bigr)+\bigl(\lvert 1\rangle\langle 1\rvert\otimes\sum_{n=-\infty}^{\infty}\lvert n-1\rangle\langle n\rvert\bigr). (2) A single step of the Hadamard quantum walk is thus W\;=\;S\bigl(H\otimes\mathbb{I}_{p}\bigr), (3) The process of W is iterated without resorting to the intermediate measurements to realize a large number of steps of the quantum walk. It has been demonstrated in cmc1 that a three-parameter SU(2) quantum coin operation, C(\xi,\theta,\zeta)=\begin{pmatrix}e^{i\xi}\cos\theta&e^{i\zeta}\sin\theta\\[6.0pt] -e^{-i\zeta}\sin\theta&e^{-i\xi}\cos\theta\end{pmatrix}, (4) is sufficient to describe the most general form of the discrete-time quantum walk, where \xi,\theta,\zeta\in\mathbb{R} and \theta\in[0,\pi/2] . By choosing different (\xi,\theta,\zeta) , one obtains a variety of discrete-time walks with distinct dynamical features. Consider a general single-qubit quantum state given by \lvert\psi\rangle=\psi_{0}\lvert 0\rangle+\psi_{1}\lvert 1\rangle. (5) Here, the complex amplitudes can be written as \psi_{0}=r_{0}e^{i\phi_{0}} and \psi_{1}=r_{1}e^{i\phi_{1}} . The probabilities of measuring the qubit in the computational basis states \lvert 0\rangle and \lvert 1\rangle are given by \displaystyle\begin{array}[]{rc}P_{0}=\mid\psi_{0}\mid^{2}=r_{0}^{2}\\ P_{1}=\mid\psi_{1}\mid^{2}=r_{1}^{2}\end{array} Applying the Hadamard gate to the state \lvert\psi\rangle transforms it as follows: \frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\ 1&-1\end{bmatrix}\begin{bmatrix}\psi_{0}\\ \psi_{1}\end{bmatrix}=\frac{1}{\sqrt{2}}\begin{bmatrix}\psi_{0}+\psi_{1}\\ \psi_{0}-\psi_{1}\end{bmatrix}=\begin{bmatrix}\psi_{0}^{\prime}\\ \psi_{1}^{\prime}\end{bmatrix} (8) Suppose \psi_{0}^{\prime}=r_{0}^{\prime}e^{i\phi_{0}^{\prime}} and \psi_{1}^{\prime}=r_{1}^{\prime}e^{i\phi_{1}^{\prime}} then one can write \displaystyle\begin{array}[]{rc}P_{0}^{\prime}={r_{0}^{\prime}}^{2}=\frac{1}{2}(r_{0}^{2}+r_{1}^{2}+2r_{0}r_{1}\cos(\phi_{0}-\phi_{1})),\\ P_{1}^{\prime}={r_{1}^{\prime}}^{2}=\frac{1}{2}(r_{0}^{2}+r_{1}^{2}-2r_{0}r_{1}\cos(\phi_{0}-\phi_{1})),\end{array} and \displaystyle\begin{array}[]{rc}\phi_{0}^{\prime}=\tan^{-1}\left(\frac{r_{0}\sin\phi_{0}+r_{1}\sin\phi_{1}}{r_{0}\cos\phi_{0}+r_{1}\cos\phi_{1}}\right),\\ \phi_{1}^{\prime}=\tan^{-1}\left(\frac{r_{0}\sin\phi_{0}-r_{1}\sin\phi_{1}}{r_{0}\cos\phi_{0}-r_{1}\cos\phi_{1}}\right).\end{array} Where P_{0}^{\prime} and P_{1}^{\prime} are resulting probabilities of measuring the transformed state in the computational basis. We now construct an urn model specifically designed to replicate the measurement

Read the complete text