Reducing provers simplifies distributed quantum verification tasks

Reducing Provers in Distributed Quantum Verification

Distributed, Parallel, and Cluster Computing

Summary

The paper looks at how groups of quantum computers check shared information using help from quantum proofs. Usually, many helpers called provers provide these proofs, but having fewer provers can make the process simpler. The authors show how to reduce multiple provers down to two or even just one, with some trade-offs in proof size and communication, without losing the system’s effectiveness. This helps make distributed quantum verification more practical.

What this means in practice

  • For quantum network engineers: Optimize quantum verification protocols to reduce prover resources while maintaining proof integrity in distributed quantum networks.
  • For quantum software developers: Improve design of distributed quantum verification algorithms by minimizing communication overhead and prover counts without losing accuracy.

A theory result. No direct application yet.

Authors

Alex Della Schiava, Atsuya Hasegawa, François Le Gall, Harumichi Nishimura

Abstract

In the distributed quantum Merlin-Arthur ($\mathsf{dQMA}$) model introduced by Fraigniaud, Le Gall, Nishimura, and Paz (ITCS 2021), a network of quantum computers verifies a global property with the aid of a quantum proof supplied by an untrusted prover. While the nodes are computationally unbounded, the challenge is to limit proof size and the communication required for verification. In this paper, we consider the model of Hasegawa, Kundu, and Nishimura (PODC 2024), where the proof must be unentangled across nodes, and define its extension to $k$ unentangled provers, denoted by $\mathsf{dQMAS}(k)$. In this setting, we investigate the proof size per node and the communication costs of reducing the number of provers. Our first result reduces the number of provers from $k$ to two, doubling the proof size without additional communication. Moreover, with four additional rounds, we can reduce the number of provers from $k$ to one, using at most three times the original local proof size plus a logarithmic term in the number of nodes. Finally, we establish amplification for perfectly complete protocols. In this regime, a single prover suffices with a constant-factor overhead in our reductions, yielding $\mathsf{dQMAS} = \mathsf{dQMAS}(k)$.