Quadratic speedup for spatial search by continuous-time quantum walk
- URL: http://arxiv.org/abs/2112.12746v1
- Date: Thu, 23 Dec 2021 17:57:49 GMT
- Title: Quadratic speedup for spatial search by continuous-time quantum walk
- Authors: Simon Apers, Shantanav Chakraborty, Leonardo Novo, J\'er\'emie Roland
- Abstract summary: Continuous-time quantum walks provide a framework to tackle the fundamental problem of finding a node among a set of marked nodes in a graph, known as spatial search.
We present a new continuous-time quantum walk search algorithm that 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.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- 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^{-tH^2}|\psi\rangle$, 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.
Related papers
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP)
We generalize the SDP-inspired quantum algorithm to sum-of-squares.
Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
arXiv Detail & Related papers (2024-08-14T19:04:13Z) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry.
The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time.
Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
arXiv Detail & Related papers (2024-05-02T10:29:06Z) - Quantum walks advantage on the dihedral group for uniform sampling
problem [0.0]
Mixing through walks is the process for a Markov chain to approximate a stationary distribution for a group.
Quantum walks have shown potential advantages in mixing time over the classical case but lack general proof in the finite group case.
This work has potential applications in algorithms for sampling non-abelian groups, graph isomorphism tests, etc.
arXiv Detail & Related papers (2023-12-25T11:21:55Z) - Comparison among Classical, Probabilistic and Quantum Algorithms for
Hamiltonian Cycle problem [0.0]
Hamiltonian cycle problem (HCP) consists of having a graph G with n nodes and m edges and finding the path that connects each node exactly once.
In this paper we compare some algorithms to solve aHCP, using different models of computations and especially the probabilistic and quantum ones.
arXiv Detail & Related papers (2023-11-18T02:36:10Z) - Discrete-time Semiclassical Szegedy Quantum Walks [0.0]
We introduce the semiclassical walks in discrete time, which are algorithms that combines classical and quantum dynamics.
We have demonstrated experimentally that the semiclassical walks can be applied on real quantum computers using the platform IBM Quantum.
arXiv Detail & Related papers (2023-03-31T16:57:13Z) - Improvement of quantum walk-based search algorithms in single marked
vertex graphs [0.0]
Amplitude amplification is usually used to amplify success probability, but the souffl'e problems follow.
In this work, we define generalized interpolated quantum walks, which can both improve the success probability of search algorithms and avoid the souffl'e problems.
arXiv Detail & Related papers (2022-09-09T07:43:46Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle.
We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm.
We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z) - Robust Quantum Walk Search Without Knowing the Number of Marked Vertices [0.2320417845168326]
Existing quantum walk-based search algorithms suffer from the souffl'e problem.
We present a new quantum walk-based search framework that achieves robustness without sacrificing the quantum speedup.
arXiv Detail & Related papers (2021-11-17T10:04:44Z) - Algebraic Compression of Quantum Circuits for Hamiltonian Evolution [52.77024349608834]
Unitary evolution under a time dependent Hamiltonian is a key component of simulation on quantum hardware.
We present an algorithm that compresses the Trotter steps into a single block of quantum gates.
This results in a fixed depth time evolution for certain classes of Hamiltonians.
arXiv Detail & Related papers (2021-08-06T19:38:01Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$.
This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
arXiv Detail & Related papers (2021-06-11T09:43:09Z) - Continuous-time quantum walks in the presence of a quadratic
perturbation [55.41644538483948]
We address the properties of continuous-time quantum walks with Hamiltonians of the form $mathcalH= L + lambda L2$.
We consider cycle, complete, and star graphs because paradigmatic models with low/high connectivity and/or symmetry.
arXiv Detail & Related papers (2020-05-13T14:53:36Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.