Related papers: Walking on Vertices and Edges by Continuous-Time Quantum Walk

Walking on Vertices and Edges by Continuous-Time Quantum Walk

URL: http://arxiv.org/abs/2206.03375v3
Date: Tue, 20 Dec 2022 19:37:11 GMT
Title: Walking on Vertices and Edges by Continuous-Time Quantum Walk
Authors: Caue F. T. Silva, Daniel Posner, and Renato Portugal
Abstract summary: 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.
Score: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: The quantum walk dynamics obey the laws of quantum mechanics with an extra locality constraint, which demands that the evolution operator is local in the sense that the walker must visit the neighboring locations before endeavoring to distant places. Usually, the Hamiltonian is obtained from either the adjacency or the laplacian matrix of the graph and the walker hops from vertices to neighboring vertices. In this work, we define a version of the continuous-time quantum walk that allows the walker to hop from vertices to edges and vice versa. As an application, we analyze the spatial search algorithm on the complete bipartite graph by modifying the new version of the Hamiltonian with an extra term that depends on the location of the marked vertex or marked edge, similar to what is done in the standard continuous-time quantum walk model. We show that the optimal running time to find either a vertex or an edge is $O(\sqrt{N_e})$ with success probability $1-o(1)$, where $N_e$ is the number of edges of the complete bipartite graph.

Related papers

Constant-Time Quantum Search with a Many-Body Quantum System [39.58317527488534]
We consider a many-body quantum system that naturally effects parallel queries. We show that its parameters can be tuned to search a database in constant time.
arXiv Detail & Related papers (2024-08-09T22:57:59Z)
A hybrid quantum algorithm to detect conical intersections [39.58317527488534]
We show that for real molecular Hamiltonians, the Berry phase can be obtained by tracing a local optimum of a variational ansatz along the chosen path. We demonstrate numerically the application of our algorithm on small toy models of the formaldimine molecule.
arXiv Detail & Related papers (2023-04-12T18:00:01Z)
Multimarked Spatial Search by Continuous-Time Quantum Walk [0.0]
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.
arXiv Detail & Related papers (2022-03-27T20:22:17Z)
Feedback-assisted quantum search by continuous-time quantum walks [58.720142291102135]
We address the quantum search of a target node on a cycle graph by means of a quantum walk assisted by continuous measurement and feedback. In particular, our protocol is able to drive the walker to a desired target node.
arXiv Detail & Related papers (2022-01-12T16:59:53Z)
Quadratic speedup for spatial search by continuous-time quantum walk [0.0]
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.
arXiv Detail & Related papers (2021-12-23T17:57:49Z)
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)
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)
Analysis of Lackadaisical Quantum Walks [0.0]
The lackadaisical quantum walk is a quantum analogue of the lazy random walk obtained by adding a self-loop to each. We analytically prove that lackadaisical quantum walks can find a unique marked. vertebrae on any regular locally arc-transitive graph with constant success probability. quadratically faster than the hitting time.
arXiv Detail & Related papers (2020-02-26T00:40:25Z)
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)
Discrete-Time Quantum Walks on Oriented Graphs [0.0]
We define discrete-time quantum walks on arbitrary oriented graphs. We introduce a parameter, called alpha, that quantifies the amount of orientation.
arXiv Detail & Related papers (2020-01-13T01:42:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.