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 [D. Layden et al., Nature (London) 619, 282 (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.
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 [D. Layden et al., Nature (London) 619, 282 (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.
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-enhanced Markov chain Monte Carlo, an algorithm in which configurations are proposed through a measured quantum quench and accepted or rejected by a classical algorithm, has been proposed as a possible method for robust quantum speedup on imperfect quantum devices. While this procedure is resilient to noise and control imperfections, the potential for quantum advantage is unclear. By upper-bounding the gap of the Markov chain, we identify competing factors that limit the algorithm's performance. One needs the quantum dynamics to efficiently delocalize the system over a range of classical states, but it is also detrimental to introduce too much entropy through the quench. 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, showing there is no advantage when quenching to an ergodic system. For the paradigmatic Sherrington-Kirkpatrick and three-spin model, we identify the regime of optimal spectral gap scaling and link it to the system's eigenstate properties.
Sampling from complicated probability distributions is a hard computational problem arising in many fields, including statistical physics, optimization, and machine learning. Quantum computers have recently been used to sample from complicated distributions that are hard to sample from classically, but which seldom arise in applications. Here we introduce a quantum algorithm to sample from distributions that pose a bottleneck in several applications, which we implement on a superconducting quantum processor. The algorithm performs Markov chain Monte Carlo (MCMC), a popular iterative sampling technique, to sample from the Boltzmann distribution of classical Ising models. In each step, the quantum processor explores the model in superposition to propose a random move, which is then accepted or rejected by a classical computer and returned to the quantum processor, ensuring convergence to the desired Boltzmann distribution. We find that this quantum algorithm converges in fewer iterations than common classical MCMC alternatives on relevant problem instances, both in simulations and experiments. It therefore opens a new path for quantum computers to solve useful--not merely difficult--problems in the near term.
Sampling problems are widely regarded as the task for which quantum computers can most readily provide a quantum advantage. Leveraging this feature, the quantum-enhanced Markov chain Monte Carlo [Layden , Nature 619, 282–287 (2023)] has been proposed recently, where sampling from a quantum computer is used as a proposal distribution and convergence to a target distribution is accelerated. However, guaranteeing convergence to the target distribution typically forces one to impose restrictive symmetry constraints on the quantum circuit, which makes it hard to design good proposal distributions and prevents making full use of the advantage of a quantum computer. We explore a hybrid quantum-classical Markov chain Monte Carlo framework that combines a quantum circuit with a generative neural sampler (GNS). The GNS is trained on quantum samples and acts as a classical surrogate to efficiently emulate quantum outputs, thereby lifting circuit constraints. We apply this method to Boltzmann sampling of spin glasses using proposals trained with a quantum approximate optimization algorithm circuit. This approach outperforms conventional methods, showing a polynomial speedup (over cubic) in spectral gap compared with uniform proposals. Notably, it maintains similar acceleration even without parameter optimization. These results establish the method as a viable sampling-based quantum algorithm for noisy intermediate-scale quantum devices and highlight its potential for solving practical problems with quantum computation.
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.
Quantum-enhanced Markov chain Monte Carlo, an algorithm in which configurations are proposed through a measured quantum quench and accepted or rejected by a classical algorithm, has been proposed as a possible method for robust quantum speedup on imperfect quantum devices. While this procedure is resilient to noise and control imperfections, the potential for quantum advantage is unclear. By upper-bounding the gap of the Markov chain, we identify competing factors that limit the algorithm's performance. One needs the quantum dynamics to efficiently delocalize the system over a range of classical states, however, it is also detrimental to introduce too much entropy through the quench. 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, showing there is no advantage when quenching to an ergodic system. For the paradigmatic Sherrington-Kirkpatrick and 3-spin model, we identify the regime of optimal spectral gap scaling and link it to the system's eigenstate properties.