Chen Sitan, Cotler Jordan, Huang Hsin-Yuan, Li Jerry
Department of Electrical Engineering and Computer Science, University of California, Berkeley, Berkeley, CA, USA.
John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, USA.
Nat Commun. 2023 Sep 26;14(1):6001. doi: 10.1038/s41467-023-41217-6.
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.
近期含噪声中等规模量子（NISQ）设备的激增使得了解它们的能力变得势在必行。在这项工作中，我们定义并研究了复杂度类NISQ，它涵盖了那些可由能访问有噪声量子电路的经典计算机有效解决的问题。我们基于对西蒙问题的修改解决一些问题，在经典计算、NISQ和容错量子计算之间的复杂度上建立了超多项式分离。然后我们考虑NISQ对三个经过充分研究的问题的能力。对于无结构搜索问题，我们证明NISQ无法在经典计算机上实现类似格罗弗算法的二次加速。对于伯恩斯坦 - 瓦齐拉尼问题，我们表明NISQ只需要经典计算机所需查询次数对数级别的查询次数。最后，对于一个量子态学习问题，我们证明NISQ比能访问无噪声恒定深度量子电路的经典计算机指数级地弱。
