Quantum Random Walks do not need a Coin Toss

Abstract

Classical randomized algorithms use a coin toss instruction to explore different evolutionary branches of a problem. Quantum algorithms, on the other hand, can explore multiple evolutionary branches by mere superposition of states. Discrete quantum random walks, studied in the literature, have nonetheless used both superposition and a quantum coin toss instruction. This is not necessary, and a discrete quantum random walk without a quantum coin toss instruction is defined and analyzed here. Our construction eliminates quantum entanglement from the algorithm, and the results match those obtained with a quantum coin toss instruction.

6 pages, 4 figures, RevTeX (v2) Expanded to include relation to quantum walk with a coin. Connection with Dirac equation pointed out. Version to be published in Phys. Rev. A

References in corpus (4)

• Quantum random walks - an introductory overview
• Quantum Computation and Decision Trees
• From quantum cellular automata to quantum lattice gases
• Spatial search and the Dirac equation

Cited by in corpus (41)

• Quantum walks: a comprehensive review
• Connecting the discrete and continuous-time quantum walks
• Limit Theorem for Continuous-Time Quantum Walk on the Line
• Quantum Walks on a Random Environment
• The Staggered Quantum Walk Model
• Experimental Implementation of Quantum Walks on IBM Quantum Computers
• Staggered Quantum Walks on Graphs
• Perfect state transfer by means of discrete-time quantum walk on complete bipartite graphs
• Spatial search by continuous-time quantum walks on crystal lattices
• Non-Markovian continuous-time quantum walks on lattices with dynamical noise
• Search on a Hypercubic Lattice using a Quantum Random Walk: I. d>2
• Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model
• Staggered Quantum Walks with Hamiltonians
• One-Dimensional Coinless Quantum Walks
• Quantum walks with a one-dimensional coin
• Quantum search on the two-dimensional lattice using the staggered model with Hamiltonians
• Dynamics of Rydberg excitations and quantum correlations in an atomic array coupled to a photonic crystal waveguide
• Continuous Limit of Discrete Quantum Walks
• Staggered quantum walks with superconducting microwave resonators
• Thermodynamics of N-dimensional quantum walks
• Coherent chemical kinetics as quantum walks I: Reaction operators for radical pairs
• Discrete-time quantum walks as fermions of lattice gauge theory
• Renormalization and Scaling in Quantum Walks
• Continuous-Time Quantum Random Walks Require Discrete Space
• Relation between coined quantum walks and quantum cellular automata
• Moments of Coinless Quantum Walks on Lattices
• Spatial Search on Graphs with Multiple Targets using Flip-flop Quantum Walk
• Non-Markovian quantum interference in multilevel quantum systems: Exact master equation approach
• Chirality from quantum walks without quantum coin
• Bandit Algorithm Driven by a Classical Random Walk and a Quantum Walk
• Second-order topological insulator in a coinless discrete-time quantum walk
• Quantum hub and authority centrality measures for directed networks based on continuous-time quantum walks
• Staggered Quantum Walk on Hexagonal Lattices
• Quantum Walks on Embeddings
• Quantum vs Classical Birth and Death Processes; Exactly Solvable Examples
• Integrated photonic 3D waveguide arrays for quantum random walks on a circle
• Quantum Algorithms: Database Search and its Variations
• Path integral approach to one-dimensional discrete-time quantum walk
• How to Teach a Quantum Computer a Probability Distribution
• Asymptotic reduced density matrix of discrete-time quantum walks
• Quantum walks in the density operator picture