Bounding speedup of quantum-enhanced Markov chain Monte Carlo
- URL: http://arxiv.org/abs/2403.03087v1
- Date: Tue, 5 Mar 2024 16:20:01 GMT
- Title: Bounding speedup of quantum-enhanced Markov chain Monte Carlo
- Authors: Alev Orfi and Dries Sels
- Abstract summary: 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.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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.
Related papers
- Robust Extraction of Thermal Observables from State Sampling and
Real-Time Dynamics on Quantum Computers [49.1574468325115]
We introduce a technique that imposes constraints on the density of states, most notably its non-negativity, and show that this way, we can reliably extract Boltzmann weights from noisy time series.
Our work enables the implementation of the time-series algorithm on present-day quantum computers to study finite temperature properties of many-body quantum systems.
arXiv Detail & Related papers (2023-05-30T18:00:05Z) - Sample-size-reduction of quantum states for the noisy linear problem [0.0]
We show that it is possible to reduce a quantum sample size in a quantum random access memory (QRAM) to the linearithmic order.
We achieve a shorter run-time for the noisy linear problem.
arXiv Detail & Related papers (2023-01-08T05:53:17Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms.
We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z) - Quantum-assisted Monte Carlo algorithms for fermions [5.625946422295428]
We propose a family of scalable quantum-assisted Monte Carlo algorithms where the quantum computer is used at its minimal cost.
We show that the hybrid Monte Carlo framework is a general way to suppress errors in the ground state obtained from classical algorithms.
arXiv Detail & Related papers (2022-05-30T07:49:22Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle.
We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm.
We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z) - Quantum-enhanced Markov chain Monte Carlo [0.22166578153935784]
We introduce a quantum algorithm to sample from distributions that pose a bottleneck in several applications.
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.
We find that this quantum algorithm converges in fewer iterations than common classical MCMC alternatives on relevant problem instances.
arXiv Detail & Related papers (2022-03-23T15:50:12Z) - Quantum algorithm for stochastic optimal stopping problems with
applications in finance [60.54699116238087]
The famous least squares Monte Carlo (LSM) algorithm combines linear least square regression with Monte Carlo simulation to approximately solve problems in optimal stopping theory.
We propose a quantum LSM based on quantum access to a process, on quantum circuits for computing the optimal stopping times, and on quantum techniques for Monte Carlo.
arXiv Detail & Related papers (2021-11-30T12:21:41Z) - Accelerated quantum Monte Carlo with mitigated error on noisy quantum
computer [4.762232147934851]
We introduce a novel non-variational algorithm using quantum simulation as a subroutine to accelerate quantum Monte Carlo.
The proposed quantum algorithm is applicable to near-term noisy quantum hardware.
arXiv Detail & Related papers (2021-06-18T02:45:14Z) - Imaginary Time Propagation on a Quantum Chip [50.591267188664666]
Evolution in imaginary time is a prominent technique for finding the ground state of quantum many-body systems.
We propose an algorithm to implement imaginary time propagation on a quantum computer.
arXiv Detail & Related papers (2021-02-24T12:48:00Z) - Sampling Overhead Analysis of Quantum Error Mitigation: Uncoded vs.
Coded Systems [69.33243249411113]
We show that Pauli errors incur the lowest sampling overhead among a large class of realistic quantum channels.
We conceive a scheme amalgamating QEM with quantum channel coding, and analyse its sampling overhead reduction compared to pure QEM.
arXiv Detail & Related papers (2020-12-15T15:51:27Z) - Sampling and the complexity of nature [0.0]
I investigate the complexity-theoretic and physical foundations of quantum sampling algorithms.
I shed light on how and under which conditions quantum sampling devices can be tested or verified.
An overarching theme of the thesis is the quantum sign problem which arises due to destructive interference between paths.
arXiv Detail & Related papers (2020-12-14T19:35:27Z)
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.