量子计算的主要期望是有效地解决某些对经典计算机来说极其昂贵的问题。经过验证的量子优势的大多数问题涉及重复使用一个黑盒，其结构编码解决方案。算法性能的一个度量是查询复杂性，例如在给定概率下找到解决方案所需的黑盒调用的数量。量子算法的多比特的验证，如Deutsch–Jozsa 及 Grover算法，已在不同的物理系统，如核磁共振、离子阱、光学系统及超导电路中实现。然而，在小范围内，这些问题可以通过一些黑盒查询得到经典解决，从而限制了所获得的优势。在这里，我们解决了一个基于黑盒的问题，在一个五比特的超导处理器上基于噪声环境下的学习校验。使用相同的黑盒执行经典和量子算法，我们观察到查询计数中的一个大的差距，有利于量子处理。我们发现，这种差距是错误率和问题大小的函数，呈数量级增长。这一结果表明，虽然通用量子计算需要复杂的容错架构，但现有的存在噪声的系统已经显现出显著的量子优势。

（2017年9月25日）

量子机器学习入门：

http://blog.sciencenet.cn/blog-3364677-1096172.html

量子最快入门教程：

http://blog.sciencenet.cn/home.php?mod=space&uid=3364677&do=blog&id=1084559&from=space

Demonstration of quantum advantage in machine learning

来源：https://www.nature.com/articles/s41534-017-0017-3

The main promise of quantum computing is to efficiently solve certain problems that are prohibitively expensive for a classical computer. Most problems with a proven quantum advantage involve the repeated use of a black box, or oracle, whose structure encodes the solution. One measure of the algorithmic performance is the query complexity, i.e., the scaling of the number of oracle calls needed to find the solution with a given probability. Few-qubit demonstrations of quantum algorithms, such as Deutsch–Jozsa and Grover, have been implemented across diverse physical systems such as nuclear magnetic resonance, trapped ions, optical systems, and superconducting circuits. However, at the small scale, these problems can already be solved classically with a few oracle queries, limiting the obtained advantage. Here we solve an oracle-based problem, known as learning parity with noise, on a five-qubit superconducting processor. Executing classical and quantum algorithms using the same oracle, we observe a large gap in query count in favor of quantum processing. We find that this gap grows by orders of magnitude as a function of the error rates and the problem size. This result demonstrates that, while complex fault-tolerant architectures will be required for universal quantum computing, a significant quantum advantage already emerges in existing noisy systems.