Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2506.19538

Dynamics of discrete spacetimes with Quantum-enhanced Markov Chain Monte Carlo

Ferguson, Stuart, Arad Nasiri, Petros Wallden

Published Jun 24, 2025• 0 citations
arXivHTMLPDF

Abstract

Quantum algorithms offer the potential for significant computational advantages; however, in many cases, it remains unclear how these advantages can be practically realized. Causal Set Theory is a discrete, Lorentz-invariant approach to quantum gravity which may be well positioned to benefit from quantum computing. In this work, we introduce a quantum algorithm that investigates the dynamics of causal sets by sampling the space of causal sets, improving on classical methods. Our approach builds on the quantum-enhanced Markov chain Monte Carlo technique developed by Layden et al. [Nature 619, 282 (2023)], adapting it to sample from the constrained spaces required for application. This is done by adding a constraint term to the Hamiltonian of the system. A qubit Hamiltonian representing the Benincasa-Dowker action (the causal set equivalent of the Einstein-Hilbert action) is also derived and used in the algorithm as the problem Hamiltonian. We achieve a super-quadratic quantum scaling advantage and, under some conditions, demonstrate a greater potential compared to classical approaches than previously observed in unconstrained QeMCMC implementations.

DOI
10.48550/arxiv.2506.19538

Related papers

Benincasa-Dowker-Glaser causal set actions by quantum counting

Sean A. Adamson, Petros Wallden

Causal set theory is an approach to quantum gravity in which spacetime is fundamentally discrete while retaining local Lorentz invariance. The Benincasa-Dowker-Glaser action is the causal set equivalent to the Einstein-Hilbert action underpinning Einstein's general theory of relativity. We present a O ̃ ( n 2 ) running-time quantum algorithm to compute the Benincasa-Dowker-Glaser action in arbitrary spacetime dimensions for causal sets with n elements, which is asymptotically optimal and offers a polynomial speedup compared to all known classical or quantum algorithms. To do this, we prepare a uniform superposition over an O ( n 2 ) -size arbitrary subset of computational basis states encoding the classical description of a causal set of interest. We then construct depth O ̃ ( n ) -depth oracle circuits testing for different discrete volumes between pairs of causal set elements. Repeatedly performing a two-stage variant of quantum counting using these oracles yields the desired algorithm.

arXiv:2505.22217•Physical Review Research•Feb 11, 2026•0 citations

Quantum-enhanced Markov Chain Monte Carlo for Combinatorial Optimization

Kate V. Marshall, Daniel J. Egger, Michael Garn +4 more

Quantum computing offers an alternative paradigm for addressing combinatorial optimization problems compared to classical computing. Despite recent hardware improvements, the execution of empirical quantum optimization experiments at scales known to be hard for state-of-the-art classical solvers is not yet in reach. In this work, we offer a different way to approach combinatorial optimization with near-term quantum computing. Motivated by the promising results observed in using quantum-enhanced Markov chain Monte Carlo (QeMCMC) for approximating complicated probability distributions, we combine ideas of sampling from the device with QeMCMC together with warm-starting and parallel tempering, in the context of combinatorial optimization. We demonstrate empirically that our algorithm recovers the global optima for instances of the Maximum Independent Set problem (MIS) up to 117 decision variables using 117 qubits on IBM quantum hardware. We show early evidence of a scaling advantage of our algorithm compared to similar classical methods for the chosen instances of MIS. MIS is practically relevant across domains like financial services and molecular biology, and, in some cases, already difficult to solve to optimality classically with only a few hundred decision variables.

quant-pharXiv:2602.06171•Feb 9, 2026•0 citations

Quantum-enhanced Markov chain Monte Carlo for systems larger than a quantum computer

Stuart Ferguson, Petros Wallden

Quantum computers theoretically promise computational advantages in many tasks, but it is much less clear how such advantages can be maintained when using existing and near-term hardware that has limitations in the number and quality of its qubits. Layden [] proposed a promising application by introducing a quantum-enhanced Markov chain Monte Carlo (QeMCMC) approach to reduce the thermalization time required when sampling from hard probability distributions. In QeMCMC, the size of the required quantum computer scales linearly with the problem, placing limitations on the sizes of systems that can be considered. In this paper we introduce a framework to coarse grain the algorithm in such a way that the quantum computation can be performed using considerably smaller quantum computers and we term the method the coarse grained quantum-enhanced Markov chain Monte Carlo (CGQeMCMC). Example strategies within this framework are put to the test, with the quantum speedup persisting while using only n simulated qubits where n is the number of qubits required in the original QeMCMC—a quadratic reduction in resources. The coarse graining framework has the potential to be practically applicable in the near term as it requires very few qubits to approach classically intractable problem instances; in this case, only six simulated qubits suffice to gain an advantage compared with standard classical approaches when investigating the magnetization of a 36-spin system. Our method can be easily combined with other classical and quantum techniques and is adaptable to various quantum hardware specifications—in particular those with limited connectivity.

arXiv:2405.04247•Physical Review Research•Mar 3, 2025•4 citations

Quantum dynamical Hamiltonian Monte Carlo

Owen Lockwood, Peter Weiß, Filip Aronshtein +1 more

One of the open challenges in quantum computing is to find meaningful and practical methods to leverage quantum computation to accelerate classical machine-learning workflows. A ubiquitous problem in machine-learning workflows is sampling from probability distributions that we only have access to via their log probability. To this end, we extend the well-known Hamiltonian Monte Carlo (HMC) method for Markov chain Monte Carlo (MCMC) sampling to leverage quantum computation in a hybrid manner as a proposal function. Our new algorithm, Quantum Dynamical Hamiltonian Monte Carlo (QD-HMC), replaces the classical symplectic integration proposal step with simulations of quantum-coherent continuous-space dynamics on digital or analog quantum computers. We show that QD-HMC maintains key characteristics of HMC, such as maintaining the detailed balanced condition with momentum inversion, while also having the potential for polynomial speedups over its classical counterpart in certain scenarios. As sampling is a core subroutine in many forms of probabilistic inference, and MCMC in continuously parametrized spaces covers a large class of potential applications, this work widens the areas of applicability of quantum devices. Published by the American Physical Society 2024

arXiv:2403.01775•Physical Review Research•Aug 6, 2024•13 citations

Bounding speedup of quantum-enhanced Markov chain Monte Carlo

Alev Orfi, Dries Sels

Sampling tasks are a natural class of problems for quantum computers due to the probabilistic nature of the Born rule. Sampling from useful distributions on noisy quantum hardware remains a challenging problem. A recent paper [Layden, D. et al. Nature 619, 282-287 (2023)] proposed a quantum-enhanced Markov chain Monte Carlo algorithm where moves are generated by a quantum device and accepted or rejected by a classical algorithm. While this procedure is robust to noise and control imperfections, its potential for quantum advantage is unclear. Here we show that there is no speedup over classical sampling on a worst-case unstructured sampling problem. We present an upper bound to the Markov gap that rules out a speedup for any unital quantum proposal.

arXiv:2403.03087•Mar 5, 2024•0 citations

Experimental Realization of the Markov Chain Monte Carlo Algorithm on a Quantum Computer

Baptiste Claudon, Sergi Ramos-Calderer, Jean-Philip Piquemal

Quantum algorithms present a quadratically improved complexity over classical ones for certain sampling tasks. For instance, the Quantum Amplitude Estimation (QAE) algorithm promises to speed up the estimation of the mean of certain functions, given access to the quantum state corresponding to the probability distribution to be sampled from. Classically, samples are often obtained by simulating a Markov chain. In this work, we experimentally use encodings of Markov chains to prepare quantum states and run a quantum Markov Chain Monte Carlo (qMCMC) algorithm on Quantinuum System Model H2 and Quantinuum Helios quantum computers. We first demonstrate that it is possible to obtain accurate results by operating directly on the physical qubits. Crucially, to pave the way toward fault-tolerant execution, we also implement these algorithms using logical qubits protected by the Iceberg Quantum Error Detection (QED) code. By applying multiple rounds of mid-circuit QED during a random walk, we successfully catch and filter out hardware errors. These experiments demonstrate the feasibility of qMCMC on quantum hardware, bringing us closer to realizing quadratic quantum speedups with broad applications ranging from molecular modeling to machine learning and finance.

