文章基本信息

标题：Quantum Advantage for the LOCAL Model in Distributed Computing
本地全文：下载
作者：François Le Gall ; Harumichi Nishimura ; Ansis Rosmanis 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：126
页码：1-14
DOI：10.4230/LIPIcs.STACS.2019.49
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：There are two central models considered in (fault-free synchronous) distributed computing: the CONGEST model, in which communication channels have limited bandwidth, and the LOCAL model, in which communication channels have unlimited bandwidth. Very recently, Le Gall and Magniez (PODC 2018) showed the superiority of quantum distributed computing over classical distributed computing in the CONGEST model. In this work we show the superiority of quantum distributed computing in the LOCAL model: we exhibit two computational tasks that can be solved in a constant number of rounds in the quantum setting but require Omega(n) rounds in the classical (randomized) setting, where n denotes the size of the network.
关键词：Quantum computing; distributed computing; LOCAL model