Quantum computers offer the potential of achieving significant speedup for certain computational problems. Yet, many existing quantum algorithms with notable asymptotic speedups require a degree of fault tolerance that is currently unavailable. The quantum algorithm for topological data analysis (TDA) by Lloyd et al. is believed to be one such algorithm. TDA is a powerful technique for extracting complex and valuable shape-related summaries of high-dimensional data. However, the computational demands of classical TDA algorithms are exorbitant, and become impractical for high-order characteristics. In this paper, we present NISQ-TDA, the first fully implemented end-to-end quantum machine learning algorithm needing only a short circuit-depth, that is applicable to non-handcrafted high-dimensional classical data, and with provable asymptotic speedup for certain classes of problems. The algorithm neither suffers from the data-loading problem nor does it need to store the input data on the quantum computer explicitly. Our approach includes three key innovations: an efficient realization of the full boundary operator; a quantum rejection sampling and projection approach to restrict a quantum state to the simplices of the desired order in the given complex; and a stochastic rank estimation method to estimate the topological features in the form of approximate Betti numbers. We present theoretical results that establish additive error guarantees, along with computational cost and circuit-depth complexities for normalized output estimates, up to the error tolerance. The algorithm was successfully executed on quantum computing devices, as well as on noisy quantum simulators, applied to small datasets. Preliminary empirical results suggest that the algorithm is robust to noise. Finally, we provide target depths and noise level estimates to realize near-term, non-fault-tolerant quantum advantage.


翻译:量子计算机为某些计算问题提供了实现大幅加速的潜力。 然而,许多现有的量子算法,其显著的无症状加速速度需要一定程度的断层容忍度,而目前还不具备这种容忍度。 劳埃德等人的地形数据分析量子算法(TDA)被认为是一种这样的算法。 量子计算机是提取复杂和宝贵的高维数据形状摘要的强大技术。 然而,传统TDA算法的计算要求过高,对于高级特性来说不切实际。 在本文中,我们提出了SISQ-TDA,这是第一个完全执行的端到端的量子机器学习速度算法,只需要一个短路段深度的算法。 适用于非手动高层次的经典数据分析的量子算法(TDA)被认为是一种非常快速的算法。 算法既不会因数据负荷问题而受到影响,也不需要将输入的数据储存在量子计算机上。 我们的方法包括三个关键的创新: 快速实现完全边界操作者; 量子拒绝率抽样取样和投影的量机器测算法,只需要一个直径的直径直径的直径的直径的直径的直径直径算算算算算法, 也就是算算法的精确测算算法的精确测测算法的精确的精确测测算法。

0
下载
关闭预览

相关内容

Linux导论,Introduction to Linux,96页ppt
专知会员服务
78+阅读 · 2020年7月26日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
IEEE ICKG 2022: Call for Papers
机器学习与推荐算法
3+阅读 · 2022年3月30日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Latest News & Announcements of the Tutorial
中国图象图形学学会CSIG
3+阅读 · 2021年12月20日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
Arxiv
0+阅读 · 2023年2月18日
Arxiv
0+阅读 · 2023年2月17日
Arxiv
0+阅读 · 2023年2月16日
Arxiv
0+阅读 · 2023年2月15日
VIP会员
相关资讯
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
IEEE ICKG 2022: Call for Papers
机器学习与推荐算法
3+阅读 · 2022年3月30日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Latest News & Announcements of the Tutorial
中国图象图形学学会CSIG
3+阅读 · 2021年12月20日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
相关基金
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
Top
微信扫码咨询专知VIP会员