A framework for optimal quantum spatial search using alternating phase-walks

Abstract

We present a novel methodological framework for quantum spatial search, generalising the Childs & Goldstone ($\mathcal{C}\mathcal{G}$) algorithm via alternating applications of marked-vertex phase shifts and continuous-time quantum walks. We determine closed form expressions for the optimal walk time and phase shift parameters for periodic graphs. These parameters are chosen to rotate the system about subsets of the graph Laplacian eigenstates, amplifying the probability of measuring the marked vertex. The state evolution is asymptotically optimal for any class of periodic graphs having a fixed number of unique eigenvalues. We demonstrate the effectiveness of the algorithm by applying it to obtain $\mathcal{O}(\sqrt{N})$ search on a variety of graphs. One important class is the $n\times n^3$ rook graph, which has $N=n^4$ vertices. On this class of graphs the $\mathcal{C}\mathcal{G}$ algorithm performs suboptimally, achieving only $\mathcal{O}(N^{-1/8})$ overlap after time $\mathcal{O}(N^{5/8})$. Using the new alternating phase-walk framework, we show that $\mathcal{O}(1)$ overlap is obtained in $\mathcal{O}(\sqrt{N})$ phase-walk iterations.

References in corpus (30)

• A Quantum Approximate Optimization Algorithm
• Quantum Amplitude Amplification and Estimation
• Quantum walks: a comprehensive review
• Exponential algorithmic speedup by quantum walk
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Spatial search by quantum walk
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Grover's quantum searching algorithm is optimal
• Perfect Transfer of Arbitrary States in Quantum Spin Networks
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Grover Algorithm with zero theoretical failure rate
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• A Review of Perfect State Transfer and its Application as a Constructive Tool
• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• Fixed-point quantum search with an optimal number of queries
• $XY$-mixers: analytical and numerical results for QAOA
• Spatial search by quantum walk is optimal for almost all graphs
• On Arbitrary Phases in Quantum Amplitude Amplification
• Fast-forwarding of Hamiltonians and Exponentially Precise Measurements
• Global Symmetry is Unnecessary for Fast Quantum Search
• Systematic Dimensionality Reduction for Quantum Walks: Optimal Spatial Search and Transport on Non-Regular Graphs
• A quantum walk assisted approximate algorithm for bounded NP optimisation problems
• Combinatorial optimisation via highly efficient quantum walks
• Quantum circuit implementation of the Hamiltonian versions of Grover's algorithm
• 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
• Deterministic spatial search using alternating quantum walks
• Exact quantum lower bound for Grover's problem

Cited by in corpus (2)

• Spatial Search on Johnson Graphs by Discrete-Time Quantum Walk
• Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact