Lackadaisical quantum walks on triangular and honeycomb 2D grids
- URL: http://arxiv.org/abs/2007.13564v1
- Date: Fri, 24 Jul 2020 13:01:36 GMT
- Title: Lackadaisical quantum walks on triangular and honeycomb 2D grids
- Authors: Nikolajs Nahimovs
- Abstract summary: In the typical model, a discrete-time coined quantum walk search has the same running time of $O(sqrtN logN)$ for 2D rectangular, triangular and honeycomb grids.
We show that for both types of grids adding a self-loop of weight $6/N$ and $3/N$ for triangular and honeycomb grids, respectively, results in $O(sqrtN logN)$ running time.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the typical model, a discrete-time coined quantum walk search has the same
running time of $O(\sqrt{N} \log{N})$ for 2D rectangular, triangular and
honeycomb grids. It is known that for 2D rectangular grid the running time can
be improved to $O(\sqrt{N \log{N}})$ using several different techniques. One of
such techniques is adding a self-loop of weight $4/N$ to each vertex (i.e.
making the walk lackadaisical).
In this paper we apply lackadaisical approach to quantum walk search on
triangular and honeycomb 2D grids. We show that for both types of grids adding
a self-loop of weight $6/N$ and $3/N$ for triangular and honeycomb grids,
respectively, results in $O(\sqrt{N \log{N}})$ running time.
Related papers
- Most Neural Networks Are Almost Learnable [52.40331776572531]
We show that for any fixed $epsilon>0$ and depth $i$, there is a poly-time algorithm that learns random Xavier networks of depth $i$.
The algorithm runs in time and sample complexity of $(bard)mathrmpoly(epsilon-1)$, where $bar d$ is the size of the network.
For some cases of sigmoid and ReLU-like activations the bound can be improved to $(bard)mathrmpolylog(eps
arXiv Detail & Related papers (2023-05-25T22:27:42Z) - CCuantuMM: Cycle-Consistent Quantum-Hybrid Matching of Multiple Shapes [62.45415756883437]
Jointly matching multiple, non-rigidly deformed 3D shapes is a challenging, $mathcalNP$-hard problem.
Existing quantum shape-matching methods do not support multiple shapes and even less cycle consistency.
This paper introduces the first quantum-hybrid approach for 3D shape multi-matching.
arXiv Detail & Related papers (2023-03-28T17:59:55Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods.
We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
arXiv Detail & Related papers (2023-03-03T18:23:20Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems.
We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$.
We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
arXiv Detail & Related papers (2022-12-03T02:45:23Z) - 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) - 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) - Lackadaisical quantum walks on 2D grids with multiple marked vertices [0.0]
Lackadaisical quantum walk (LQW) is a quantum analog of a classical lazy walk.
We numerically study search by LQW for different types of 2D grids -- triangular, rectangular and honeycomb.
arXiv Detail & Related papers (2021-04-20T13:33:16Z) - Quasi-polynomial time approximation of output probabilities of
geometrically-local, shallow quantum circuits [0.0]
We present a classical algorithm for any 3D geometrically-local, polylogarithmic-depth quantum circuit.
It computes the quantity $| x |C|0otimes n>|2$ to within any inverse-polynomial additive error in quasi-polynomial time.
arXiv Detail & Related papers (2020-12-10T05:19:29Z) - Unstructured Search by Random and Quantum Walk [0.0]
Find an entry in an unsorted list of $N$ elements famously takes $O(N)$ queries to an oracle for a classical computer.
We derive how discrete- and continuous-time random walks and quantum walks solve this problem.
arXiv Detail & Related papers (2020-11-30T04:00:31Z) - Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language [1.0118253437732931]
We study the quantum query complexity of two problems.
We consider connectivity problems on grid graphs in 2 dimensions, if some of the edges of the grid may be missing.
By embedding the "balanced parentheses" problem into the grid, we show a lower bound of $Omega(n1.5-epsilon)$ for the directed 2D grid and $Omega(n2-epsilon)$ for the undirected 2D grid.
arXiv Detail & Related papers (2020-07-06T09:51:41Z) - PUGeo-Net: A Geometry-centric Network for 3D Point Cloud Upsampling [103.09504572409449]
We propose a novel deep neural network based method, called PUGeo-Net, to generate uniform dense point clouds.
Thanks to its geometry-centric nature, PUGeo-Net works well for both CAD models with sharp features and scanned models with rich geometric details.
arXiv Detail & Related papers (2020-02-24T14:13:29Z)
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.