Achieving quantum supremacy with sparse and noisy commuting quantum computations
Achieving quantum supremacy with sparse and noisy commuting quantum computations
复制标题
DOI：
10.22331/q-2017-04-25-8
复制
发表时间：
2017-01-01
期刊：
影响因子：
6.4
通讯作者：
Shepherd, Dan J.
中科院分区：
文献类型：
--
作者：
Bremner, Michael J.;Montanaro, Ashley;Shepherd, Dan J.
被称为IQP（瞬时量子多项式时间）的交换量子电路类已被证明很难经典模拟，假设某些复杂性理论的架构。在这里，我们研究的电源IQP电路中存在的物理动机的限制。首先，我们表明，有一个家庭的稀疏IQP电路，可以在深度为O（根n log n）的n个量子位的正方形晶格上实现，这可能是很难模拟经典。接下来，我们表明，如果一个任意小的恒定量的噪声被施加到每个量子比特在任何IQP电路的输出概率分布是足够的反集中的结束，有一个多项式时间的经典算法，模拟采样从产生的分布，在总变化距离恒定的精度。然而，我们表明，纯经典的纠错技术可以用来设计IQP电路仍然很难模拟经典，即使在存在任意数量的这种形式的噪声。这些结果展示了旨在证明量子优越于经典计算的实验所面临的挑战，以及如何克服这些挑战。
The class of commuting quantum circuits known as IQP (instantaneous quantum polynomial-time) has been shown to be hard to simulate classically, assuming certain complexity-theoretic conjectures. Here we study the power of IQP circuits in the presence of physically motivated constraints. First, we show that there is a family of sparse IQP circuits that can be implemented on a square lattice of n qubits in depth O(root n log n), and which is likely hard to simulate classically. Next, we show that, if an arbitrarily small constant amount of noise is applied to each qubit at the end of any IQP circuit whose output probability distribution is sufficiently anticoncentrated, there is a polynomial-time classical algorithm that simulates sampling from the resulting distribution, up to constant accuracy in total variation distance. However, we show that purely classical error-correction techniques can be used to design IQP circuits which remain hard to simulate classically, even in the presence of arbitrary amounts of noise of this form. These results demonstrate the challenges faced by experiments designed to demonstrate quantum supremacy over classical computation, and how these challenges can be overcome.