Quantum advantage for differential equation analysis
Quantum advantage for differential equation analysis
复制标题
DOI：
10.1103/physreva.105.022415
复制
发表时间：
2020-10
期刊：
影响因子：
--
通讯作者：
B. Kiani;G. Palma;D. Englund;W. Kaminsky;M. Marvian;S. Lloyd
中科院分区：
文献类型：
--
作者：
B. Kiani;G. Palma;D. Englund;W. Kaminsky;M. Marvian;S. Lloyd
用于微分方程求解和机器学习的量子算法可能比所有已知的经典算法提供指数级的加速。然而，在有用的问题实例中获得这种潜在的加速也存在障碍。量子微分方程求解的本质障碍是输出有用的信息可能需要困难的后处理，而量子机器学习的本质障碍是输入训练集本身就是一项艰巨的任务。在本文中，我们证明，当这些困难结合起来时，这些困难是相互解决的。我们展示了量子微分方程求解的输出如何作为量子机器学习的输入，允许在主成分、功率谱和小波分解方面进行动态分析。为了说明这一点，我们考虑流行病学和社会网络上的连续时间马尔可夫过程。这些量子算法提供了一个指数优势比现有的经典蒙特卡罗方法。
Quantum algorithms for both differential equation solving and for machine learning potentially offer an exponential speedup over all known classical algorithms. However, there also exist obstacles to obtaining this potential speedup in useful problem instances. The essential obstacle for quantum differential equation solving is that outputting useful information may require difficult post-processing, and the essential obstacle for quantum machine learning is that inputting the training set is a difficult task just by itself. In this paper, we demonstrate, when combined, these difficulties solve one another. We show how the output of quantum differential equation solving can serve as the input for quantum machine learning, allowing dynamical analysis in terms of principal components, power spectra, and wavelet decompositions. To illustrate this, we consider continuous time Markov processes on epidemiological and social networks. These quantum algorithms provide an exponential advantage over existing classical Monte Carlo methods.