A Quantum Algorithm for Random Number Generation

• URL: http://arxiv.org/abs/2606.13034v1
• Date: Thu, 11 Jun 2026 08:10:11 GMT
• Title: A Quantum Algorithm for Random Number Generation
• Abstract summary: We present a quantum algorithm for random number generation that achieves a provable quadratic speedup over classical Markov chain mixing.<n>The algorithm integrates three quantum primitives into a unified mixing circuit.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a quantum algorithm for random number generation that achieves a provable quadratic speedup over classical Markov chain mixing, building on the Diaconis-Shahshahani Fourier analysis of the top-to-random card shuffle. The algorithm integrates three quantum primitives into a unified mixing circuit: the Quantum Fourier Transform (QFT), which diagonalizes the Markov transition operator; controlled phase rotations, which encode the shuffle eigenvalue spectrum; and the Grover diffusion operator, which acts as a quantum analogue of the Aldous-Diaconis strong uniform stopping time by reflecting amplitudes about their mean at each iteration. For an n-qubit register, the mixing time is O(\sqrt{n \log n}) iterations. Extending to m qudits of local dimension d reduces this to O(\sqrt{\log_d N}) iterations, where N = d^m, compared to the classical O(n \log n) bound. The qudit formulation further reduces QFT circuit depth from O(\log^2 N) to O(\log_d^2 N) gates per layer by encoding the same N-state space using m = \log_d N subsystems instead of \log_2 N qubits. We validate both variants on IBM superconducting hardware.

Related papers

• Quantum-Inspired Algorithms beyond Unitary Circuits: the Laplace Transform [0.0]
  Quantum-inspired algorithms can deliver substantial speedups over classical state-of-the-art methods.<n>We introduce a tensor-network approach to compute the discrete Laplace transform, a non-unitary, aperiodic transform.<n>We demonstrate simulations up to $N=230$ input data points, with up to $260$ output data points, and quantify how bond dimension controls runtime and accuracy.
  arXiv  Detail & Related papers  (2026-01-25T07:19:56Z)
• Neural Guided Sampling for Quantum Circuit Optimization [26.90377134346014]
  Translating a quantum circuit on a specific hardware topology with a reduced set of available gates, also known as transpilation, comes with a substantial increase in the length of the equivalent circuit.<n>One method to address efficient transpilation is based on approaches known from optimization, e.g. by using random sampling and token replacement strategies.<n>Here, we propose in this work 2D neural guided sampling. Thus, given a 2D representation of a quantum circuit, a neural network predicts groups of gates in the quantum circuit, which are likely reducible.
  arXiv  Detail & Related papers  (2025-10-14T12:09:05Z)
• FFT-Accelerated Auxiliary Variable MCMC for Fermionic Lattice Models: A Determinant-Free Approach with $O(N\log N)$ Complexity [52.3171766248012]
  We introduce a Markov Chain Monte Carlo (MCMC) algorithm that dramatically accelerates the simulation of quantum many-body systems.<n>We validate our algorithm on benchmark quantum physics problems, accurately reproducing known theoretical results.<n>Our work provides a powerful tool for large-scale probabilistic inference and opens avenues for physics-inspired generative models.
  arXiv  Detail & Related papers  (2025-10-13T07:57:21Z)
• Sublinear Classical-to-Quantum Data Encoding using $n$-Toffoli Gates [3.0711566483997066]
  A common strategy is amplitude encoding, which embeds a classical input vector of size N=2textsuperscriptn in the amplitudes of an n-qubit register.<n>We propose a general-purpose procedure with sublinear average depth in N, increasing the window of utility.<n>Our amplitude encoding method encodes arbitrary complex vectors of size N=2textsuperscriptn at any desired binary precision using a register with n qubits plus 2 ancillas and a sublinear number of multi-controlled NOT (MCX) gates.
  arXiv  Detail & Related papers  (2025-05-09T13:49:16Z)
• Quantum Algorithms for Stochastic Differential Equations: A Schrödingerisation Approach [29.662683446339194]
  We propose quantum algorithms for linear differential equations.<n>The gate complexity of our algorithms exhibits an $mathcalO(dlog(Nd))$ dependence on the dimensions.<n>The algorithms are numerically verified for the Ornstein-Uhlenbeck processes, Brownian motions, and one-dimensional L'evy flights.
  arXiv  Detail & Related papers  (2024-12-19T14:04:11Z)
• Schrödingerization based Quantum Circuits for Maxwell's Equation with time-dependent source terms [24.890270804373824]
  This paper explicitly constructs a quantum circuit for Maxwell's equations with perfect electric conductor (PEC) boundary conditions. We show that quantum algorithms constructed using Schr"odingerisation exhibit acceleration in computational complexity compared to the classical Finite Difference Time Domain (FDTD) format.
  arXiv  Detail & Related papers  (2024-11-17T08:15:37Z)
• Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions [13.16814860487575]
  We present quantum algorithms for sampling from nonlogconcave probability distributions. $f$ can be written as a finite sum $f(x):= frac1Nsum_k=1N f_k(x)$.
  arXiv  Detail & Related papers  (2023-10-17T17:55:32Z)
• Improving Quantum Simulation Efficiency of Final State Radiation with Dynamic Quantum Circuits [1.3375143521862154]
  We make use of a new quantum hardware capability called dynamical quantum computing to improve the scaling of the QPS algorithm. We modify the quantum parton shower circuit to incorporate mid-circuit qubit measurements, resets, and quantum operations conditioned on classical information.
  arXiv  Detail & Related papers  (2022-03-18T15:31:19Z)
• Two quantum Ising algorithms for the Shortest Vector Problem: one for now and one for later [19.4417702222583]
  We describe two variants of a quantum Ising algorithm to solve the Shortest Vector Problem. One variant is spatially efficient, requiring only O(NlogN) qubits where N is the lattice dimension, while the other variant is more robust to noise. Analysis of the algorithms' performance on a quantum annealer and in numerical simulations show that the more qubit-efficient variant will outperform in the long run.
  arXiv  Detail & Related papers  (2020-06-24T21:22:11Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)
• Trading T gates for dirty qubits in state preparation and unitary synthesis [0.0]
  We present a quantum algorithm for preparing any dimension-$N$ pure quantum state specified by a list of $N$ classical numbers. Our scheme uses $mathcalO(fracNlambda+lambdalogfracNepsilonlogfraclogNepsilon)$ to reduce the T-gate cost to $mathcalO(fracNlambda+lambdalogfracNepsilonlogfraclogNepsilon)$
  arXiv  Detail & Related papers  (2018-12-03T18:24:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.