The CONGEST and CONGEST-CLIQUE models have been carefully studied to represent situations where the communication bandwidth between processors in a network is severely limited. Messages of only $O(log(n))$ bits of information each may be sent between processors in each round. The quantum versions of these models allow the processors instead to communicate and compute with quantum bits under the same bandwidth limitations. This leads to the following natural research question: What problems can be solved more efficiently in these quantum models than in the classical ones? Building on existing work, we contribute to this question in two ways. Firstly, we present two algorithms in the Quantum CONGEST-CLIQUE model of distributed computation that succeed with high probability; one for producing an approximately optimal Steiner Tree, and one for producing an exact directed minimum spanning tree, each of which uses $\tilde{O}(n^{1/4})$ rounds of communication and $\tilde{O}(n^{9/4})$ messages, where $n$ is the number of nodes in the network. The algorithms thus achieve a lower asymptotic round and message complexity than any known algorithms in the classical CONGEST-CLIQUE model. At a high level, we achieve these results by combining classical algorithmic frameworks with quantum subroutines. An existing framework for using distributed version of Grover's search algorithm to accelerate triangle finding lies at the core of the asymptotic speedup. Secondly, we carefully characterize the constants and logarithmic factors involved in our algorithms as well as related algorithms, otherwise commonly obscured by $\tilde{O}$ notation. The analysis shows that some improvements are needed to render both our and existing related quantum and classical algorithms practical, as their asymptotic speedups only help for very large values of $n$.


翻译:CONGEST和CONGEST-CLIQUE模型已经被认真地研究,用于表示网络处理器之间的通信带宽严重受限的情况。每次只能在处理器之间发送 $O(log(n))$ 位信息。量子版本的这些模型允许处理器在相同的带宽限制下使用量子位进行通信和计算。这导致了以下自然的研究问题:这些量子模型比经典模型更高效地解决了哪些问题?在现有工作的基础上,我们通过两种方式解决了这个问题。首先,我们在量子CONGEST-CLIQUE模型中提出了两个算法,分别用于生成近似最优斯坦纳树和精确的有向最小生成树,每个算法使用 $\tilde{O}(n^{1/4})$ 轮通信和 $\tilde{O}(n^{9/4})$ 条消息,其中 $n$ 是网络中节点的数量。因此,这些算法实现了比经典CONGEST-CLIQUE模型中已知算法更低的渐进轮和消息复杂度。在高层次上,我们通过将经典算法框架与量子子程序相结合来实现这些结果,而使用分布式版本的Grover搜索算法的现有框架来加速三角查找则是渐进速度提升的核心。其次,我们仔细地表征了我们的算法以及与其相关的算法中涉及的常数和对数因子,这些通常被 $\tilde{O}$ 符号掩盖。分析表明,为了使我们的算法和现有相关的量子和经典算法实用化,需要进行一些改进,因为它们的渐进速度提升只对非常大的 $n$ 值有帮助。

0
下载
关闭预览

相关内容

【硬核书】稀疏多项式优化:理论与实践,220页pdf
专知会员服务
67+阅读 · 2022年9月30日
专知会员服务
94+阅读 · 2021年8月28日
专知会员服务
18+阅读 · 2021年7月11日
专知会员服务
50+阅读 · 2020年12月14日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
基于PyTorch/TorchText的自然语言处理库
专知
28+阅读 · 2019年4月22日
TorchSeg:基于pytorch的语义分割算法开源了
极市平台
20+阅读 · 2019年1月28日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
利用动态深度学习预测金融时间序列基于Python
量化投资与机器学习
18+阅读 · 2018年10月30日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Arxiv
0+阅读 · 2023年6月7日
Arxiv
0+阅读 · 2023年6月6日
VIP会员
相关VIP内容
【硬核书】稀疏多项式优化:理论与实践,220页pdf
专知会员服务
67+阅读 · 2022年9月30日
专知会员服务
94+阅读 · 2021年8月28日
专知会员服务
18+阅读 · 2021年7月11日
专知会员服务
50+阅读 · 2020年12月14日
相关资讯
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
基于PyTorch/TorchText的自然语言处理库
专知
28+阅读 · 2019年4月22日
TorchSeg:基于pytorch的语义分割算法开源了
极市平台
20+阅读 · 2019年1月28日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
利用动态深度学习预测金融时间序列基于Python
量化投资与机器学习
18+阅读 · 2018年10月30日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Top
微信扫码咨询专知VIP会员