Quantum walk mixing is faster than classical on periodic lattices
- URL: http://arxiv.org/abs/2309.16352v1
- Date: Thu, 28 Sep 2023 11:23:10 GMT
- Title: Quantum walk mixing is faster than classical on periodic lattices
- Authors: Shyam Dhamapurkar and Xiu-Hao Deng
- Abstract summary: 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.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This work focuses on the quantum mixing time, which is crucial for efficient
quantum sampling and algorithm performance. We extend Richter's previous
analysis of continuous time quantum walks on the periodic lattice
$\mathbb{Z}_{n_1}\times \mathbb{Z}_{n_2}\times \dots \times \mathbb{Z}_{n_d}$,
allowing for non-identical dimensions $n_i$. We present two quantum walks that
achieve faster mixing compared to classical random walks. The first is a
coordinate-wise quantum walk with a mixing time of $O\left(\left(\sum{i=1}^{d}
n_i \right) \log{(d/\epsilon)}\right)$ and $O(d \log(d/\epsilon))$
measurements. The second is a continuous-time quantum walk with
$O(\log(1/\epsilon))$ measurements, conjectured to have a mixing time of
$O\left(\sum_{i=1}^d n_i(\log(n_1))^2 \log(1/\epsilon)\right)$. Our results
demonstrate a quadratic speedup over classical mixing times on the generalized
periodic lattice. We provide analytical evidence and numerical simulations
supporting the conjectured faster mixing time. The ultimate goal is to prove
the general conjecture for quantum walks on regular graphs.
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.
Even with sublinear barriers, we use Feynman-Kac techniques to lift classical to quantum ones establishing tight lower bound $T_mathrmmix = 2Omega(nalpha)$.
arXiv Detail & Related papers (2024-11-06T22:51:27Z) - Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer.
Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model.
We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
arXiv Detail & Related papers (2024-05-14T15:28:37Z) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry.
The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time.
Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
arXiv Detail & Related papers (2024-05-02T10:29:06Z) - 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) - 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) - Quantum Algorithms for Sampling Log-Concave Distributions and Estimating
Normalizing Constants [8.453228628258778]
We develop quantum algorithms for sampling logconcave distributions and for estimating their normalizing constants.
We exploit quantum analogs of the Monte Carlo method and quantum walks.
We also prove a $1/epsilon1-o(1)$ quantum lower bound for estimating normalizing constants.
arXiv Detail & Related papers (2022-10-12T19:10:43Z) - The Quantum and Classical Streaming Complexity of Quantum and Classical
Max-Cut [0.07614628596146598]
We investigate the space complexity of two graph streaming problems: Max-Cut and its quantum analogue, Quantum Max-Cut.
Our work resolves the quantum and classical approximability of quantum and classical Max-Cut using $textrmo(n)$ space.
arXiv Detail & Related papers (2022-06-01T03:40:56Z) - 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) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
We present an efficient read-out protocol that yields the classical vector form of the generated state.
Our protocol suits the case that the output state lies in the row space of the input matrix.
One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
arXiv Detail & Related papers (2020-04-14T11:05:26Z) - Quantum Coupon Collector [62.58209964224025]
We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements.
We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
arXiv Detail & Related papers (2020-02-18T16:14:55Z)
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.