Quasi-optimal quantum Markov chain spectral gap estimation

• URL: http://arxiv.org/abs/2601.07601v1
• Date: Mon, 12 Jan 2026 14:50:46 GMT
• Title: Quasi-optimal quantum Markov chain spectral gap estimation
• Authors: Adam Connolly, Steven Herbert, Julien Sorci,
• Abstract summary: This paper proposes a quantum algorithm for Markov chain spectral gap estimation.<n>Knowing a Markov chain's spectral gap can speed-up sampling in Markov chain Monte Carlo.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper proposes a quantum algorithm for Markov chain spectral gap estimation that is quasi-optimal (i.e., optimal up to a polylogarithmic factor) in the number of vertices for all parameters, and additionally quasi-optimal in the reciprocal of the spectral gap itself, if the permitted relative error is above some critical value. In particular, these results constitute an almost quadratic advantage over the best-possible classical algorithm. Our algorithm also improves on the quantum state of the art, and we contend that this is not just theoretically interesting but also potentially practically impactful in real-world applications: knowing a Markov chain's spectral gap can speed-up sampling in Markov chain Monte Carlo. Our approach uses the quantum singular value transformation, and as a result we also develop some theory around block-encoding Markov chain transition matrices, which is potentially of independent interest. In particular, we introduce explicit block-encoding methods for the transition matrices of two algebraically-defined classes of Markov chains.

Related papers

• Semidefinite Programming for Quantum Channel Learning [35.18016233072556]
  Semidefinite Programming (SDP) can be applied to solve the fidelity optimization problem with respect to the Choi matrix.<n>We have tested several commercially available SDP solvers, all of which allowed for the reconstruction of quantum channels of different forms.<n>This suggests that a relatively small Kraus rank quantum channel is typically sufficient to describe experimentally observed classical data.
  arXiv  Detail & Related papers  (2026-01-18T17:26:45Z)
• Quantum Approximate Optimization Algorithm for MIMO with Quantized b-bit Beamforming [47.98440449939344]
  Multiple-input multiple-output (MIMO) is critical for 6G communication, offering improved spectral efficiency and reliability.<n>This paper explores the use of the Quantum Approximate Optimization Algorithm (QAOA) and alternating optimization to address the problem of b-bit quantized phase shifters both at the transmitter and the receiver.<n>We demonstrate that the structure of this quantized beamforming problem aligns naturally with hybrid-classical methods like QAOA, as the phase shifts used in beamforming can be directly mapped to rotation gates in a quantum circuit.
  arXiv  Detail & Related papers  (2025-10-07T17:53:02Z)
• Quantum Markov chain Monte Carlo with programmable quantum simulators [0.0]
  We show how to address the conditions for ergodicity and sampling from distributions of quantum states using the Many-Body Localized phase.<n>The algorithm can be implemented on any quantum hardware capable of simulating the Floquet dynamics of a 1D Ising chain with nearest-neighbor interactions.
  arXiv  Detail & Related papers  (2025-05-27T14:37:35Z)
• QAMA: Scalable Quantum Annealing Multi-Head Attention Operator for Deep Learning [48.12231190677108]
  Quantum Annealing Multi-Head Attention (QAMA) is proposed, a novel drop-in operator that reformulates attention as an energy-based Hamiltonian optimization problem.<n>In this framework, token interactions are encoded into binary quadratic terms, and quantum annealing is employed to search for low-energy configurations.<n> Empirically, evaluation on both natural language and vision benchmarks shows that, across tasks, accuracy deviates by at most 2.7 points from standard multi-head attention.
  arXiv  Detail & Related papers  (2025-04-15T11:29:09Z)
• Quantum Speedup for Nonreversible Markov Chains [0.0]
  It has been discussed that Markov chains problems could be solved significantly faster using quantum computing.<n>This study develops quantum algorithmic techniques to accelerate nonreversible processes.<n>Such an up-to-exponential quantum speedup is likely to have a decisive impact on many applications.
  arXiv  Detail & Related papers  (2025-01-10T11:09:40Z)
• Quantum enhanced Markov chains require fine-tuned quenches [0.0]
  Quantum-enhanced Markov chain Monte Carlo is proposed as a method for robust quantum speedup on imperfect quantum devices. We identify competing factors that limit the algorithm's performance. Specifically, we show that in the long-time limit, the gap of the Markov chain is bounded by the inverse participation ratio of the classical states in the eigenstate basis.
  arXiv  Detail & Related papers  (2024-08-15T01:40:07Z)
• Collective quantum enhancement in critical quantum sensing [37.69303106863453]
  Critical quantum sensing (CQS) protocols can be realized using finite-component phase transitions.<n>We show that a collective quantum advantage can be achieved in a multipartite CQS protocol using a chain of parametrically coupled critical resonators.
  arXiv  Detail & Related papers  (2024-07-25T14:08:39Z)
• Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processes [32.07657827173262]
  We introduce an innovative quantum framework for the agent's engagement with an unknown MDP.<n>We show that the quantum advantage in mean estimation leads to exponential advancements in regret guarantees for infinite horizon Reinforcement Learning.
  arXiv  Detail & Related papers  (2023-10-18T03:17:51Z)
• A quantum advantage over classical for local max cut [48.02822142773719]
  Quantum optimization approximation algorithm (QAOA) has a computational advantage over comparable local classical techniques on degree-3 graphs. Results hint that even small-scale quantum computation, which is relevant to the current state-of the art quantum hardware, could have significant advantages over comparably simple classical.
  arXiv  Detail & Related papers  (2023-04-17T16:42:05Z)
• Quantum vs classical Markov chains; Exactly solvable examples [0.0]
  A coinless quantisation procedure of general reversible Markov chains on graphs is presented.<n>A quantum Hamiltonian H is obtained by a similarity transformation of the fundamental transition probability matrix K.
  arXiv  Detail & Related papers  (2022-12-21T01:24:23Z)
• Markov Chain Monte-Carlo Enhanced Variational Quantum Algorithms [0.0]
  We introduce a variational quantum algorithm that uses Monte Carlo techniques to place analytic bounds on its time-complexity. We demonstrate both the effectiveness of our technique and the validity of our analysis through quantum circuit simulations for MaxCut instances.
  arXiv  Detail & Related papers  (2021-12-03T23:03:44Z)
• 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)

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.