Space-efficient Quantization Method for Reversible Markov Chains

• URL: http://arxiv.org/abs/2206.06886v1
• Date: Tue, 14 Jun 2022 14:41:56 GMT
• Title: Space-efficient Quantization Method for Reversible Markov Chains
• Authors: Chen-Fu Chiang, Anirban Chowdhury, Pawel Wocjan
• Abstract summary: Szegedy showed how to construct a quantum walk $W(P)$ for any reversible Markov chain $P$ We show that it is possible to avoid this doubling of state space for certain Markov chains.
• Score: 1.558664512158522
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In a seminal paper, Szegedy showed how to construct a quantum walk $W(P)$ for any reversible Markov chain $P$ such that its eigenvector with eigenphase $0$ is a quantum sample of the limiting distribution of the random walk and its eigenphase gap is quadratically larger than the spectral gap of $P$. The standard construction of Szegedy's quantum walk requires an ancilla register of Hilbert-space dimension equal to the size of the state space of the Markov chain. We show that it is possible to avoid this doubling of state space for certain Markov chains that employ a symmetric proposal probability and a subsequent accept/reject probability to sample from the Gibbs distribution. For such Markov chains, we give a quantization method which requires an ancilla register of dimension equal to only the number of different energy values, which is often significantly smaller than the size of the state space. To accomplish this, we develop a technique for block encoding Hadamard products of matrices which may be of wider interest.

Related papers

• Exact path integrals on half-line in quantum cosmology with a fluid clock and aspects of operator ordering ambiguity [0.0]
  We perform $textitexact$ half-line path integral quantization of flat, homogeneous cosmological models containing a perfect fluid acting as an internal clock. We argue that a particular ordering prescription in the quantum theory can preserve two symmetries.
  arXiv  Detail & Related papers  (2025-01-20T19:00:02Z)
• Quantum Homogenization as a Quantum Steady State Protocol on NISQ Hardware [42.52549987351643]
  Quantum homogenization is a reservoir-based quantum state approximation protocol. We extend the standard quantum homogenization protocol to the dynamically-equivalent ($mathttSWAP$)$alpha$ formulation. We show that our proposed protocol yields a completely positive, trace preserving (CPTP) map under which the code subspace is correctable.
  arXiv  Detail & Related papers  (2024-12-19T05:50:54Z)
• Efficient Eigenstate Preparation in an Integrable Model with Hilbert Space Fragmentation [42.408991654684876]
  We consider the preparation of all the eigenstates of spin chains using quantum circuits. We showivities of the growth is also achievable for interacting models where the interaction between the particles is sufficiently simple.
  arXiv  Detail & Related papers  (2024-11-22T18:57:08Z)
• Geometric Quantum Machine Learning with Horizontal Quantum Gates [41.912613724593875]
  We propose an alternative paradigm for the symmetry-informed construction of variational quantum circuits. We achieve this by introducing horizontal quantum gates, which only transform the state with respect to the directions to those of the symmetry. For a particular subclass of horizontal gates based on symmetric spaces, we can obtain efficient circuit decompositions for our gates through the KAK theorem.
  arXiv  Detail & Related papers  (2024-06-06T18:04:39Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• 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)
• Markov chains with doubly stochastic transition matrices and application to a sequence of non-selective quantum measurements [0.0]
  A time-dependent finite-state Markov chain that uses doubly transition matrices is considered. entropy that describe the randomness of the probability vectors, and also the randomness of the discrete paths, are studied.
  arXiv  Detail & Related papers  (2022-03-16T14:58:38Z)
• Preserving quantum correlations and coherence with non-Markovianity [50.591267188664666]
  We demonstrate the usefulness of non-Markovianity for preserving correlations and coherence in quantum systems. For covariant qubit evolutions, we show that non-Markovianity can be used to preserve quantum coherence at all times.
  arXiv  Detail & Related papers  (2021-06-25T11:52:51Z)
• Random quantum circuits anti-concentrate in log depth [118.18170052022323]
  We study the number of gates needed for the distribution over measurement outcomes for typical circuit instances to be anti-concentrated. Our definition of anti-concentration is that the expected collision probability is only a constant factor larger than if the distribution were uniform. In both the case where the gates are nearest-neighbor on a 1D ring and the case where gates are long-range, we show $O(n log(n)) gates are also sufficient.
  arXiv  Detail & Related papers  (2020-11-24T18:44:57Z)
• Spectral statistics in constrained many-body quantum chaotic systems [0.0]
  We study the spectral statistics of spatially-extended many-body quantum systems with on-site Abelian symmetries or local constraints. In particular, we analytically argue that in a system of length $L$ that conserves the $mth$ multipole moment, $t_mathrmTh$ scales subdiffusively as $L2(m+1)$.
  arXiv  Detail & Related papers  (2020-09-24T17:59:57Z)
• Mapping quantum random walks onto a Markov chain by mapping a unitary transformation to a higher dimension of an irreducible matrix [0.0]
  A new process, discrete in time and space, yields the results of both a random walk and a quantum random walk. Results for a quantum random walk on infinite and finite lines are introduced.
  arXiv  Detail & Related papers  (2020-06-19T11:50:07Z)

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.