CoChat
Sign Up
PreprintCited by 8Quantum Computing Algorithms and ArchitectureQuantum Information and CryptographyComplexity and Algorithms in Graphs

The DOI matches its DataCite record.

Quantum supremacy and high-dimensional integration

Open access
Arrazola, Juan Miguel, Rebentrost, Patrick, Weedbrook, Christian·2017·arXiv
DOI 10.48550/arxiv.1712.07288arXiv 1712.07288
Open this paper in CoChat — free accountOpen PDF

Abstract

We establish a connection between continuous-variable quantum computing and high-dimensional integration by showing that the outcome probabilities of continuous-variable instantaneous quantum polynomial (CV-IQP) circuits are given by integrals of oscillating functions in large dimensions. We prove two results related to the classical hardness of evaluating these integrals: (i) we show that there exist circuits such that these integrals are approximations of a weighted sum of #P-hard problems and (ii) we prove that calculating these integrals is as hard as calculating integrals of arbitrary bounded functions. We then leverage these results to show that, given a plausible conjecture about the hardness of computing the integrals, approximate sampling from CV-IQP circuits cannot be done in polynomial time on a classical computer unless the polynomial hierarchy collapses to the third level. Our results hold even in the presence of finite squeezing and limited measurement precision, without an explicit need for fault-tolerance.

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.1712.07288

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?

  • Both GBS and CV-IQP circuits have been shown to be intractable to simulate classically.

    “Both GBS [106,110] and CV-IQP circuits [109,111] have been shown to be intractable to simulate classically.”

    From Continuous-variable quantum neural networks (2019) · cites this paper as [111]

    The paper’s discussion (p. 4) supports classical intractability for approximate sampling from CV-IQP circuits, but only if approximating the associated integrals is #P-hard on average and unless the polynomial hierarchy collapses. The cited paper is attached to the CV-IQP part of the sentence, not the separately cited GBS part. Saying CV-IQP circuits have been shown intractable without those conditions overstates its result. (LLM, conf=0.88)

    Experimental — accuracy not yet measured

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

No references could be resolved yet.

Research works printed but not linked: 24

  1. [1]P. W. Shor, in Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on (Ieee, 1994), pp. 124-134.
  2. [3]D. Boneh and R. J. Lipton, in Annual International Cryptology Conference (Springer, 1995), pp. 424-437.
  3. [12]D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma, in Forum of Mathematics, Sigma (Cambridge University Press, 2017), vol. 5.
  4. [14]S. Aaronson and A. Arkhipov, in Proceedings of the fortythird annual ACM symposium on Theory of computing (ACM, 2011), pp. 333-342.
  5. [15]C. S. Hamilton, R. Kruse, L. Sansoni, S. Barkhofen, C. Silberhorn, and I. Jex, Physical Review Letters 119 , 170501 (2017).
  6. [16]S. Boixo, S. V. Isakov, V. N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, J. M. Martinis, and H. Neven, arXiv:1608.00263 (2016). · arXiv
  7. [17]S. Aaronson and L. Chen, arXiv:1612.05903 (2016). · arXiv
  8. [18]E. Farhi, J. Goldstone, and S. Gutmann, arXiv:1411.4028 (2014). · arXiv
  9. [19]E. Farhi and A. W. Harrow, arXiv:1602.07674 (2016). · arXiv
  10. [20]X. Gao, S.-T. Wang, and L.-M. Duan, Physical Review Letters 118 , 040502 (2017).
  11. [21]J. Bermejo-Vega, D. Hangleiter, M. Schwarz, R. Raussendorf, and J. Eisert, arXiv:1703.00466 (2017). · arXiv
  12. [22]J. Miller, S. Sanders, and A. Miyake, arXiv:1703.11002 · arXiv
  13. [23]M. J. Bremner, R. Jozsa, and D. J. Shepherd, in Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences (The Royal Society, 2010), p. 0301.
  14. [24]M. J. Bremner, A. Montanaro, and D. J. Shepherd, Physical Review Letters 117 , 080501 (2016).
  15. [26]S. Lloyd and S. L. Braunstein, Physical Review Letters 82 , 1784 (1999).
  16. [28]M. Gu, C. Weedbrook, N. C. Menicucci, T. C. Ralph, and P. van Loock, Physical Review A 79 , 062318 (2009).
  17. [29]N. C. Menicucci, P. van Loock, M. Gu, C. Weedbrook, T. C. Ralph, and M. A. Nielsen, Physical Review Letters 97 , 110501 (2006).
  18. [30]T. Douce, D. Markham, E. Kashefi, E. Diamanti, T. Coudreau, P. Milman, P. van Loock, and G. Ferrini, Physical Review Letters 118 , 070503 (2017).
  19. [32]I. H. Sloan and H. Wozniakowski, Journal of Complexity 14 , 1 (1998).
  20. [33]E. Novak and H. Wozniakowski, Journal of Complexity 25 , 398 (2009).
  21. [37]P. P. Rohde, D. W. Berry, K. R. Motes, and J. P. Dowling, arXiv:1607.04960 (2016). · arXiv
  22. [38]S. D. Bartlett, B. C. Sanders, S. L. Braunstein, and K. Nemoto, Physical Review Letters 88 , 097904 (2002).
  23. [39]S. Toda, SIAM Journal on Computing 20 , 865 (1991).
  24. [40]L. Stockmeyer, SIAM Journal on Computing 14 , 849 (1985).

Cited by

Sorted by citations

Metadata

Authors
Arrazola, J. M., Rebentrost, P., & Weedbrook, C.
Affiliations
Xanadu Quantum Technologies (Canada) (CA)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2017
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.1712.07288
arXiv
1712.07288
OpenAlex
W2780619840
Cited by
8
References
0
Citations by year
2022: 1 · 2021: 1 · 2020: 1 · 2019: 2 · 2018: 3
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 › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
Keywords
quantum advantage, continuous-variable quantum computing, high-dimensional integration, #P-hardness, polynomial hierarchy, approximate sampling, squeezing, measurement precision, oscillatory functions

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