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

• 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)
• Alternating quantum-emitter chains: Exceptional-point phase transition, edge state, and quantum walks [0.0]
  We study the long-range hopping limit of a one-dimensional array of $N$ equal-distanced quantum emitters in free space. For two species of emitters in an alternating arrangement, the single excitation sector exhibits non-Hermitian spectral singularities known as exceptional points. We unveil an unconventional phase transition, dubbed exceptional-point phase transition, from the collective to individual spontaneous emission behaviors.
  arXiv  Detail & Related papers  (2023-05-25T13:45:30Z)
• A hybrid quantum algorithm to detect conical intersections [39.58317527488534]
  We show that for real molecular Hamiltonians, the Berry phase can be obtained by tracing a local optimum of a variational ansatz along the chosen path. We demonstrate numerically the application of our algorithm on small toy models of the formaldimine molecule.
  arXiv  Detail & Related papers  (2023-04-12T18:00:01Z)
• 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)
• Quantum Statistical Complexity Measure as a Signalling of Correlation Transitions [55.41644538483948]
  We introduce a quantum version for the statistical complexity measure, in the context of quantum information theory, and use it as a signalling function of quantum order-disorder transitions. We apply our measure to two exactly solvable Hamiltonian models, namely: the $1D$-Quantum Ising Model and the Heisenberg XXZ spin-$1/2$ chain. We also compute this measure for one-qubit and two-qubit reduced states for the considered models, and analyse its behaviour across its quantum phase transitions for finite system sizes as well as in the thermodynamic limit by using Bethe ansatz.
  arXiv  Detail & Related papers  (2020-02-05T00:45:21Z)

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.