Quantum walks advantage on the dihedral group for uniform sampling problem

• URL: http://arxiv.org/abs/2312.15693v1
• Date: Mon, 25 Dec 2023 11:21:55 GMT
• Title: Quantum walks advantage on the dihedral group for uniform sampling problem
• Authors: Shyam Dhamapurkar, Yuhang Dang, Saniya Wagh, and Xiu-Hao Deng
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Random walk algorithms, including sampling and approximations, have played a significant role in statistical physics and theoretical computer science. 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. Here, we investigate the continuous-time quantum walks on Cayley graphs of the dihedral group $D_{2n}$ for odd $n$, generated by the smallest inverse closed symmetric subset. We present a significant finding that, in contrast to the classical mixing time on these Cayley graphs, which is typically of order $O(n^2 \log(2n/\epsilon))$, the continuous-time quantum walk mixing time on $D_{2n}$ is of order $O(n (\log n)^5 \log(1/\epsilon))$, achieving a quadratic improvement over the classical case. Our paper advances the general understanding of quantum walk mixing on Cayley graphs, highlighting the improved mixing time achieved by continuous-time quantum walks on $D_{2n}$. This work has potential applications in algorithms for sampling non-abelian groups, graph isomorphism tests, etc.

Related papers

• Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
  We present a quantum generalization of these tools through a generic bottleneck lemma. This lemma focuses on quantum measures of distance, analogous to the classical Hamming distance but rooted in uniquely quantum principles. We show how to lift classical slow mixing results in the presence of a transverse field using Poisson Feynman-Kac techniques.
  arXiv  Detail & Related papers  (2024-11-06T22:51:27Z)
• A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [102.46640028830441]
  We introduce the Optimistic Matrix Multiplicative Weights Update (OMMWU) algorithm and establish its average-iterate convergence complexity as $mathcalO(d/epsilon)$ to $epsilon$-Nash equilibria. This quadratic speed-up sets a new benchmark for computing $epsilon$-Nash equilibria in quantum zero-sum games.
  arXiv  Detail & Related papers  (2023-11-17T20:38:38Z)
• Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions [13.16814860487575]
  We present quantum algorithms for sampling from nonlogconcave probability distributions. $f$ can be written as a finite sum $f(x):= frac1Nsum_k=1N f_k(x)$.
  arXiv  Detail & Related papers  (2023-10-17T17:55:32Z)
• Quantum walk mixing is faster than classical on periodic lattices [0.0]
  We present two quantum walks that achieve faster mixing compared to classical random walks. The ultimate goal is to prove the general conjecture for quantum walks on regular graphs.
  arXiv  Detail & Related papers  (2023-09-28T11:23:10Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• Improvement of quantum walk-based search algorithms in single marked vertex graphs [0.0]
  Amplitude amplification is usually used to amplify success probability, but the souffl'e problems follow. In this work, we define generalized interpolated quantum walks, which can both improve the success probability of search algorithms and avoid the souffl'e problems.
  arXiv  Detail & Related papers  (2022-09-09T07:43:46Z)
• Discrete Quantum Walks on the Symmetric Group [0.0]
  In quantum walks, the propagation is governed by quantum mechanical rules; generalizing random walks to the quantum setting. In this paper we investigate the discrete time coined quantum walk (DTCQW) model using tools from non-commutative Fourier analysis. Specifically, we are interested in characterizing the DTCQW on Cayley graphs generated by the symmetric group ($sym$) with appropriate generating sets.
  arXiv  Detail & Related papers  (2022-03-28T23:48:08Z)
• 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)
• Average-case Speedup for Product Formulas [69.68937033275746]
  Product formulas, or Trotterization, are the oldest and still remain an appealing method to simulate quantum systems. We prove that the Trotter error exhibits a qualitatively better scaling for the vast majority of input states. Our results open doors to the study of quantum algorithms in the average case.
  arXiv  Detail & Related papers  (2021-11-09T18:49:48Z)
• 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)
• 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)

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.