Quantum Lower Bounds for Distributed Network Computing
Michael Elkin, Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan · arXiv (Cornell University) · 2012
We study lower bounds for quantum distributed computing, where a set of nodes (representing quantum computers) interconnected by an underlying network consisting of (bandwidth-restricted) links, communicate using quantum communication. Nodes have unlimited computational power and may share an unlimited number of entangled qubits. Our main contribution is a simple uniform technique for proving lower bounds for quantum distributed algorithms. In particular, we identify a new quantum communication model called the Server model which provides a connection between distributed algorithms and communication complexity: it is strong enough to capture the hardness of several distributed computing problems, while weak enough that several hard problems in two-party communication complexity remain hard; to this end, we identify a set of communication complexity techniques that can be carried over to the Server model, namely techniques based on nonlocal games. We show that these techniques serve as a fundamental tool in proving lower bounds in quantum distributed computing. The new techniques help us to prove several non-trivial quantum distributed lower bounds (which are the first-known quantum bounds for fundamental global problems such as minimum spanning tree, shortest paths etc.), some of which are new even in the classical setting. First, it allows us to show that all previous classical lower bounds of more than twenty verification and optimization graph problems in [Das Sarma et al., STOC 11] also hold in the quantum setting. Many of these bounds are tight, implying a large class of problems that do not gain an advantage from quantum effects. Our results also imply the following new results in the classical communication models: (1) the first randomized lower bounds for Hamiltonian cycle and spanning tree verification problems in both the distributed computing and the communication complexity model, answering the open problem of Das Sarma et al. and subsuming many bounds in [Babai, Frankl, and Simon, FOCS 96], and (2) the first lower bound that is tight for all weight aspect ratios, matching previous upper bounds of [Elkin, STOC 04]. Submitted for a Regular Presentation. The full version of this paper can be found as [15] at http://arxiv.org/abs/1207.5211. ∗Department of Computer Science, Ben-Gurion University, Beer-Sheva, 84105, Israel. E-mail: [email protected]. †Division of Mathematical Sciences, Nanyang Technological University, Singapore 637371 & Centre for Quantum Technologies, National University of Singapore, Singapore 117543. E-mail: [email protected]. Research at the Centre for Quantum Technologies is funded by the Singapore Ministry of Education and the National Research Foundation. ‡Division of Mathematical Sciences, Nanyang Technological University, Singapore 637371. Work partially done while at University of Vienna, Austria. E-mail: [email protected]. §Division of Mathematical Sciences, Nanyang Technological University, Singapore 637371 & Department of Computer Science, Brown University, Providence, RI 02912, USA. E-mail: [email protected]. Supported in part by the following research grants: Nanyang Technological University grant M58110000, Singapore MOE Academic Research Fund (AcRF) Tier 2 grant MOE2010-T2-2-082, and a grant from the US-Israeli Binational Science Foundation (BSF).