Multimarked Spatial Search by Continuous-Time Quantum Walk
- URL: http://arxiv.org/abs/2203.14384v3
- Date: Wed, 17 Jan 2024 14:45:54 GMT
- Title: Multimarked Spatial Search by Continuous-Time Quantum Walk
- Authors: Pedro H. G. Lug\~ao, Renato Portugal, Mohamed Sabri, Hajime Tanaka
- Abstract summary: We describe a framework for determining the computational complexity of spatial search by continuous-time quantum walk on arbitrary graphs.
The quantum walk is driven by a Hamiltonian derived from the adjacency matrix of the graph modified by the presence of the marked vertices.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The quantum-walk-based spatial search problem aims to find a marked vertex
using a quantum walk on a graph with marked vertices. We describe a framework
for determining the computational complexity of spatial search by
continuous-time quantum walk on arbitrary graphs by providing a recipe for
finding the optimal running time and the success probability of the algorithm.
The quantum walk is driven by a Hamiltonian derived from the adjacency matrix
of the graph modified by the presence of the marked vertices. The success of
our framework depends on the knowledge of the eigenvalues and eigenvectors of
the adjacency matrix. The spectrum of the Hamiltonian is subsequently obtained
from the roots of the determinant of a real symmetric matrix $M$, the
dimensions of which depend on the number of marked vertices. The eigenvectors
are determined from a basis of the kernel of $M$. We show each step of the
framework by solving the spatial searching problem on the Johnson graphs with a
fixed diameter and with two marked vertices. Our calculations show that the
optimal running time is $O(\sqrt{N})$ with an asymptotic probability of
$1+o(1)$, where $N$ is the number of vertices.
Related papers
- Walking on Vertices and Edges by Continuous-Time Quantum Walk [0.0]
We define a version of the continuous-time quantum walk that allows the walker to hop from vertices to edges and vice versa.
We analyze the spatial search algorithm on the complete bipartite graph by modifying the new version of the Hamiltonian.
arXiv Detail & Related papers (2022-06-07T15:10:18Z) - A framework for optimal quantum spatial search using alternating
phase-walks [0.0]
We generalise the Childs & Goldstone ($mathcalCG$) algorithm via alternating applications of marked-vertex phase shifts and continuous-time quantum walks.
We demonstrate the effectiveness of the algorithm by applying it to obtain $mathcalO(sqrtN)$ search on a variety of graphs.
arXiv Detail & Related papers (2021-09-29T11:16:52Z) - The average search probabilities of discrete-time quantum walks [0.0]
We first show that, for a regular graph, the spectrum of the transition matrix is determined by the weighted adjacency matrix of an augmented graph.
We then consider the average search probability on a distance regular graph, and find a formula in terms of the adjacency matrix of its subgraph.
In particular, for any family of (1) complete graphs, or (2) strongly regular graphs, or (3) distance regular graphs of a fixed parameter $d$, varying valency $k$ and varying size $n$, the average search probability approaches $1/4$ as the valency goes to infinity.
arXiv Detail & Related papers (2021-08-22T18:53:22Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits.
Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering.
We show the qudit implementation is superior to the qubit encoding as quantified by the gate count.
arXiv Detail & Related papers (2021-06-22T11:07:38Z) - 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) - Spectral clustering under degree heterogeneity: a case for the random
walk Laplacian [83.79286663107845]
This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree.
In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
arXiv Detail & Related papers (2021-05-03T16:36:27Z) - Quantum walk-based search algorithms with multiple marked vertices [0.0]
The quantum walk is a powerful tool to develop quantum algorithms.
We extend previous analytical methods based on Szegedy's quantum walk.
Two examples based on the coined quantum walk on two-dimensional lattices and hypercubes show the details of our method.
arXiv Detail & Related papers (2021-03-23T22:57:07Z) - Quantum algorithms for spectral sums [50.045011844765185]
We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices.
We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
arXiv Detail & Related papers (2020-11-12T16:29:45Z) - 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) - Search on Vertex-Transitive Graphs by Lackadaisical Quantum Walk [0.0]
The lackadaisical quantum walk is a discrete-time, coined quantum walk on a graph.
It can improve spatial search on the complete graph, discrete torus, cycle, and regular complete bipartite graph.
We present a number of numerical simulations supporting this hypothesis.
arXiv Detail & Related papers (2020-02-26T00:10:38Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
We provide the first non-asymptotic analysis for finding stationary points of nonsmooth, nonsmooth functions.
In particular, we study Hadamard semi-differentiable functions, perhaps the largest class of nonsmooth functions.
arXiv Detail & Related papers (2020-02-10T23:23:04Z)
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.