Doubling the Success of Quantum Walk Search Using Internal-State Measurements
arXiv:1511.03865 · doi:10.1088/1751-8113/49/45/455301
Abstract
In typical discrete-time quantum walk algorithms, one measures the position of the walker while ignoring its internal spin/coin state. Rather than neglecting the information in this internal state, we show that additionally measuring it doubles the success probability of many quantum spatial search algorithms. For example, this allows Grover's unstructured search problem to be solved with certainty, rather than with probability 1/2 if only the walker's position is measured, so the additional measurement yields a search algorithm that is twice as fast as without it, on average. Thus the internal state of discrete-time quantum walks holds valuable information that can be utilized to improve algorithms. Furthermore, we determine conditions for which spatial search problems on regular graphs are amenable to this doubling of the success probability, and this involves diagrammatically analyzing search using degenerate perturbation theory and deriving a useful formula for how the quantum walk acts in its reduced subspace.
arXiv comment11 pages, 9 figures
References in corpus (14)
- Quantum random walks - an introductory overview
- A Quantum Random Walk Search Algorithm
- Quantum walks: a comprehensive review
- From quantum cellular automata to quantum lattice gases
- Universal quantum computation using the discrete time quantum walk
- Optimized quantum random-walk search algorithms
- On the absence of homogeneous scalar unitary cellular automata
- Global Symmetry is Unnecessary for Fast Quantum Search
- Connectivity is a Poor Indicator of Fast Quantum Search
- Spatial Search by Continuous-Time Quantum Walk with Multiple Marked Vertices
- Quantum Search with Multiple Walk Steps per Oracle Query
- Quantum search algorithms on the hypercube
- Diagrammatic Approach to Quantum Search
- Faster Quantum Walk Search on a Weighted Graph
Cited by in corpus (6)
- Quantum Walk Search on the Complete Bipartite Graph
- Equivalence of Szegedy's and Coined Quantum Walks
- Search by Lackadaisical Quantum Walk with Nonhomogeneous Weights
- Search on Vertex-Transitive Graphs by Lackadaisical Quantum Walk
- Full Characterization of Oscillatory Localization of Quantum Walks
- Oscillatory Localization of Quantum Walks Analyzed by Classical Electric Circuits