The DOI matches its DataCite record.
Simulating quantum computers with probabilistic methods
Open accessAbstract
We investigate the boundary between classical and quantum computational power. This work consists of two parts. First we develop new classical simulation algorithms that are centered on sampling methods. Using these techniques we generate new classes of classically simulatable quantum circuits where standard techniques relying on the exact computation of measurement probabilities fail to provide efficient simulations. For example, we show how various concatenations of matchgate, Toffoli, Clifford, bounded-depth, Fourier transform and other circuits are classically simulatable. We also prove that sparse quantum circuits as well as circuits composed of CNOT and exp[iaX] gates can be simulated classically. In a second part, we apply our results to the simulation of quantum algorithms. It is shown that a recent quantum algorithm, concerned with the estimation of Potts model partition functions, can be simulated efficiently classically. Finally, we show that the exponential speed-ups of Simon's and Shor's algorithms crucially depend on the very last stage in these algorithms, dealing with the classical postprocessing of the measurement outcomes. Specifically, we prove that both algorithms would be classically simulatable if the function classically computed in this step had a sufficiently peaked Fourier spectrum.
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.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Interestingly, while sampling from these circuits is challenging, expectation values can be efficiently computed classically up to poly ( n -1 ) error [61].”
From Towards secondary structure prediction of longer mRNA sequences using a quantum-centric optimization scheme (2025) · cites this paper as [61]
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
Still being checked.
Research works printed but not linked: 22
- [1][1] R. Jozsa and N. Linden, arXiv:quant-ph/0201143 (2002). - · arXiv
- [3][3] N. Yoran and A. Short, quant-ph/0601178 (2006). - · arXiv
- [4][4] [R. Jozsa, arXiv:quant-ph/0603163 (2006).](http://arxiv.org/abs/quant-ph/0603163) - · arXiv
- [6][6] D. Gottesman, talk at International Conference on Group Theoretic Methods in Physics, arXiv:quant-ph/9807006 (1998). - · arXiv
- [9][9] S. Clark, R. Jozsa, N. Linden, arXiv:quant-ph/0701103 (2007). - · arXiv
- [10][10] M. Van den Nest, arXiv:0811.0898 (2008). - · arXiv
- [13][13] S. Bravyi, Cont. Math., Vol. 482, pp. 179-211 (2009). -
- [14][14] R. Jozsa and A. Miyake, Proc. R. Soc. A 464, 3089-3106 (2008). -
- [15][15] R. Jozsa, B. Kraus, A. Miyake, J. Watrous, arXiv:0908.1467 (2009). - · arXiv
- [16][16] A. Y. Kitaev, quant-ph/9511026 (1995). - · arXiv
- [18][18] [Y. Shi, arXiv:quant-ph/0205115 (2002).](http://arxiv.org/abs/quant-ph/0205115) - · arXiv
- [19][19] I. Arad and Z. Landau, arXiv:0805.0040 (2008). - · arXiv
- [20][20] D. Deutsch and R. Jozsa (1992), Proc. Roy. Soc. A 439: 553 (1992). -
- [21][21] L. G. Valiant and V. V. Vazirani, ACM Press New York, NY, USA (1985). -
- [26][26] D. Aharonov, Z. Landau and J. Makowsky, quant-ph/0611156 (2006). - · arXiv
- [27][27] I. Markov and Y. Shi, SIAM J. Comp., 38(3):963-981 (2008). -
- [29][29] S. P. Jordan and P. Wocjan, arXiv:0904.2211 (2009). - · arXiv
- [30][30] M. Hein et al., In Proceedings of the International School of Physics 'Enrico Fermi' on 'Quantum Computers, Algorithms and Chaos' (2005); arXiv:quant-ph/0602096. - · arXiv
- [33][33] Y. Mansour, Theoretical Advances in Neural Computation and Learning, 391-424, Kluwer Academic Publishers (1994). -
- [34][34] A. Bernasconi and B. Codenotti, IEEE Trans. Computers 48 , 3, 345351 (1999). -
- [36][36] E. Kushilevitz and Y. Mansour, SICOMP 22(6): 1331-1348 (1993). -
- [38][38] R. A. Horn and C. R. Johnson, Matrix Analysis , Cambridge Univ. Press (1990). -
Cited by
Sorted by citations
Practical Characterization of Quantum Devices without Tomography
Silva, M. P. D., Landon-Cardinal, O., & Poulin, D. (2011) · Physical Review Letters · doi:10.1103/physrevlett.107.210404 · Cited by 340
Using Quantum Computers for Quantum Simulation
Brown, K. L., Munro, W. J., & Kendon, V. M. (2010) · Entropy · doi:10.3390/e12112268 · Cited by 129
“Classical simulations of quantum systems are usually “strong simulations” [6,7] which provide the whole probability distribution, and we often need at least a significant part of this, e.”
BackgroundFeynman-path-type simulation using stabilizer projector decomposition of unitaries
Huang, Y., & Love, P. J. (2021) · Physical Review A · doi:10.1103/physreva.103.022428 · Cited by 10
Kumar, V., Alevras, D., Metkar, M., Welling, E., Cade, C., Niesen, I., Friedhoff, T., Park, J.-E., Shivpuje, S., LaDue, M., et al. (2025) · arXiv · doi:10.48550/arxiv.2505.05782 · Cited by 3
Variational quantum and neural quantum states algorithms for the linear complementarity problem
De, S., Knitter, O., Kodati, R., Jayakumar, P., STOKES, J. M., & Veerapaneni, S. (2025) · Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rsta.2024.0423
Metadata
- Authors
- Nest, M. V. D.
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2009
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 0911.1624
- OpenAlex
- W4293870420
- Cited by
- 3
- References
- 0
- Citations by year
- 2025: 1 · 2021: 1
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Keywords
- classical simulation of quantum circuits, quantum sampling, matchgates, Toffoli gate, Clifford circuits, CNOT gate, quantum algorithms, Simon's algorithm, Shor's algorithm, Fourier spectrum
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Simulating quantum computers with probabilistic methods. https://app.cochat.ai/papers/10.48550/arxiv.0911.1624
- The paper
- Nest, M. V. D. (2009). Simulating quantum computers with probabilistic methods. arXiv. https://doi.org/10.48550/arxiv.0911.1624
