Quadratic speedup for spatial search by continuous-time quantum walk

Abstract

Continuous-time quantum walks provide a natural framework to tackle the fundamental problem of finding a node among a set of marked nodes in a graph, known as spatial search. Whether spatial search by continuous-time quantum walk provides a quadratic advantage over classical random walks has been an outstanding problem. Thus far, this advantage is obtained only for specific graphs or when a single node of the underlying graph is marked. In this article, we provide a new continuous-time quantum walk search algorithm that completely resolves this: our algorithm can find a marked node in any graph with any number of marked nodes, in a time that is quadratically faster than classical random walks. The overall algorithm is quite simple, requiring time evolution of the quantum walk Hamiltonian followed by a projective measurement. A key component of our algorithm is a purely analog procedure to perform operations on a state of the form $e^{-t{H}^2}|\psi ⟩$, for a given Hamiltonian $H$: it only requires evolving $H$ for time scaling as $\sqrt{t}$. This allows us to quadratically fast-forward the dynamics of a continuous-time classical random walk. The applications of our work thus go beyond the realm of quantum walks and can lead to new analog quantum algorithms for preparing ground states of Hamiltonians or solving optimization problems.

References in corpus (9)

• Universal computation by quantum walk
• Spatial search by quantum walk
• Quantum Simulations of Classical Annealing Processes
• Spatial search and the Dirac equation
• Connectivity is a Poor Indicator of Fast Quantum Search
• On the optimality of spatial search by continuous-time quantum walk
• On the adiabatic condition and the quantum hitting time of Markov chains
• Continuous-time quantum walk spatial search on the Bollobás scale-free network
• Quantum Gaussian filter for exploring ground-state properties

Cited by in corpus (27)

• Review on Quantum Walk Computing: Theory, Implementation, and Application
• Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
• Efficient implementation of discrete-time quantum walks on quantum computers
• Quantum differential equation solvers: limitations and fast-forwarding
• Quantum Gaussian filter for exploring ground-state properties
• Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters
• Spatial search by continuous-time quantum walks on renormalized Internet networks
• Multiparameter estimation of continuous-time Quantum Walk Hamiltonians through Machine Learning
• Perfect chiral quantum routing
• Quantum search in many-body interacting system with long-range interaction
• Coined quantum walks on the line: Disorder, entanglement, and localization
• Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact
• The cost of solving linear differential equations on a quantum computer: fast-forwarding to explicit resource counts
• Quantum walk state transfer on a hypercube
• Scoring Anomalous Vertices Through Quantum Walks
• Quantum Dissipative Search via Lindbladians
• Multimarked Spatial Search by Continuous-Time Quantum Walk
• Demonstration of Discrete-Time Quantum Walks and Observation of Topological Edge States in a Superconducting Qutrit Chain
• Recurrence in discrete-time quantum stochastic walks
• Impact of Bivariate Gaussian Potentials on Quantum Walks for Spatial Search
• Optimizing topology for quantum probing with discrete-time quantum walks
• Quantum search by continuous-time quantum walk on t-designs
• Lower bounds on the number of rounds of the quantum approximate optimization algorithm required for guaranteed approximation ratios
• Quantum Hitting Time according to a given distribution
• Search and state transfer between hubs by quantum walks
• Temporal nonclassicality in continuous-time quantum walks
• Next-generation interferometry with gauge-invariant linear optical scatterers