2025/11/11 by Marco Radaelli, Radaelli, Marco, Claudia Benedetti +3
Biochemistry, Genetics and Molecular Biology · Computer Science · #Convergence of random variables #Convolution (computer science) #DNA and Biological Computing #Ergodic theory #FOS: Physical sciences #Iterated function #Position (finance) #Quantum #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Quantum walk #Quantum-Dot Cellular Automata #Random walk #Sequence (biology)
paper · pdf · doi:10.48550/arxiv.2511.08293
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2025/11/11 · openalex created_date 2025/11/13 · openalex updated_date 2026/07/28
We investigate the use of discrete-time quantum walks to sample from an almost-uniform distribution, in the absence of any external source of randomness. Integers are encoded on the vertices of a cycle graph, and a quantum walker evolves for a fixed number of steps before its position is measured and recorded. The walker is then reset to the measured site, and the procedure is iterated to produce the sequence of random numbers. We show that when the quantum walk parameters, such as the coin operator and initial state, satisfy the conditions of the ergodic theorem for random walks on finite groups, the resulting sequence converges asymptotically to the uniform distribution. Although correlations between successive outcomes are unavoidable, they can be significantly reduced by a suitable choice of the evolution time. By analyzing the iterated convolution of the quantum walk transition probability and exploiting the ergodic theorem, we demonstrate convergence of the marginal distributions toward the uniform distribution in the asymptotic limit.