Deterministic spatial search using alternating quantum walks

Abstract

This paper examines the performance of spatial search where the Grover diffusion operator is replaced by continuous-time quantum walks on a class of interdependent networks. We prove that for a set of optimal quantum walk times and marked vertex phase shifts, a deterministic algorithm for structured spatial search is established that finds the marked vertex with 100% probability. This improves on the original spatial search algorithm on the same class of graphs, which we show can only amplify to 50% probability. Our method uses $\lceil \frac{\pi }{2\sqrt{2}}\sqrt{N}\rceil$ marked vertex phase shifts for an $N$-vertex graph, making it comparable with Grover's algorithm for unstructured search. It is expected that this new framework can be readily extended to deterministic spatial search on other families of graph structures.

arXiv comment10 pages, 8 figures

References in corpus (20)

• A Quantum Approximate Optimization Algorithm
• Quantum Amplitude Amplification and Estimation
• Quantum walks: a comprehensive review
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Spatial search by quantum walk
• Grover Algorithm with zero theoretical failure rate
• Continuous-Time Quantum Walks: Models for Coherent Transport on Complex Networks
• Fixed-point quantum search with an optimal number of queries
• Spatial search by quantum walk is optimal for almost all graphs
• Near-optimal quantum circuit for Grover's unstructured search using a transverse field
• Efficient Quantum Walk on a Quantum Processor
• Global Symmetry is Unnecessary for Fast Quantum Search
• Systematic Dimensionality Reduction for Quantum Walks: Optimal Spatial Search and Transport on Non-Regular Graphs
• Variationally Learning Grover's Quantum Search Algorithm
• A quantum walk assisted approximate algorithm for bounded NP optimisation problems
• Combinatorial optimisation via highly efficient quantum walks
• On the optimality of spatial search by continuous-time quantum walk
• Quantum spatial search on graphs subject to dynamical noise
• Quantum Walk Search on Johnson Graphs
• Efficient quantum circuits for continuous-time quantum walks on composite graphs

Cited by in corpus (4)

• A framework for optimal quantum spatial search using alternating phase-walks
• Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact
• Quantum walk-based protocol for secure communication between any two directly connected nodes on a network
• Decoding Quantum Search Advantage: The Critical Role of State Properties in Random Walks