Spatial Search by Continuous-Time Quantum Walk with Multiple Marked Vertices

Abstract

In the typical spatial search problems solved by continuous-time quantum walk, changing the location of the marked vertices does not alter the search problem. In this paper, we consider search when this is no longer true. In particular, we analytically solve search on the "simplex of $K_M$ complete graphs" with all configurations of two marked vertices, two configurations of $M+1$ marked vertices, and two configurations of $2(M+1)$ marked vertices, showing that the location of the marked vertices can dramatically influence the required jumping rate of the quantum walk, such that using the wrong configuration's value can cause the search to fail. This sensitivity to the jumping rate is an issue unique to continuous-time quantum walks that does not affect discrete-time ones.

29 pages, 15 figures

References in corpus (10)

• Universal computation by quantum walk
• Spatial search by quantum walk
• Grover Search with Lackadaisical Quantum Walks
• Systematic Dimensionality Reduction for Quantum Walks: Optimal Spatial Search and Transport on Non-Regular Graphs
• Connectivity is a Poor Indicator of Fast Quantum Search
• Hamiltonian Oracles
• Quantum Search with Multiple Walk Steps per Oracle Query
• Diagrammatic Approach to Quantum Search
• Faster Quantum Walk Search on a Weighted Graph
• Quantum Walk on the Line through Potential Barriers

Cited by in corpus (15)

• Laplacian versus Adjacency Matrix in Quantum Walk Search
• Continuous-Time Quantum Search on Balanced Trees
• Quantum spatial search on graphs subject to dynamical noise
• Vertices cannot be hidden from quantum spatial search for almost all random graphs
• Irreconcilable Difference Between Quantum Walks and Adiabatic Quantum Computing
• Engineering the Success of Quantum Walk Search Using Weighted Graphs
• Spatial search by continuous-time quantum walks on renormalized Internet networks
• Doubling the Success of Quantum Walk Search Using Internal-State Measurements
• Quantum search in many-body interacting system with long-range interaction
• Optimal Quantum Walk Search on Kronecker Graphs with Dominant or Fixed Regular Initiators
• Multimarked Spatial Search by Continuous-Time Quantum Walk
• Quantum search by continuous-time quantum walk on t-designs
• Faster Search of Clustered Marked States with Lackadaisical Quantum Walks
• Universality of the fully connected vertex in Laplacian continuous-time quantum walk problems
• Photon-Number Conserved Universal Quantum Logic Employing Continuous-Time Quantum Walk on Dual-Rail Qubit Arrays