Even after decades of quantum computing development, examples of generally useful quantum algorithms with exponential speedups over classical counterparts are scarce. Recent progress in quantum algorithms for linear-algebra positioned quantum machine learning (QML) as a potential source of such useful exponential improvements. Yet, in an unexpected development, a recent series of "dequantization" results has equally rapidly removed the promise of exponential speedups for several QML algorithms. This raises the critical question whether exponential speedups of other linear-algebraic QML algorithms persist. In this paper, we study the quantum-algorithmic methods behind the algorithm for topological data analysis of Lloyd, Garnerone and Zanardi through this lens. We provide evidence that the problem solved by this algorithm is classically intractable by showing that its natural generalization is as hard as simulating the one clean qubit model -- which is widely believed to require superpolynomial time on a classical computer -- and is thus very likely immune to dequantizations. Based on this result, we provide a number of new quantum algorithms for problems such as rank estimation and complex network analysis, along with complexity-theoretic evidence for their classical intractability. Furthermore, we analyze the suitability of the proposed quantum algorithms for near-term implementations. Our results provide a number of useful applications for full-blown, and restricted quantum computers with a guaranteed exponential speedup over classical methods, recovering some of the potential for linear-algebraic QML to become one of quantum computing's killer applications.
翻译:即使在数十年的量子计算发展之后,一些普通有用的量子算法的例子也很少见。最近,线性值与古典对应方的指数加速速度相比,也很少见。最近,线性值与数子机器学习(QML)的量子算法作为这种有用指数改进的潜在来源,在线性值与数子计算发展之后,作为这种有用的指数改进的潜在来源。然而,在意想不到的发展中,最近一系列的“消化”结果同样迅速地消除了数子加速数对数子计算法的希望。这引起了一个关键问题:其他线性与数子的QMLAM算法的指数加速速度是否还在继续。在本文中,我们通过这个镜头研究劳埃德、加内罗内纳和扎纳纳迪的表面学数据分析算法背后的量子- 。我们提供一些新的量子值分析方法,例如劳埃德、加内罗内罗内尔和Zanardi(Qrandi)的表面数据分析,我们用这个算算法解决的自然概括化问题,就像一个纯级的精度分析。我们所拟的精确的货币计算的直径的直径值分析。