Related papers: Analysis of Lackadaisical Quantum Walks

Analysis of Lackadaisical Quantum Walks

URL: http://arxiv.org/abs/2002.11234v3
Date: Fri, 13 Nov 2020 20:31:15 GMT
Title: Analysis of Lackadaisical Quantum Walks
Authors: Peter H{\o}yer and Zhan Yu
Abstract summary: 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.
Score: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The lackadaisical quantum walk is a quantum analogue of the lazy random walk obtained by adding a self-loop to each vertex in the graph. We analytically prove that lackadaisical quantum walks can find a unique marked vertex on any regular locally arc-transitive graph with constant success probability quadratically faster than the hitting time. This result proves several speculations and numerical findings in previous work, including the conjectures that the lackadaisical quantum walk finds a unique marked vertex with constant success probability on the torus, cycle, Johnson graphs, and other classes of vertex-transitive graphs. Our proof establishes and uses a relationship between lackadaisical quantum walks and quantum interpolated walks for any locally arc-transitive graph.

Related papers

Quantum Walk Search on Complete Multipartite Graph with Multiple Marked Vertices [7.922488341886121]
This paper examines the quantum walk search algorithm on complete multipartite graphs. We employ the coined quantum walk model and achieve quadratic speedup. We also provide the numerical simulation and circuit implementation of our quantum algorithm.
arXiv Detail & Related papers (2024-10-07T11:13:41Z)
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)
Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem [55.80819771134007]
In this paper, we give a short proof of the optimal linear hitting time for a welded tree problem by a discrete-time quantum walk. The same technique can be applied to other 1-dimensional hierarchical graphs.
arXiv Detail & Related papers (2024-04-30T11:45:49Z)
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)
Search by Lackadaisical Quantum Walk with Symmetry Breaking [0.0]
The lackadaisical quantum walk is a lazy version of a discrete-time, coined quantum walk. They have been used to speed up spatial search on a variety of graphs.
arXiv Detail & Related papers (2021-08-31T14:08:40Z)
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)
Graph-Theoretic Framework for Self-Testing in Bell Scenarios [37.067444579637076]
Quantum self-testing is the task of certifying quantum states and measurements using the output statistics solely. We present a new approach for quantum self-testing in Bell non-locality scenarios.
arXiv Detail & Related papers (2021-04-27T08:15:01Z)
Quantum walk processes in quantum devices [55.41644538483948]
We study how to represent quantum walk on a graph as a quantum circuit. Our approach paves way for the efficient implementation of quantum walks algorithms on quantum computers.
arXiv Detail & Related papers (2020-12-28T18:04:16Z)
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)
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.