Noise and the Frontier of Quantum Supremacy
Noise and the Frontier of Quantum Supremacy
复制标题
DOI：
10.1109/focs52979.2021.00127
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Adam Bouland;Bill Fefferman;Zeph Landau;Yunchao Liu
中科院分区：
文献类型：
--
作者：
Adam Bouland;Bill Fefferman;Zeph Landau;Yunchao Liu
噪声是 NISQ 时代的决定性特征，但目前尚不清楚噪声量子设备是否能够实现量子加速。量子霸权实验是向前迈出的一大步，但这些实验背后的理论与其实际实施之间仍然存在差距。在这项工作中，我们开始研究具有实际噪声量的量子随机电路采样实验的复杂性。实际的量子霸权实验具有高水平的未校正噪声和指数衰减的保真度。人们很自然地会问，在这些高噪声设备中是否存在指数复杂度的信号。令人惊讶的是，我们表明，在没有纠错的情况下计算噪声随机量子电路的输出概率仍然很困难。更正式地说，只要设备的噪声率低于错误检测阈值，我们就表明计算每个门噪声率为恒定的随机电路的输出概率是#P-困难的。即使这些概率以指数方式接近均匀，这种硬度仍然存在。因此，与均匀性的微小偏差很难计算，从而形式化了谷歌霸主地位背后的重要直觉。有趣的是，这些硬度结果也对低噪声环境下实验的复杂性产生影响。这里的问题是，用于计算随机电路输出概率的先前硬度结果不够稳健，不足以与斯托克迈耶关于从恒定保真度电路中采样的硬度的论证联系起来。在随机电路采样和玻色子采样的情况下，我们以指数方式提高了先前结果对不精确性的鲁棒性。在后一种情况下，我们将经过验证的硬度控制在首次采样硬度所需稳健性指数的常数因子内。然后我们表明，我们的结果彼此之间存在紧张关系——高噪声结果意味着低噪声结果本质上是最优的，即使我们的技术得到了推广。
Noise is the defining feature of the NISQ era, but it remains unclear if noisy quantum devices are capable of quantum speedups. Quantum supremacy experiments have been a major step forward, but gaps remain between the theory behind these experiments and their actual implementations. In this work we initiate the study of the complexity of quantum random circuit sampling experiments with realistic amounts of noise. Actual quantum supremacy experiments have high levels of uncorrected noise and exponentially decaying fidelities. It is natural to ask if there is any signal of exponential complexity in these highly noisy devices. Surprisingly, we show that it remains hard to compute the output probabilities of noisy random quantum circuits without error correction. More formally, so long as the noise rate of the device is below the error detection threshold, we show it is #P-hard to compute the output probabilities of random circuits with a constant rate of noise per gate. This hardness persists even though these probabilities are exponentially close to uniform. Therefore the small deviations away from uniformity are hard to compute, formalizing an important intuition behind Google's supremacy claim. Interestingly these hardness results also have implications for the complexity of experiments in a low-noise setting. The issue here is that prior hardness results for computing output proba-bilities of random circuits are not robust enough to imprecision to connect with the Stockmeyer argument for hardness of sampling from circuits with constant fidelity. We exponentially improve the robustness of prior results to imprecision, both in the cases of Random Circuit Sampling and BosonSampling. In the latter case we bring the proven hardness within a constant factor in the exponent of the robustness required for hardness of sampling for the first time. We then show that our results are in tension with one another - the high-noise result implies the low-noise result is essentially optimal, even with generalizations of our techniques.