Related papers: Implementation of hitting times of discrete time quantum random walks on Cubelike graphs

Implementation of hitting times of discrete time quantum random walks on Cubelike graphs

URL: http://arxiv.org/abs/2108.13769v1
Date: Tue, 31 Aug 2021 11:49:34 GMT
Title: Implementation of hitting times of discrete time quantum random walks on Cubelike graphs
Authors: Jaideep Mulherkar, Rishikant Rajdeepak and V Sunitha
Abstract summary: We show an implementation of the hitting time of a discrete time quantum random walk on cubelike graphs. We extend the study to another family of cubelike graphs called the augmented cubes.
Score: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We demonstrate an implementation of the hitting time of a discrete time quantum random walk on cubelike graphs using IBM's Qiskit platform. Our implementation is based on efficient circuits for the Grover and Shift operators. We verify the results about the one-shot hitting time of quantum walks on a hypercube as proved in [https://link.springer.com/article/10.1007/s00440-004-0423-2]. We extend the study to another family of cubelike graphs called the augmented cubes [https://onlinelibrary.wiley.com/doi/abs/10.1002/net.10033]. Based on our numerical study, we conjecture that for all families of cubelike graphs there is a linear relationship between the degree of a cubelike graph and its hitting time which holds asymptotically. That is, for any cubelike graph of degree $\Delta$, the probability of finding the quantum random walk at the target node at time $\frac{\pi \Delta}{2}$ approaches 1 as the degree $\Delta$ of the cubelike graph approaches infinity.

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)
Quantum walks advantage on the dihedral group for uniform sampling problem [0.0]
Mixing through walks is the process for a Markov chain to approximate a stationary distribution for a group. Quantum walks have shown potential advantages in mixing time over the classical case but lack general proof in the finite group case. This work has potential applications in algorithms for sampling non-abelian groups, graph isomorphism tests, etc.
arXiv Detail & Related papers (2023-12-25T11:21:55Z)
General Graph Random Features [42.75616308187867]
We propose a novel random walk-based algorithm for unbiased estimation of arbitrary functions of a weighted adjacency matrix. Our algorithm enjoys subquadratic time complexity with respect to the number of nodes, overcoming the notoriously prohibitive cubic scaling of exact graph kernel evaluation.
arXiv Detail & Related papers (2023-10-07T15:47:31Z)
Moments, Random Walks, and Limits for Spectrum Approximation [40.43008834125277]
We show that there are distributions on $[-1,1]$ that cannot be approximated to accuracy $epsilon$ in Wasserstein-1 distance. No algorithm can compute an $epsilon$-accurate approximation to the spectrum of a normalized graph adjacency matrix with constant probability.
arXiv Detail & Related papers (2023-07-02T05:03:38Z)
Quantum simulation of perfect state transfer on weighted cubelike graphs [0.0]
A continuous-time quantum walk on a graph evolves according to the unitary operator $e-iAt$. Perfect state transfer (PST) in a quantum walk is the transfer of a quantum state from one node to another node with $100%$ fidelity.
arXiv Detail & Related papers (2021-10-30T10:42:54Z)
Perfect State Transfer in Weighted Cubelike Graphs [0.0]
A continuous-time quantum random walk describes the motion of a quantum mechanical particle on a graph. We generalize the PST or periodicity of cubelike graphs to that of weighted cubelike graphs.
arXiv Detail & Related papers (2021-09-26T13:44:44Z)
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)
How to Teach a Quantum Computer a Probability Distribution [0.0]
We explore teaching a coined discrete time quantum walk on a regular graph a probability distribution. We also discuss some hardware and software concerns as well as immediate applications and the several connections to machine learning.
arXiv Detail & Related papers (2021-04-15T02:41:27Z)
Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
We prove that the practical single loop accelerated gradient tracking needs $O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$. Our convergence rates improve significantly over the ones of $O(frac1epsilon5/7)$ and $O(fracLmu)5/7frac1 (1-sigma)1.5logfrac1epsilon)$.
arXiv Detail & Related papers (2021-04-06T15:34:14Z)
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)

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