Speedup via quantum sampling
Open accessThe DOI matches its Crossref record; 2 of the 2 references it cites were found in a registry or an index.
Abstract
The Markov-chain Monte Carlo method is at the heart of efficient approximation schemes for a wide range of problems in combinatorial enumeration and statistical physics. It is therefore very natural and important to determine whether quantum computers can speed up classical mixing processes based on Markov chains. To this end, we present a quantum algorithm, making it possible to prepare a quantum sample---i.e., a coherent version of the stationary distribution of a reversible Markov chain. Our algorithm has a significantly better running time than that of a previous algorithm based on adiabatic-state generation. We also show that our methods provide a greater speedup over a recently proposed method for obtaining the ground states of (classical) Hamiltonians.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The complexity of computing the permanent
Valiant, L. G. (1979) · Theoretical Computer Science · doi:10.1016/0304-3975(79)90044-6 · Cited by 2,705
(2004) · doi:10.1109/focs.2004.53 · Cited by 599
Cited by
Simulation of electronic structure Hamiltonians using quantum computers
Whitfield, J. D., Biamonte, J., & Aspuru-Guzik, A. (2011) · Molecular Physics · doi:10.1080/00268976.2011.552441 · Cited by 472
Simulating Chemistry Using Quantum Computers
Kassal, I., Whitfield, J. D., Perdomo-Ortiz, A., Yung, M.-H., & Aspuru-Guzik, A. (2011) · Annual Review of Physical Chemistry · doi:10.1146/annurev-physchem-032210-103512 · Cited by 352
Moore, C., & Mertens, S. (2011) · doi:10.1093/acprof:oso/9780199233212.001.0001 · Cited by 347
Quantum speedup of Monte Carlo methods
Montanaro, A. (2015) · Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.2015.0301 · Cited by 334
Herman, D., Googin, C., Liu, X., Sun, Y., Galda, A., Safro, I., Pistoia, M., & Alexeev, Y. (2023) · Nature Reviews Physics · doi:10.1038/s42254-023-00603-1 · Cited by 284
Quantum Speedup for Active Learning Agents
Paparo, G. D., Dunjko, V., Makmal, A., Martin-Delgado, M. A., & Briegel, H. J. (2014) · Physical Review X · doi:10.1103/physrevx.4.031002 · Cited by 192
Shaydulin, R., Li, C., Chakrabarti, S., DeCross, M., Herman, D., Kumar, N., Larson, J., Lykov, D., Minssen, P., Sun, Y., et al. (2024) · Science Advances · doi:10.1126/sciadv.adm6761 · Cited by 120
“These include amplitude amplification (1), quantum walks (2–4) and quantum Markov Chain algorithms (5, 6), as well as the recently introduced short path algorithm (7, 8).”
BackgroundQuantum enhancements for deep reinforcement learning in large spaces
Jerbi, S., Trenkwalder, L. M., Nautrup, H. P., Briegel, H. J., & Dunjko, V. (2019) · arXiv · doi:10.48550/arxiv.1910.12760 · Cited by 69
“More precisely, it was shown [78] that given a schedule β 0 = 0 , β 1 , . . . , β l = β and classical Markov chains P β 0 , P β 1 , . . . , P β l with stationary distributions π β 0 , π β 1 , . . . , π β l that fulfill the slow-varying condition , where δ lower bounds the spectral gaps of these…”
Bias-field digitized counterdiabatic quantum algorithm for higher-order binary optimization
Romero, S. V., Visuri, A.-M., Cadavid, A. G., Simen, A., Solano, E., & Hegade, N. N. (2025) · Communications Physics · doi:10.1038/s42005-025-02270-3 · Cited by 18
Threshold for Fault-tolerant Quantum Advantage with the Quantum Approximate Optimization Algorithm
Omanakuttan, S., He, Z., Zhang, Z., Hao, T., Babakhani, A., Boulebnane, S., Chakrabarti, S., Herman, D., Sullivan, J., Perlin, M. A., et al. (2025) · arXiv · doi:10.48550/arxiv.2504.01897 · Cited by 3
“However, most such speedups are obtained using a variant of amplitude amplification [5] and are therefore only quadratic [6–10].”
Metadata
- Authors
- Wocjan, P., & Abeyesinghe, A.
- Venue
- Physical Review A
- Publisher
- American Physical Society (APS)
- Published
- 2008-10-31
- Volume
- 78
- Issue
- 4
- ISSN
- 0556-2791 (ISSN-L)
- 1050-2947
- 1094-1622
- OpenAlex
- W1989383224
- Cited by
- 120
- References
- 2
- FWCI
- 22.26
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.