Related papers: Quantized Markov chain couplings that prepare Qsamples

Quantized Markov chain couplings that prepare Qsamples

URL: http://arxiv.org/abs/2504.02651v1
Date: Thu, 03 Apr 2025 14:48:47 GMT
Title: Quantized Markov chain couplings that prepare Qsamples
Authors: Kristan Temme, Pawel Wocjan,
Abstract summary: We present a novel approach to quantizing Markov chains.<n>The approach is based on the Markov chain coupling method.<n>We show that the convergence time of the quantum map is directly related to the coupling time of the Markov chain.
Score: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We present a novel approach to quantizing Markov chains. The approach is based on the Markov chain coupling method, which is frequently used to prove fast mixing. Given a particular coupling, e.g., a grand coupling, we construct a completely positive and trace preserving map. This quantum map has a unique fixed point, which corresponds to the quantum sample (qsample) of the classical Markov chain's stationary distribution. We show that the convergence time of the quantum map is directly related to the coupling time of the Markov chain coupling.

Related papers

Characterizing Dependence of Samples along the Langevin Dynamics and Algorithms via Contraction of $Φ$-Mutual Information [16.54557731304283]
We study the question of how fast the samples become approximately independent along popular Markov chains for continuous-space sampling. Our proof technique is based on showing the Strong Data Processing Inequalities (SDPIs) hold along the Markov chains.
arXiv Detail & Related papers (2024-02-26T23:05:02Z)
Ito Diffusion Approximation of Universal Ito Chains for Sampling, Optimization and Boosting [64.0722630873758]
We consider rather general and broad class of Markov chains, Ito chains, that look like Euler-Maryama discretization of some Differential Equation. We prove the bound in $W_2$-distance between the laws of our Ito chain and differential equation.
arXiv Detail & Related papers (2023-10-09T18:38:56Z)
Quantum vs classical Markov chains; Exactly solvable examples [0.0]
A quantum Hamiltonian H is obtained by a similarity transformation of the fundamental transition probability matrix K. The evolution of the classical and quantum Markov chains are described.
arXiv Detail & Related papers (2022-12-21T01:24:23Z)
Enabling Quantum Speedup of Markov Chains using a Multi-level Approach [0.0]
Quantum speedup for mixing a Markov chain can be achieved based on the construction of slowly-varying $r$ Markov chains. We show that the density function of a low-resolution Markov chain can be used to warm start the Markov chain with high resolution.
arXiv Detail & Related papers (2022-10-25T15:17:52Z)
A rapidly mixing Markov chain from any gapped quantum many-body system [2.321323878201932]
We consider a bit string $x$ from a $pi(x)=|langle x|psirangle|2$, where $psi$ is the unique ground state of a local Hamiltonian $H$. Our main result describes a direct link between the inverse spectral gap of $H$ and the mixing time of an associated continuous-time Markov Chain with steady state $pi$.
arXiv Detail & Related papers (2022-07-14T16:38:42Z)
Sampling in Combinatorial Spaces with SurVAE Flow Augmented MCMC [83.48593305367523]
Hybrid Monte Carlo is a powerful Markov Chain Monte Carlo method for sampling from complex continuous distributions. We introduce a new approach based on augmenting Monte Carlo methods with SurVAE Flows to sample from discrete distributions. We demonstrate the efficacy of our algorithm on a range of examples from statistics, computational physics and machine learning, and observe improvements compared to alternative algorithms.
arXiv Detail & Related papers (2021-02-04T02:21:08Z)
Pretty good quantum state transfer on isotropic and anisotropic Heisenberg spin chains with tailored site dependent exchange couplings [68.8204255655161]
We consider chains with isotropic and anisotropic Heisenberg Hamiltonian with up to 100 spins. We consider short transferred times, in particular shorter than those achievable with known time-dependent control schemes.
arXiv Detail & Related papers (2021-01-08T19:32:10Z)
Sampling Overhead Analysis of Quantum Error Mitigation: Uncoded vs. Coded Systems [69.33243249411113]
We show that Pauli errors incur the lowest sampling overhead among a large class of realistic quantum channels. We conceive a scheme amalgamating QEM with quantum channel coding, and analyse its sampling overhead reduction compared to pure QEM.
arXiv Detail & Related papers (2020-12-15T15:51:27Z)
From stochastic spin chains to quantum Kardar-Parisi-Zhang dynamics [68.8204255655161]
We introduce the asymmetric extension of the Quantum Symmetric Simple Exclusion Process. We show that the time-integrated current of fermions defines a height field which exhibits a quantum non-linear dynamics.
arXiv Detail & Related papers (2020-01-13T14:30:36Z)
Targeted stochastic gradient Markov chain Monte Carlo for hidden Markov models with rare latent states [48.705095800341944]
Markov chain Monte Carlo (MCMC) algorithms for hidden Markov models often rely on the forward-backward sampler. This makes them computationally slow as the length of the time series increases, motivating the development of sub-sampling-based approaches. We propose a targeted sub-sampling approach that over-samples observations corresponding to rare latent states when calculating the gradient of parameters associated with them.
arXiv Detail & Related papers (2018-10-31T17:44:20Z)
The $χ^2$-divergence and Mixing times of quantum Markov processes [0.0]
We introduce quantum versions of the $chi2$-divergence, provide a detailed analysis of their properties, and apply them in the investigation of mixing times of quantum Markov processes. A strict spectral bound to the convergence rate can be given for time-discrete as well as for time-continuous quantum Markov processes.
arXiv Detail & Related papers (2010-05-13T15:56:12Z)

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