IBM T. J. Watson Research Center, Yorktown Heights, NY 10598, USA.
Technical University of Munich, 85748 Garching, Germany.
Science. 2018 Oct 19;362(6412):308-311. doi: 10.1126/science.aar3106.
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).
量子效应可以增强信息处理能力并加快某些计算问题的解决速度。在某些环境中是否可以严格证明存在量子优势，或者使用近期设备在实验中证明，这是一个活跃的争论话题。我们证明，在一个恒定时间段内运行的并行量子算法比它们的经典对应算法具有更强的能力；它们在解决与二进制二次型相关的某些线性代数问题方面被证明更优。我们的工作给出了计算量子优势的无条件证明，同时指出了其起源：这是量子非局域性的结果。所提出的量子算法是未来实验实现的合适候选者，因为它仅需要在二维量子位（qubit）网格上具有最近邻门的恒定深度量子电路。
