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 Search with the Signless Laplacian [0.0]
We explore the signless Laplacian, which may arise in layered antiferromagnetic materials. For some parameter regimes, the signless Laplacian yields the fastest search algorithm of the three, suggesting that it could be a new tool for developing faster quantum algorithms.
arXiv Detail & Related papers (2025-01-28T18:18:01Z)
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)
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)
A Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy [37.34153902687548]
We tackle the problem of exactly recovering an unknown ground-truth binary labeling of the nodes from a single corrupted observation of each edge. We apply a hierarchy of relaxations known as the sum-of-squares hierarchy, to the problem. We show that the solution of the dual of the relaxed problem is related to finding edge weights of the Johnson and Kneser graphs.
arXiv Detail & Related papers (2021-02-16T08:36:19Z)
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.