Scattering Quantum Random Walks on Square Grids and Randomly Generated Mazes

Abstract

The Scattering Quantum Random Walk scheme has found success as a basis for search algorithms on highly symmetric graph structures. In this paper we examine its effectiveness at locating a specially marked vertex on square grid graphs, consisting of N${}^2$ nodes. We simulate these quantum systems using classical computational methods, and find that the probability distributions that arise are very favorable for a hybrid quantum / classical algorithm. We then examine how this hybrid algorithm handles varying types of randomness in both location of the special vertex and later random obstacles placed throughout the geometry, showing that that the algorithm is resilient to both cases.

References in corpus (24)

• A variational eigenvalue solver on a quantum processor
• The theory of variational hybrid quantum-classical algorithms
• A Quantum Random Walk Search Algorithm
• Quantum walks of correlated particles
• Spatial search by quantum walk
• Quantum Walk in Position Space with Single Optically Trapped Atoms
• Photons Walking the Line: A quantum walk with adjustable coin operations
• Realization of quantum walks with negligible decoherence in waveguide lattices
• Quantum walk of a trapped ion in phase space
• A 2D Quantum Walk Simulation of Two-Particle Dynamics
• Optimized quantum random-walk search algorithms
• Quantum searches on highly symmetric graphs
• Perfect state transfer by means of discrete-time quantum walk search algorithms on highly symmetric graphs
• Perfect state transfer by means of discrete-time quantum walk on complete bipartite graphs
• Searching via walking: How to find a marked subgraph of a graph using quantum walks
• Finding structural anomalies in graphs by means of quantum walks
• Quantum walks as a probe of structural anomalies in graphs
• Finding structural anomalies in star graphs: A general approach
• Finding paths in tree graphs with a quantum walk
• Finding paths with quantum walks or quantum walking through a maze
• The quantum walk search algorithm: Factors affecting efficiency
• Finding Structural Anomalies in Star Graphs Using Quantum Walks: A General Approach
• Study of Quantum Walk over a Square Lattice
• Searches on star graphs and equivalent oracle problems