How many qubits are needed for quantum computational supremacy?
How many qubits are needed for quantum computational supremacy?
复制标题
DOI：
10.22331/q-2020-05-11-264
复制
发表时间：
2020-04-30
期刊：
影响因子：
6.4
通讯作者：
La Placa, Rolando L.
中科院分区：
文献类型：
--
作者：
Dalzell, Alexander M.;Harrow, Aram W.;La Placa, Rolando L.
量子计算至上论据描述了量子计算机执行经典计算机无法完成的任务的方式，通常需要与经典计算的局限性相关的某种计算假设。一个常见的假设是多项式层次(PH)不会崩溃，这是P不等于NP这一说法的更强版本，这导致了这样的结论：对某些量子电路家族的任何经典模拟都需要比电路大小的任何多项式更差的时间定标。然而，这一结论的渐近性质使我们无法准确计算这些量子电路必须拥有多少量子比特，才能使它们的经典模拟在现代经典超级计算机上变得难以处理。我们提炼了这些量子计算优势论证，并通过施加细粒度的非坍塌猜想来执行这样的计算。我们的前两个猜想Poly3-nseth(A)和per-int-nseth(B)采取了具体的经典计数问题，涉及F2上n个变量的三次多项式的零点个数或n×n整值矩阵的恒等式，并断言任何求解它们的非确定性算法都需要2(Cn)个时间步长，其中c是{a，b}的元素。第三个猜想Poly3-AVE-SBSETH(a‘)断言了关于生活在复杂类SBP的指数时间版本中的平均情况算法的类似陈述。我们分析了这些猜想的证据，并认为当a=1/2，b=0.999和a‘=1/2时，它们是可信的。假定Poly3-nseth(1/2)和Per-int-nseth(0.999)，并假设假设的量子电路模拟算法的运行时间将随门/约束/光学元件的数量线性扩展，我们得出结论：具有208Qubit和500门的瞬时量子多项式时间(IQP)电路，具有420个量子比特和500个约束条件的量子近似优化算法(QAOA)电路和具有98个光子和500个光学元件的玻色子采样电路(即线性光网络)足够大，足以从它们的输出分布到恒定的乘法误差来产生样本，在现有技术下是难以处理的。应用Poly3-AVE-SBSETH(1/2)，我们还排除了对相同大小的IQP和QAOA电路进行具有恒定加性误差的模拟。在没有线性增加模拟时间的假设下，我们可以对量子比特稍少但需要10(4)到10(7)门的电路进行类似的描述。
Quantum computational supremacy arguments, which describe a way for a quantum computer to perform a task that cannot also be done by a classical computer, typically require some sort of computational assumption related to the limitations of classical computation. One common assumption is that the polynomial hierarchy (PH) does not collapse, a stronger version of the statement that P not equal NP, which leads to the conclusion that any classical simulation of certain families of quantum circuits requires time scaling worse than any polynomial in the size of the circuits. However, the asymptotic nature of this conclusion prevents us from calculating exactly how many qubits these quantum circuits must have for their classical simulation to be intractable on modern classical supercomputers. We refine these quantum computational supremacy arguments and perform such a calculation by imposing fine-grained versions of the non-collapse conjecture. Our first two conjectures poly3-NSETH(a) and per-int-NSETH(b) take specific classical counting problems related to the number of zeros of a degree-3 polynomial in n variables over F2 or the permanent of an n x n integer-valued matrix, and assert that any non-deterministic algorithm that solves them requires 2(cn) time steps, where c is an element of {a, b}. A third conjecture poly3-ave-SBSETH(a') asserts a similar statement about average-case algorithms living in the exponential-time version of the complexity class SBP. We analyze evidence for these conjectures and argue that they are plausible when a = 1 /2, b = 0.999 and a' = 1/2.Imposing poly3-NSETH(1/2) and per-int-NSETH(0.999), and assuming that the runtime of a hypothetical quantum circuit simulation algorithm would scale linearly with the number of gates/constraints/optical elements, we conclude that Instantaneous Quantum Polynomial-Time (IQP) circuits with 208 qubits and 500 gates, Quantum Approximate Optimization Algorithm (QAOA) circuits with 420 qubits and 500 constraints and boson sampling circuits (i.e. linear optical networks) with 98 photons and 500 optical elements are large enough for the task of producing samples from their output distributions up to constant multiplicative error to be intractable on current technology. Imposing poly3-ave-SBSETH(1/2), we additionally rule out simulations with constant additive error for IQP and QAOA circuits of the same size. Without the assumption of linearly increasing simulation time, we can make analogous statements for circuits with slightly fewer qubits but requiring 10(4) to 10(7) gates.