The complexity of NISQ.
Journal
Nature communications
ISSN: 2041-1723
Titre abrégé: Nat Commun
Pays: England
ID NLM: 101528555
Informations de publication
Date de publication:
26 Sep 2023
26 Sep 2023
Historique:
received:
19
02
2023
accepted:
25
08
2023
medline:
27
9
2023
pubmed:
27
9
2023
entrez:
26
9
2023
Statut:
epublish
Résumé
The recent proliferation of NISQ devices has made it imperative to understand their power. In this work, we define and study the complexity class NISQ, which encapsulates problems that can be efficiently solved by a classical computer with access to noisy quantum circuits. We establish super-polynomial separations in the complexity among classical computation, NISQ, and fault-tolerant quantum computation to solve some problems based on modifications of Simon's problems. We then consider the power of NISQ for three well-studied problems. For unstructured search, we prove that NISQ cannot achieve a Grover-like quadratic speedup over classical computers. For the Bernstein-Vazirani problem, we show that NISQ only needs a number of queries logarithmic in what is required for classical computers. Finally, for a quantum state learning problem, we prove that NISQ is exponentially weaker than classical computers with access to noiseless constant-depth quantum circuits.
Identifiants
pubmed: 37752125
doi: 10.1038/s41467-023-41217-6
pii: 10.1038/s41467-023-41217-6
pmc: PMC10522708
doi:
Types de publication
Journal Article
Langues
eng
Sous-ensembles de citation
IM
Pagination
6001Subventions
Organisme : U.S. Department of Energy (DOE)
ID : DE-SC0007870
Informations de copyright
© 2023. The Author(s).
Références
Nature. 2017 Mar 8;543(7644):221-225
pubmed: 28277511
Phys Rev Lett. 2007 May 11;98(19):190504
pubmed: 17677613
Nature. 2022 Jan;601(7893):343-347
pubmed: 35046604
Phys Rev Lett. 2021 May 14;126(19):190505
pubmed: 34047595
Nature. 2022 Mar;603(7901):416-420
pubmed: 35296841
Nat Commun. 2014 Jul 23;5:4213
pubmed: 25055053
Science. 2022 Jun 10;376(6598):1182-1186
pubmed: 35679419
Nature. 2016 Aug 03;536(7614):63-6
pubmed: 27488798
Proc Natl Acad Sci U S A. 2010 May 11;107(19):8513-8
pubmed: 20404195
Phys Rev Lett. 2007 Jan 12;98(2):020501
pubmed: 17358588
Nature. 2022 Jan;601(7893):338-342
pubmed: 35046603
Nat Commun. 2022 Aug 22;13(1):4919
pubmed: 35995777
Nature. 2019 Mar;567(7747):209-212
pubmed: 30867609
Sci Adv. 2018 Feb 02;4(2):eaao3603
pubmed: 29423443
Phys Rev Lett. 2000 Aug 21;85(8):1758-61
pubmed: 10970607
Nature. 2019 Oct;574(7779):505-510
pubmed: 31645734
Science. 1996 Aug 23;273(5278):1073-8
pubmed: 8688088
Phys Rev Lett. 2009 Oct 9;103(15):150502
pubmed: 19905613
Sci Bull (Beijing). 2021 Nov 15;66(21):2181-2188
pubmed: 36654109
Nat Commun. 2021 May 11;12(1):2631
pubmed: 33976136
Nature. 2008 Jun 19;453(7198):1031-42
pubmed: 18563154
Nature. 2017 Sep 13;549(7671):242-246
pubmed: 28905916
Nature. 2022 Jan;601(7893):348-353
pubmed: 35046601
Nat Commun. 2019 Nov 29;10(1):5464
pubmed: 31784527
Phys Rev Lett. 2019 Feb 1;122(4):040504
pubmed: 30768345
Nature. 2017 Nov 29;551(7682):601-604
pubmed: 29189781
Nat Commun. 2022 Feb 16;13(1):887
pubmed: 35173160