quant-pharXiv:2603.08395•Mar 10, 2026•0 citations
Quantum algorithms offer the potential for significant computational advantages; however, in many cases, it remains unclear how these advantages can be practically realized. Causal Set Theory is a discrete, Lorentz-invariant approach to quantum gravity which may be well positioned to benefit from quantum computing. In this work, we introduce a quantum algorithm that investigates the dynamics of causal sets by sampling the space of causal sets, improving on classical methods. Our approach builds on the quantum-enhanced Markov chain Monte Carlo technique developed by Layden et al. [Nature 619, 282 (2023)], adapting it to sample from the constrained spaces required for application. This is done by adding a constraint term to the Hamiltonian of the system. A qubit Hamiltonian representing the Benincasa-Dowker action (the causal set equivalent of the Einstein-Hilbert action) is also derived and used in the algorithm as the problem Hamiltonian. We achieve a super-quadratic quantum scaling advantage and, under some conditions, demonstrate a greater potential compared to classical approaches than previously observed in unconstrained QeMCMC implementations.
Causal set theory is an approach to quantum gravity in which spacetime is fundamentally discrete while retaining local Lorentz invariance. The Benincasa-Dowker-Glaser action is the causal set equivalent to the Einstein-Hilbert action underpinning Einstein's general theory of relativity. We present a O ̃ ( n 2 ) running-time quantum algorithm to compute the Benincasa-Dowker-Glaser action in arbitrary spacetime dimensions for causal sets with n elements, which is asymptotically optimal and offers a polynomial speedup compared to all known classical or quantum algorithms. To do this, we prepare a uniform superposition over an O ( n 2 ) -size arbitrary subset of computational basis states encoding the classical description of a causal set of interest. We then construct depth O ̃ ( n ) -depth oracle circuits testing for different discrete volumes between pairs of causal set elements. Repeatedly performing a two-stage variant of quantum counting using these oracles yields the desired algorithm.
Quantum computing offers an alternative paradigm for addressing combinatorial optimization problems compared to classical computing. Despite recent hardware improvements, the execution of empirical quantum optimization experiments at scales known to be hard for state-of-the-art classical solvers is not yet in reach. In this work, we offer a different way to approach combinatorial optimization with near-term quantum computing. Motivated by the promising results observed in using quantum-enhanced Markov chain Monte Carlo (QeMCMC) for approximating complicated probability distributions, we combine ideas of sampling from the device with QeMCMC together with warm-starting and parallel tempering, in the context of combinatorial optimization. We demonstrate empirically that our algorithm recovers the global optima for instances of the Maximum Independent Set problem (MIS) up to 117 decision variables using 117 qubits on IBM quantum hardware. We show early evidence of a scaling advantage of our algorithm compared to similar classical methods for the chosen instances of MIS. MIS is practically relevant across domains like financial services and molecular biology, and, in some cases, already difficult to solve to optimality classically with only a few hundred decision variables.
Quantum computers theoretically promise computational advantages in many tasks, but it is much less clear how such advantages can be maintained when using existing and near-term hardware that has limitations in the number and quality of its qubits. Layden [] proposed a promising application by introducing a quantum-enhanced Markov chain Monte Carlo (QeMCMC) approach to reduce the thermalization time required when sampling from hard probability distributions. In QeMCMC, the size of the required quantum computer scales linearly with the problem, placing limitations on the sizes of systems that can be considered. In this paper we introduce a framework to coarse grain the algorithm in such a way that the quantum computation can be performed using considerably smaller quantum computers and we term the method the coarse grained quantum-enhanced Markov chain Monte Carlo (CGQeMCMC). Example strategies within this framework are put to the test, with the quantum speedup persisting while using only n simulated qubits where n is the number of qubits required in the original QeMCMC—a quadratic reduction in resources. The coarse graining framework has the potential to be practically applicable in the near term as it requires very few qubits to approach classically intractable problem instances; in this case, only six simulated qubits suffice to gain an advantage compared with standard classical approaches when investigating the magnetization of a 36-spin system. Our method can be easily combined with other classical and quantum techniques and is adaptable to various quantum hardware specifications—in particular those with limited connectivity.
One of the open challenges in quantum computing is to find meaningful and practical methods to leverage quantum computation to accelerate classical machine-learning workflows. A ubiquitous problem in machine-learning workflows is sampling from probability distributions that we only have access to via their log probability. To this end, we extend the well-known Hamiltonian Monte Carlo (HMC) method for Markov chain Monte Carlo (MCMC) sampling to leverage quantum computation in a hybrid manner as a proposal function. Our new algorithm, Quantum Dynamical Hamiltonian Monte Carlo (QD-HMC), replaces the classical symplectic integration proposal step with simulations of quantum-coherent continuous-space dynamics on digital or analog quantum computers. We show that QD-HMC maintains key characteristics of HMC, such as maintaining the detailed balanced condition with momentum inversion, while also having the potential for polynomial speedups over its classical counterpart in certain scenarios. As sampling is a core subroutine in many forms of probabilistic inference, and MCMC in continuously parametrized spaces covers a large class of potential applications, this work widens the areas of applicability of quantum devices. Published by the American Physical Society 2024
Sampling tasks are a natural class of problems for quantum computers due to the probabilistic nature of the Born rule. Sampling from useful distributions on noisy quantum hardware remains a challenging problem. A recent paper [Layden, D. et al. Nature 619, 282-287 (2023)] proposed a quantum-enhanced Markov chain Monte Carlo algorithm where moves are generated by a quantum device and accepted or rejected by a classical algorithm. While this procedure is robust to noise and control imperfections, its potential for quantum advantage is unclear. Here we show that there is no speedup over classical sampling on a worst-case unstructured sampling problem. We present an upper bound to the Markov gap that rules out a speedup for any unital quantum proposal.
Quantum algorithms present a quadratically improved complexity over classical ones for certain sampling tasks. For instance, the Quantum Amplitude Estimation (QAE) algorithm promises to speed up the estimation of the mean of certain functions, given access to the quantum state corresponding to the probability distribution to be sampled from. Classically, samples are often obtained by simulating a Markov chain. In this work, we experimentally use encodings of Markov chains to prepare quantum states and run a quantum Markov Chain Monte Carlo (qMCMC) algorithm on Quantinuum System Model H2 and Quantinuum Helios quantum computers. We first demonstrate that it is possible to obtain accurate results by operating directly on the physical qubits. Crucially, to pave the way toward fault-tolerant execution, we also implement these algorithms using logical qubits protected by the Iceberg Quantum Error Detection (QED) code. By applying multiple rounds of mid-circuit QED during a random walk, we successfully catch and filter out hardware errors. These experiments demonstrate the feasibility of qMCMC on quantum hardware, bringing us closer to realizing quadratic quantum speedups with broad applications ranging from molecular modeling to machine learning and finance.