CoChat
Sign Up
PreprintCited by 5Quantum Computing Algorithms and ArchitectureQuantum Information and CryptographyQuantum many-body systems

The DOI matches its DataCite record.

Simulating quantum computers with probabilistic methods

Open access
Nest, M. Van den·2009·arXiv
DOI 10.48550/arxiv.0911.1624arXiv 0911.1624
Open this paper in CoChat — free accountOpen PDF

Abstract

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.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.0911.1624

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.

A few free checks a day · papers already verified open instantly · results are public

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?

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][1] R. Jozsa and N. Linden, arXiv:quant-ph/0201143 (2002). - · arXiv
  2. [3][3] N. Yoran and A. Short, quant-ph/0601178 (2006). - · arXiv
  3. [4][4] [R. Jozsa, arXiv:quant-ph/0603163 (2006).](http://arxiv.org/abs/quant-ph/0603163) - · arXiv
  4. [6][6] D. Gottesman, talk at International Conference on Group Theoretic Methods in Physics, arXiv:quant-ph/9807006 (1998). - · arXiv
  5. [9][9] S. Clark, R. Jozsa, N. Linden, arXiv:quant-ph/0701103 (2007). - · arXiv
  6. [10][10] M. Van den Nest, arXiv:0811.0898 (2008). - · arXiv
  7. [13][13] S. Bravyi, Cont. Math., Vol. 482, pp. 179-211 (2009). -
  8. [14][14] R. Jozsa and A. Miyake, Proc. R. Soc. A 464, 3089-3106 (2008). -
  9. [15][15] R. Jozsa, B. Kraus, A. Miyake, J. Watrous, arXiv:0908.1467 (2009). - · arXiv
  10. [16][16] A. Y. Kitaev, quant-ph/9511026 (1995). - · arXiv
  11. [18][18] [Y. Shi, arXiv:quant-ph/0205115 (2002).](http://arxiv.org/abs/quant-ph/0205115) - · arXiv
  12. [19][19] I. Arad and Z. Landau, arXiv:0805.0040 (2008). - · arXiv
  13. [20][20] D. Deutsch and R. Jozsa (1992), Proc. Roy. Soc. A 439: 553 (1992). -
  14. [21][21] L. G. Valiant and V. V. Vazirani, ACM Press New York, NY, USA (1985). -
  15. [26][26] D. Aharonov, Z. Landau and J. Makowsky, quant-ph/0611156 (2006). - · arXiv
  16. [27][27] I. Markov and Y. Shi, SIAM J. Comp., 38(3):963-981 (2008). -
  17. [29][29] S. P. Jordan and P. Wocjan, arXiv:0904.2211 (2009). - · arXiv
  18. [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
  19. [33][33] Y. Mansour, Theoretical Advances in Neural Computation and Learning, 391-424, Kluwer Academic Publishers (1994). -
  20. [34][34] A. Bernasconi and B. Codenotti, IEEE Trans. Computers 48 , 3, 345351 (1999). -
  21. [36][36] E. Kushilevitz and Y. Mansour, SICOMP 22(6): 1331-1348 (1993). -
  22. [38][38] R. A. Horn and C. R. Johnson, Matrix Analysis , Cambridge Univ. Press (1990). -

Cited by

Sorted by citations

See all 5

Related

Metadata

Authors
Nest, M. V. D.
Venue
arXiv
Publisher
arXiv
Published
2009
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.0911.1624
arXiv
0911.1624
OpenAlex
W4293870420
Cited by
3
References
0
Citations by year
2025: 1 · 2021: 1
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
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