Publisher Correction: The complexity of NISQ

Creators: Chen, Sitan; Cotler, Jordan; Huang, Hsin-Yuan¹; Li, Jerry

1. California Institute of Technology

Abstract

The recent proliferation of NISQ devices has made it imperative to understand their power. In this work, we define and study the complexity class , 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, , and fault-tolerant quantum computation to solve some problems based on modifications of Simon's problems. We then consider the power of for three well-studied problems. For unstructured search, we prove that cannot achieve a Grover-like quadratic speedup over classical computers. For the Bernstein-Vazirani problem, we show that only needs a number of queries logarithmic in what is required for classical computers. Finally, for a quantum state learning problem, we prove that is exponentially weaker than classical computers with access to noiseless constant-depth quantum circuits.

Copyright and License

© The Author(s) 2023. This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

Acknowledgement

We would like to thank Isaac Chuang for valuable conversations on complexity classes for learning theory, John Preskill for inspiring discussions on NISQ and its complexity class formulation, and John Wright for bringing76 and related works to our attention. S.C. is supported by NSF Award 2103300. J.C. is supported by a Junior Fellowship from the Harvard Society of Fellows, as well as in part by the Department of Energy under grant DE-SC0007870. H.H. is supported by a Google Ph.D. fellowship.

Contributions

S.C., J.C., H.H., and J.L. contributed equally to this work. All authors developed the theoretical aspects of this work and wrote the manuscript together.

Conflict of Interest

The authors declare no competing interests.

Errata

Correction to: Nature Communications https://doi.org/10.1038/s41467-023-41217-6, published online 26 September 2023

In the original pdf version of this Article, the text of Theorems 2.2 and 2.3 in the Results section was missing the ⊊ symbol. The html version displayed the theorems in the correct form.

This has now been corrected.

Files

	All versions	This version
Views	0	0
Downloads	0	0
Data volume	0 Bytes	0 Bytes