Quantum advantage with shallow circuits
Quantum advantage with shallow circuits
复制标题
DOI：
10.1126/science.aar3106
复制
发表时间：
2018-10-19
期刊：
影响因子：
56.9
通讯作者：
Koenig, Robert
中科院分区：
文献类型：
--
作者：
Bravyi, Sergey;Gosset, David;Koenig, Robert
量子效应可以增强信息处理能力并加速某些计算问题的解决。量子优势是否可以在某些环境中得到严格证明，或者使用近期设备进行实验证明，这是一个积极辩论的主题。我们表明，在一个恒定的时间段内运行的并行量子算法严格比他们的经典同行更强大，他们是证明更好地解决某些线性代数问题与二进制二次型。我们的工作给出了计算量子优势的无条件证明，同时指出了它的起源：它是量子非定域性的结果。所提出的量子算法是不久的将来实验实现的合适候选者，因为它只需要在二维量子位网格（量子位）上具有最近邻门的恒定深度量子电路。
Quantum effects can enhance information-processing capabilities and speed up the solution of certain computational problems. Whether a quantum advantage can be rigorously proven in some setting or demonstrated experimentally using near-term devices is the subject of active debate. We show that parallel quantum algorithms running in a constant time period are strictly more powerful than their classical counterparts; they are provably better at solving certain linear algebra problems associated with binary quadratic forms. Our work gives an unconditional proof of a computational quantum advantage and simultaneously pinpoints its origin: It is a consequence of quantum nonlocality. The proposed quantum algorithm is a suitable candidate for near-future experimental realizations, as it requires only constant-depth quantum circuits with nearest-neighbor gates on a two-dimensional grid of qubits (quantum bits).