论文标题
NISQ的复杂性
The Complexity of NISQ
论文作者
论文摘要
NISQ设备的最新扩散使得必须了解其计算能力。在这项工作中，我们定义和研究复杂性类别$ \ textsf {nisq} $，该$旨在封装可以通过访问NISQ设备的经典计算机有效解决的问题。为了对现有设备进行建模，我们假设设备可以（1）噪声初始化所有量子位，（2）应用许多嘈杂的量子门，并且（3）对所有量子器进行嘈杂的测量。我们首先提供证据表明$ \ textsf {bpp} \ subsetNeq \ textsf {nisq} \ subsetneq \ subsetneq \ textsf {bqp} $，通过基于西蒙（Simon）问题的修改，通过三个类中的超级多样性甲骨文分离来演示三个类中的超级甲骨文分离。然后，我们考虑三个经过深入研究的问题的$ \ textsf {nisq} $的功率。对于非结构化搜索，我们证明$ \ textsf {nisq} $无法在$ \ textsf {bpp} $上实现类似Grover的二次加速。对于Bernstein-Vazirani问题，我们表明$ \ textsf {nisq} $在$ \ textsf {bpp} $所需的内容中仅需要许多查询对数。最后，对于量子状态学习问题，我们证明$ \ textsf {nisq} $比经典计算呈指数弱，并且可以访问无噪声的无恒定深度量子电路。
The recent proliferation of NISQ devices has made it imperative to understand their computational power. In this work, we define and study the complexity class $\textsf{NISQ} $, which is intended to encapsulate problems that can be efficiently solved by a classical computer with access to a NISQ device. To model existing devices, we assume the device can (1) noisily initialize all qubits, (2) apply many noisy quantum gates, and (3) perform a noisy measurement on all qubits. We first give evidence that $\textsf{BPP}\subsetneq \textsf{NISQ}\subsetneq \textsf{BQP}$, by demonstrating super-polynomial oracle separations among the three classes, based on modifications of Simon's problem. We then consider the power of $\textsf{NISQ}$ for three well-studied problems. For unstructured search, we prove that $\textsf{NISQ}$ cannot achieve a Grover-like quadratic speedup over $\textsf{BPP}$. For the Bernstein-Vazirani problem, we show that $\textsf{NISQ}$ only needs a number of queries logarithmic in what is required for $\textsf{BPP}$. Finally, for a quantum state learning problem, we prove that $\textsf{NISQ}$ is exponentially weaker than classical computation with access to noiseless constant-depth quantum circuits.
