On the Power of Quantum Distributed Proofs

Abstract

Quantum nondeterministic distributed computing was recently introduced as dQMA (distributed quantum Merlin-Arthur) protocols by Fraigniaud, Le Gall, Nishimura and Paz (ITCS 2021). In dQMA protocols, with the help of quantum proofs and local communication, nodes on a network verify a global property of the network. Fraigniaud et al. showed that, when the network size is small, there exists an exponential separation in proof size between distributed classical and quantum verification protocols, for the equality problem, where the verifiers check if all the data owned by a subset of them are identical. In this paper, we further investigate and characterize the power of the dQMA protocols for various decision problems. First, we give a more efficient dQMA protocol for the equality problem with a simpler analysis. This is done by adding a symmetrization step on each node and exploiting properties of the permutation test, which is a generalization of the SWAP test. We also show a quantum advantage for the equality problem on path networks still persists even when the network size is large, by considering ``relay points'' between extreme nodes. Second, we show that even in a general network, there exist efficient dQMA protocols for the ranking verification problem, the Hamming distance problem, and more problems that derive from efficient quantum one-way communication protocols. Third, in a line network, we construct an efficient dQMA protocol for a problem that has an efficient two-party QMA communication protocol. Finally, we obtain the first lower bounds on the proof and communication cost of dQMA protocols. To prove a lower bound on the equality problem, we show any dQMA protocol with an entangled proof between nodes can be simulated with a dQMA protocol with a separable proof between nodes by using a QMA communication-complete problem introduced by Raz and Shpilka (CCC 2004).

arXiv comment49 pages

References in corpus (12)

• Quantum fingerprinting
• Faithful Squashed Entanglement
• Efficient Quantum Circuits for Schur and Clebsch-Gordan Transforms
• Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks
• Can quantum mechanics help distributed computing?
• The Efficiency of Quantum Identity Testing of Multiple States
• Quantum Distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model
• A Framework for Distributed Quantum Queries in the CONGEST Model
• Quantum Advantage for the LOCAL Model in Distributed Computing
• Quantum Distributed Complexity of Set Disjointness on a Line
• Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications
• The 7 faces of quantum NP