Quantum Distributed Network Computing: Lower Bounds and Techniques

摘要: The focus of this paper is on {\em quantum distributed} computation, where we investigate whether communication can help in speeding up} distributed network algorithms. Our main result that for certain fundamental problems such as minimum spanning tree, cut, and shortest paths, does not} substantially up algorithms these compared to the classical setting. In order obtain result, extend technique Das Sarma et al. [SICOMP 2012] a uniform approach prove non-trivial lower bounds several graph optimization (both exact approximate versions) well verification problems, some which are new even setting, e.g. tight randomized Hamiltonian cycle tree verification, answering an open problem al., bound terms weight aspect ratio, matching upper Elkin [STOC 2004]. introduces Server model} Quantum Simulation Theorem} together provide connection between complexity. model standard two-party complexity augmented with additional power; yet, most hardness carried over model. Theorem carries further computing. techniques, except proof model, require very little knowledge computing, overcoming usual impediment proving