Spatial Search by Continuous-Time Quantum Walk with Multiple Marked Vertices
arXiv:1501.07071 · doi:10.1007/s11128-015-1239-y
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 complete graphs" with all configurations of two marked vertices, two configurations of marked vertices, and two configurations of 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.
arXiv comment29 pages, 15 figures
References in corpus (18)
- Quantum random walks - an introductory overview
- Quantum Computation and Decision Trees
- A Quantum Random Walk Search Algorithm
- Universal computation by quantum walk
- Spatial search by quantum walk
- From quantum cellular automata to quantum lattice gases
- On the absence of homogeneous scalar unitary cellular automata
- Grover Search with Lackadaisical Quantum Walks
- Global Symmetry is Unnecessary for Fast Quantum Search
- Systematic Dimensionality Reduction for Quantum Walks: Optimal Spatial Search and Transport on Non-Regular Graphs
- Connectivity is a Poor Indicator of Fast Quantum Search
- Quantum walks can find a marked element on any graph
- Hamiltonian Oracles
- Non-interacting multi-particle quantum random walks applied to the graph isomorphism problem for strongly regular graphs
- Quantum Search with Multiple Walk Steps per Oracle Query
- Faster Quantum Walk Search on a Weighted Graph
- Diagrammatic Approach to Quantum Search
- 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