Quantum Random Walks without a Coin Toss

2005/06/27 by Apoorva Patel, Patel, Apoorva, K. S. Raghunathan +3 · 1 citation
Physics and Astronomy · #FOS: Physical sciences #Quantum Physics (quant-ph) #quant-ph

paper · pdf · doi:10.48550/arxiv.quant-ph/0506221

8 pages, RevTeX4, 5 figures. Invited lecture at the Workshop on Quantum Information, Computation and Communication (QICC-2005), IIT Kharagpur, India, February 2005

arxiv created 2005/06/27 · arxiv updated 2009/12/01

Abstract

We construct a quantum random walk algorithm, based on the Dirac operator instead of the Laplacian. The algorithm explores multiple evolutionary branches by superposition of states, and does not require the coin toss instruction of classical randomised algorithms. We use this algorithm to search for a marked vertex on a hypercubic lattice in arbitrary dimensions. Our numerical and analytical results match the scaling behaviour of earlier algorithms that use a coin toss instruction.

Cited by

• Image classification via a quantum-inspired strategy involving a mixture of experts

Related

• Reducing number of gates in quantum random walk search algorithm via modification of coin operators
• Optimizing the walk coin in the quantum random walk search algorithm through machine learning
• Robustness of Quantum Random Walk Search Algorithm in Hypercube when only first or both first and second neighbors are measured
• Mapping quantum random walks onto a Markov chain by mapping a unitary transformation to a higher dimension of an irreducible matrix
• Where to quantum walk