The DOI matches its Crossref record; 51 of the 51 references it cites were found in a registry or an index.
Quantum speedup of Monte Carlo methods
Open accessAbstract
Monte Carlo methods use random sampling to estimate numerical quantities which are hard to compute deterministically. One important example is the use in statistical physics of rapidly mixing Markov chains to approximately compute partition functions. In this work, we describe a quantum algorithm which can accelerate Monte Carlo methods in a very general setting. The algorithm estimates the expected output value of an arbitrary randomized or quantum subroutine with bounded variance, achieving a near-quadratic speedup over the best possible classical algorithm. Combining the algorithm with the use of quantum walks gives a quantum speedup of the fastest known classical algorithms with rigorous performance bounds for computing partition functions, which use multiple-stage Markov chain Monte Carlo techniques. The quantum algorithm can also be used to estimate the total variation distance between probability distributions efficiently.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Quantum Computation and Quantum Information
Nielsen, M. A., Chuang, I., & Grover, L. K. (2002) · American Journal of Physics · doi:10.1119/1.1463744 · Cited by 21,895
Quantum computation and quantum information
Law, J. (2001) · ACM SIGSOFT Software Engineering Notes · doi:10.1145/505482.505499 · Cited by 18,842
Quantum Mechanics Helps in Searching for a Needle in a Haystack
Grover, L. K. (1997) · Physical Review Letters · doi:10.1103/physrevlett.79.325 · Cited by 4,306
Monte Carlo Methods in Financial Engineering
Glasserman, P. (2003) · Stochastic Modelling and Applied Probability · doi:10.1007/978-0-387-21617-1 · Cited by 3,782
Markov Chains and Mixing Times
Levin, D., Peres, Y., & Wilmer, E. (2008) · doi:10.1090/mbk/058 · Cited by 2,241
Quantum amplitude amplification and estimation
Brassard, G., Høyer, P., Mosca, M., & Tapp, A. (2002) · Contemporary Mathematics · doi:10.1090/conm/305/05215 · Cited by 1,680
Strengths and Weaknesses of Quantum Computing
Bennett, C. H., Bernstein, E., Brassard, G., & Vazirani, U. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796300933 · Cited by 1,470
The Monte Carlo Method for Semiconductor Device Simulation
Jacoboni, C., & Lugli, P. (1989) · Computational microelectronics · doi:10.1007/978-3-7091-6963-6 · Cited by 1,300
Random generation of combinatorial structures from a uniform distribution
Jerrum, M. R., Valiant, L. G., & Vazirani, V. V. (1986) · Theoretical Computer Science · doi:10.1016/0304-3975(86)90174-x · Cited by 985
Quantum walks: a comprehensive review
Venegas-Andraca, S. E. (2012) · Quantum Information Processing · doi:10.1007/s11128-012-0432-5 · Cited by 934
Jerrum, M., & Sinclair, A. (1989) · SIAM Journal on Computing · doi:10.1137/0218077 · Cited by 768
Aharonov, D., Ambainis, A., Kempe, J., & Vazirani, U. (2001) · Proceedings of the thirty-third annual ACM symposium on Theory of computing · doi:10.1145/380752.380758 · Cited by 654
(2004) · doi:10.1109/focs.2004.53 · Cited by 599
Polynomial-Time Approximation Algorithms for the Ising Model
Jerrum, M., & Sinclair, A. (1993) · SIAM Journal on Computing · doi:10.1137/0222066 · Cited by 548
Quantum walks: a comprehensive reviewPreprint
Venegas-Andraca, S. E. (2012) · Cited by 532
Quantum Amplitude Amplification and Estimation
Gilles Brassard, A., Høyer, P., Mosca, M., & Tapp, A. (2000) · doi:10.48550/arxiv.quant-ph/0005055 · Cited by 514
Quantum circuits with mixed states
Aharonov, D., Kitaev, A., & Nisan, N. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276708 · Cited by 428
Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters
Berry, D. W., Childs, A. M., & Kothari, R. (2015) · 2015 IEEE 56th Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2015.54 · Cited by 372
Krauth, W. (2006) · doi:10.1093/oso/9780198515357.001.0001 · Cited by 314
Monte Carlo Estimation of the Free Energy by Multistage Sampling
Valleau, J. P., & Card, D. N. (1972) · The Journal of Chemical Physics · doi:10.1063/1.1678245 · Cited by 311
Temme, K., Osborne, T. J., Vollbrecht, K. G., Poulin, D., & Verstraete, F. (2011) · Nature · doi:10.1038/nature09770 · Cited by 305
A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
Jerrum, M. (1995) · Random Structures & Algorithms · doi:10.1002/rsa.3240070205 · Cited by 288
Statistical Mechanics: Algorithms and Computations
Krauth, W. (2006) · Cited by 278
A framework for fast quantum mechanical algorithms
Grover, L. K. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276712 · Cited by 240
Poulin, D., & Wocjan, P. (2009) · Physical Review Letters · doi:10.1103/physrevlett.103.220502 · Cited by 207
Optimal quantum measurements of expectation values of observables
Knill, E., Ortiz, G., & Somma, R. D. (2007) · Physical Review A · doi:10.1103/physreva.75.012328 · Cited by 194
The quantum query complexity of approximating the median and related statistics
Nayak, A., & Wu, F. (1999) · Proceedings of the thirty-first annual ACM symposium on Theory of Computing · doi:10.1145/301250.301349 · Cited by 177
Quantum Simulations of Classical Annealing Processes
Somma, R. D., Boixo, S., Barnum, H., & Knill, E. (2008) · Physical Review Letters · doi:10.1103/physrevlett.101.130504 · Cited by 173
A quantum–quantum Metropolis algorithm
Yung, M., & Aspuru‐Guzik, A. (2012) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1111758109 · Cited by 170
Aharonov, D. (1999) · WORLD SCIENTIFIC eBooks · doi:10.1142/9789812815569_0007 · Cited by 164
Testing Symmetric Properties of Distributions
Valiant, P. (2008) · SIAM Journal on Computing · doi:10.1137/080734066 · Cited by 157
Quantum Summation with an Application to Integration
Heinrich, S. (2002) · Journal of Complexity · doi:10.1006/jcom.2001.0629 · Cited by 153
Simulating Ising spin glasses on a quantum computer
Lidar, D. A., & Biham, O. (1997) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.56.3661 · Cited by 139
Wocjan, P., & Abeyesinghe, A. (2008) · Physical Review A · doi:10.1103/physreva.78.042336 · Cited by 128
Quantum speedup of classical mixing processes
Richter, P. C. (2007) · Physical Review A · doi:10.1103/physreva.76.042306 · Cited by 87
Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems
Bezáková, I., Štefankovič, D., Vazirani, V. V., & Vigoda, E. (2008) · SIAM Journal on Computing · doi:10.1137/050644033 · Cited by 86
Quantum Computation and the Evaluation of Tensor Networks
Arad, I., & Landau, Z. A. (2010) · SIAM Journal on Computing · doi:10.1137/080739379 · Cited by 84
Adiabatic Quantum State Generation
Aharonov, D., & Ta‐Shma, A. (2007) · SIAM Journal on Computing · doi:10.1137/060648829 · Cited by 76
Quantum algorithm for approximating partition functions
Wocjan, P., Chiang, C.-F., Nagaj, D., & Abeyesinghe, A. (2009) · Physical Review A · doi:10.1103/physreva.80.022340 · Cited by 56
Brassard, G., Dupuis, F., Gambs, S., & Tapp, A. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1106.4267 · Cited by 54
Quantum Algorithms for Testing Properties of Distributions
Bravyi, S. B., Harrow, A. W., & Hassidim, A. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2134250 · Cited by 44
Quantum algorithms for spin models and simulable gate sets for quantum computation
den Nest, M. V., Dür, W., Raussendorf, R., & Briegel, H. J. (2009) · Physical Review A · doi:10.1103/physreva.80.052334 · Cited by 41
Quantum algorithms for classical lattice models
De las Cuevas, G., Dür, W., Van den Nest, M., & Martin-Delgado, M. A. (2011) · New Journal of Physics · doi:10.1088/1367-2630/13/9/093021 · Cited by 40
On the Exact Evaluation of Certain Instances of the Potts Partition Function by Quantum Computers
Geraci, J., & Lidar, D. A. (2008) · Communications in Mathematical Physics · doi:10.1007/s00220-008-0438-0 · Cited by 33
Efficient circuits for quantum walks
Chiang, C.-F., Nagaj, D., & Wocjan, P. (2010) · Quantum Information and Computation · doi:10.26421/qic10.5-6-4 · Cited by 31
Quantum Sub-Gaussian Mean EstimatorPreprint
Hamoudi, Y. (2021) · arXiv (Cornell University) · doi:10.4230/lipics.esa.2021.50 · Cited by 27
Quantum algorithm for an additive approximation of Ising partition functions
Matsuo, A., Fujii, K., & Imoto, N. (2014) · Physical Review A · doi:10.1103/physreva.90.022304 · Cited by 18
Trading Inverses for an Irrep in the Solovay-Kitaev TheoremPreprint
Bouland, A., & Ozols, M. (2017) · arXiv (Cornell University) · doi:10.4230/lipics.tqc.2018.6 · Cited by 9
Sequential quantum mixing for slowly evolving sequences of Markov chains.Preprint
Dunjko, V., & Briegel, H. J. (2015) · arXiv (Cornell University) · Cited by 5
Quantum Algorithm for Exact Monte Carlo Sampling
Destainville, N., Georgeot, B., & Giraud, O. (2010) · Physical Review Letters · doi:10.1103/physrevlett.104.250502 · Cited by 5
Tucci, R. R. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0912.4402 · Cited by 3
Cited by
Quantum computing for finance: Overview and prospects
Orús, R., Mugel, S., & Lizaso, E. (2019) · Reviews in Physics · doi:10.1016/j.revip.2019.100028 · Cited by 668
Continuous-variable quantum neural networks
Killoran, N., Bromley, T. R., Arrazola, J. M., Schuld, M., Quesada, N., & Lloyd, S. (2019) · Physical Review Research · doi:10.1103/physrevresearch.1.033063 · Cited by 418
Woerner, S., & Egger, D. J. (2019) · npj Quantum Information · doi:10.1038/s41534-019-0130-6 · Cited by 286
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 computational finance: Monte Carlo pricing of financial derivatives
Rebentrost, P., Gupt, B., & Bromley, T. R. (2018) · Physical Review A · doi:10.1103/physreva.98.022321 · Cited by 265
Metadata
- Authors
- Montanaro, A.
- Venue
- Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences
- Publisher
- The Royal Society
- Published
- 2015-09
- Volume
- 471
- Issue
- 2181
- Pages
- 20150301
- ISSN
- 1364-5021 (ISSN-L)
- 1471-2946
- OpenAlex
- W2164248509
- Cited by
- 334
- References
- 51
- FWCI
- 4.38
- Type
- journal article
- Language
- en
- Open access
- hybrid
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.