Search via Quantum Walk
arXiv:quant-ph/0608026 · doi:10.1137/090745854
Abstract
We propose a new method for designing quantum search algorithms for finding a "marked" element in the state space of a classical Markov chain. The algorithm is based on a quantum walk á la Szegedy (2004) that is defined in terms of the Markov chain. The main new idea is to apply quantum phase estimation to the quantum walk in order to implement an approximate reflection operator. This operator is then used in an amplitude amplification scheme. As a result we considerably expand the scope of the previous approaches of Ambainis (2004) and Szegedy (2004). Our algorithm combines the benefits of these approaches in terms of being able to find marked elements, incurring the smaller cost of the two, and being applicable to a larger class of Markov chains. In addition, it is conceptually simple and avoids some technical difficulties in the previous analyses of several algorithms based on quantum walk.
21 pages. Various modifications and improvements, especially in Section 4
References in corpus (4)
Cited by in corpus (127)
- Quantum algorithms: an overview
- Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
- Quantum machine learning: a classical perspective
- Quantum speedup for active learning agents
- Quantum query complexity of state conversion
- Quantum Algorithm Implementations for Beginners
- Propagation and spectral properties of quantum walks in electric fields
- Quantum Walks in artificial electric and gravitational Fields
- Quantum walks can find a marked element on any graph
- The Staggered Quantum Walk Model
- Quantum Computation and Quantum Information
- Quantum Walks and discrete Gauge Theories
- Bulk-edge correspondence of one-dimensional quantum walks
- Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments
- Asymptotic dynamics of coined quantum walks on percolation graphs
- QFold: Quantum Walks and Deep Learning to Solve Protein Folding
- Quantum enhancements for deep reinforcement learning in large spaces
- Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm
- Quantum walk approach to simulating parton showers
- Review on Quantum Walk Computing: Theory, Implementation, and Application
- Quantum search with hybrid adiabatic-quantum walk algorithms and realistic noise
- On the optimality of spatial search by continuous-time quantum walk
- Machine learning \& artificial intelligence in the quantum domain
- Predicting quantum advantage by quantum walk with convolutional neural networks
- Finding Angles for Quantum Signal Processing with Machine Precision
- Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits
- Quantum Computing: Lecture Notes
- Quantum-enhanced deliberation of learning agents using trapped ions
- Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks
- Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model
- Efficient quantum circuits for Szegedy quantum walks
- Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
- Speeding-up the decision making of a learning agent using an ion trap quantum processor
- Learning-Graph-Based Quantum Algorithm for k-distinctness
- Quantum walk speedup of backtracking algorithms
- Nested Quantum Walks with Quantum Data Structures
- Improved Quantum Information Set Decoding
- Dark states of quantum search cause imperfect detection
- From classical to quantum walks with stochastic resetting on networks
- Quantum attacks against iterated block ciphers
- How fast do quantum walks mix?
- Finding a marked node on any graph by continuous-time quantum walk
- Quantum Metropolis Solver: A Quantum Walks Approach to Optimization Problems
- Quantum Walks and Electric Networks
- Revivals in Quantum Walks with quasi-periodically time-dependent coin
- Quantum Meets Fine-grained Complexity: Sublinear Time Quantum Algorithms for String Problems
- Faster than Classical Quantum Algorithm for dense Formulas of Exact Satisfiability and Occupation Problems
- Efficient and scalable quantum walk algorithms via the quantum Fourier transform
- A learning graph based quantum query algorithm for finding constant-size subgraphs
- Eigenvalue Measurement of Topologically Protected Edge states in Split-Step Quantum Walks
- Fermion confinement via Quantum Walks in 2D+1 and 3D+1 spacetime
- Spectral Transition for Random Quantum Walks on Trees
- Implementation of generalized measurements on a qudit via quantum walks
- Efficient quantum circuits for continuous-time quantum walks on composite graphs
- Quantum Query Algorithms are Completely Bounded Forms
- Faster quantum mixing for slowly evolving sequences of Markov chains
- Analog quantum algorithms for the mixing of Markov chains
- Uncertainty and symmetry bounds for the quantum total detection probability
- Unidirectional quantum walks: evolution and exit times
- Robust Quantum Walk Search Without Knowing the Number of Marked Vertices
- Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions
- Classical-like behavior in quantum walks with inhomogeneous, time-dependent coin operators
- Simulation of Quantum Walks and Fast Mixing with Classical Processes
- Dirac quantum walks on triangular and honeycomb lattices
- Exceptional Quantum Walk Search on the Cycle
- Quantum machine learning with glow for episodic tasks and decision games
- Non-Hermitian and Zeno limit of quantum systems under rapid measurements
- Quantum Search Approaches to Sampling-Based Motion Planning
- Quantum search with interacting Bose-Einstein condensates
- Massless Dirac Equation from Fibonacci Discrete-Time Quantum Walk
- Differentially Private Clustering: Tight Approximation Ratios
- Invariance in quantum walks with time-dependent coin operators
- Improved Upper Bounds for the Hitting Times of Quantum Walks
- Parallel Quantum Algorithm for Hamiltonian Simulation
- A Sublinear-Time Quantum Algorithm for Approximating Partition Functions
- Coined Quantum Walks as Quantum Markov Chains
- Probability distributions for Markov chains based quantum walks
- Improved quantum backtracking algorithms using effective resistance estimates
- Quantum Distributed Complexity of Set Disjointness on a Line
- Quantum algorithm for estimating volumes of convex bodies
- New Developments in Quantum Algorithms
- Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
- Spatial Search on Graphs with Multiple Targets using Flip-flop Quantum Walk
- Non-Markovian quantum interference in multilevel quantum systems: Exact master equation approach
- Applications of the Adversary Method in Quantum Query Algorithms
- Green function approach for scattering quantum walks
- Complete classification of trapping coins for quantum walks on the 2D square lattice
- Quantum Algorithm for Triangle Finding in Sparse Graphs
- Quantum walk with a general coin: Exact solution and asymptotic properties
- Limit theorems and localization of three state quantum walks on a line defined by generalized Grover coins
- Spectral Properties of Quantum Walks on Rooted Binary Trees
- Optimal parallel quantum query algorithms
- SQUWALS: A Szegedy QUantum WALks Simulator
- A Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates
- Quantum Computing: Implementing Hitting Time for Coined Quantum Walks on Regular Graphs
- Efficient quantum walk on the grid with multiple marked elements
- Coined quantum walks on the line: Disorder, entanglement, and localization
- A Complete Characterization of Pretty Good State Transfer on Paths
- Multimarked Spatial Search by Continuous-Time Quantum Walk
- Improving the query complexity of quantum spatial search in two dimensions
- Preparing Many Copies of a Quantum State in the Black-Box Model
- Improved quantum algorithm for the random subset sum problem
- Hitting time for quantum walks of identical particles
- A Quantum Algorithm for the Sensitivity Analysis of Business Risks
- Implementing Semiclassical Szegedy Walks in Classical-Quantum Circuits for Homomorphic Encryption
- On Hitting Times for General Quantum Markov Processes
- Faster quantum mixing of Markov chains in non-regular graph with fewer qubits
- Lower Bounds on the Localisation Length of Balanced Random Quantum Walks
- Unbounded quantum-classical separation in sample complexity for sphere center finding
- Invariance in Quantum Walks
- Near-Optimal Quantum Algorithms for String Problems
- Clustering-induced localization of quantum walks on networks
- Generator of an abstract quantum walk
- On the Power of Non-Adaptive Learning Graphs
- Quantum Algorithms for Finding Constant-sized Sub-hypergraphs
- Quantum Hitting Time according to a given distribution
- Studies of braided non-Abelian anyons using anyonic tensor networks
- Simulating Non Commutative Geometry with Quantum Walks
- Quantum Approximate Counting for Markov Chains and Application to Collision Counting
- Szegedy's quantum walk with queries
- Two Variations of Quantum Phase Estimation for Reducing Circuit Error Rates: Application to the Harrow--Hassidim--Lloyd Algorithm
- Data Structures in Classical and Quantum Computing
- Provably secure key establishment against quantum adversaries
- Improved Quantum Query Complexity on Easier Inputs
- Leveraging Unknown Structure in Quantum Query Algorithms
- Neighborhood-History Quantum Walk
- Transition in Splitting Probabilities of Quantum Walks