# Quantum Advantage in Local Certification of Graph Properties

DevFeed: [Quantum Advantage in Local Certification of Graph Properties](<https://devfeed.tech/articles/quantum-advantage-in-local-certification-of-graph-properties-121275.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.08076>)

Author: Benjam\\'in J\\'auregui, Masayuki Miyamoto

Published: 2026-11-06T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Distributed Computing](<https://devfeed.tech/sources/arxiv-distributed-computing.md>)

Topics: [graph theory](<https://devfeed.tech/topics/graph-theory.md>), [Graphs](<https://devfeed.tech/topics/graphs.md>)

Tags: [certificate](<https://devfeed.tech/tags/certificate.md>), [certificates](<https://devfeed.tech/tags/certificates.md>), [certification](<https://devfeed.tech/tags/certification.md>), [communication](<https://devfeed.tech/tags/communication.md>), [complexity](<https://devfeed.tech/tags/complexity.md>), [cs-dc](<https://devfeed.tech/tags/cs-dc.md>), [distributed](<https://devfeed.tech/tags/distributed.md>), [dma](<https://devfeed.tech/tags/dma.md>), [equality](<https://devfeed.tech/tags/equality.md>), [global](<https://devfeed.tech/tags/global.md>), [graph](<https://devfeed.tech/tags/graph.md>), [input](<https://devfeed.tech/tags/input.md>), [local](<https://devfeed.tech/tags/local.md>), [lower-bound](<https://devfeed.tech/tags/lower-bound.md>), [messages](<https://devfeed.tech/tags/messages.md>), [model](<https://devfeed.tech/tags/model.md>), [network](<https://devfeed.tech/tags/network.md>), [properties](<https://devfeed.tech/tags/properties.md>), [property](<https://devfeed.tech/tags/property.md>), [quantum](<https://devfeed.tech/tags/quantum.md>), [quantum-advantage](<https://devfeed.tech/tags/quantum-advantage.md>)

## AI overview

Local certification verifies global graph properties through neighbor communication and certificates from an untrusted prover; complexity is the largest certificate at any vertex. The paper establishes quantum advantages for graph properties measured by the number of vertices n. For each fixed μ >= 1, it gives a one-round distributed quantum Merlin-Arthur (dQMA) protocol for a constructed property using O(μ log n)-qubit certificates and messages, while every μ-round classical distributed Merlin-Arthur (dMA) protocol requires Ω(n/(μ log² n))-bit certificates. For graph symmetry--the existence of a nontrivial automorphism--it gives a one-round dQMA protocol using Õ(n^(5/3)) qubits, compared with a known Ω(n²)-bit lower bound for one-round dMA. The supplied text is an abstract, so protocol details are not available here.

## Source excerpt

arXiv:2611.08076v1 Announce Type: new 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 $\mu \ge 1$, we construct a graph property admitting a one-round dQMA protocol with $O(\mu \log n)$-qubit certificates and messages, whereas every $\mu$-round distributed Merlin-Arthur (dMA) protocol requires $\Omega(n/(\mu \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 $\Omega(n^2)$-bit certificate lower bound is known.