Quantum protocols greatly reduce proof size for verifying network graphs
Quantum Advantage in Local Certification of Graph Properties
Distributed, Parallel, and Cluster Computing
Summary
Verifying big network structures usually requires sharing large pieces of information locally. This paper shows that using quantum communication can drastically shrink the amount of information needed to prove certain network properties. The authors demonstrate this by constructing specific graph properties where quantum methods require exponentially or polynomially smaller proofs compared to traditional ones. This means networks could verify global properties more efficiently with quantum tools.
What this means in practice
- •For network protocol designers: Design distributed network protocols that verify global graph properties using much smaller quantum certificates, reducing communication overhead.
- •For quantum software engineers: Implement one-round quantum proof systems for checking network symmetries that are more communication-efficient than classical methods.
A theory result. No direct application yet.
Authors
Benjamín Jáuregui, Masayuki Miyamoto
Abstract
Local certification allows network vertices to verify global properties using certificates from an untrusted prover and communication with their neighbors. Its complexity is the maximum certificate size at any vertex. Fraigniaud et al. (ITCS 2021) introduced the distributed quantum Merlin-Arthur (dQMA) model and proved an exponential quantum advantage for distributed equality, measured in input-string length. We resolve a question of Hasegawa, Kundu, and Nishimura (PODC 2024) by establishing unconditional exponential and polynomial quantum advantages for graph properties, which depend only on network topology, with complexity measured in the number $n$ of vertices. For every fixed integer $μ\ge 1$, we construct a graph property admitting a one-round dQMA protocol with $O(μ\log n)$-qubit certificates and messages, whereas every $μ$-round distributed Merlin-Arthur (dMA) protocol requires $Ω(n/(μ\log^2 n))$-bit certificates. We also give a one-round dQMA protocol for graph symmetry, the existence of a nontrivial automorphism, with $\widetilde{O}(n^{5/3})$-qubit certificates. This yields a polynomial advantage over one-round dMA protocols, for which an $Ω(n^2)$-bit certificate lower bound is known.