Distributed Quantum Interactive Proofs
Distributed Quantum Interactive Proofs
复制标题
DOI：
10.4230/lipics.stacs.2023.42
复制
发表时间：
2022-10
期刊：
影响因子：
--
通讯作者：
Franccois Le Gall;Masayuki Miyamoto;H. Nishimura
中科院分区：
文献类型：
--
作者：
Franccois Le Gall;Masayuki Miyamoto;H. Nishimura
分布式交互式证明的研究由 Kol、Oshman 和 Saxena [PODC 2018] 发起，作为分布式决策机制（证明标签方案等）的推广，近年来受到了广泛关注。在分布式交互式证明中，$n$节点网络$G$的节点可以与强大的证明者交换短消息（称为证书）。目标是确定输入（包括 $G$ 本身）是否属于某种语言，并尽可能减少节点和证明者之间的交互次数和交换位。有几个结果表明，与非交互式分布式证明相比，通过恒定数量的交互可以大大减小证书的大小。在本文中，我们介绍了分布式交互式证明的量子对应物：证书现在可以是量子比特，并且网络的节点可以执行量子计算。本文的第一个结果表明，通过使用量子分布式交互证明，可以显着减少交互次数。更准确地说，我们的结果表明，对于任何常数~$k$，可以由$f(n)$位证书大小的$k$转经典（即非量子）分布式交互协议决定的语言类包含在可以由$O(f(n))$位证书大小的$5$转分布式量子交互协议决定的语言类中。我们还表明，如果允许使用共享随机性，轮数可以减少到 3 轮。由于目前还没有类似的转数减少\emph{经典}技术，我们的结果也证明了量子计算在分布式交互式证明中的威力。
The study of distributed interactive proofs was initiated by Kol, Oshman, and Saxena [PODC 2018] as a generalization of distributed decision mechanisms (proof-labeling schemes, etc.), and has received a lot of attention in recent years. In distributed interactive proofs, the nodes of an $n$-node network $G$ can exchange short messages (called certificates) with a powerful prover. The goal is to decide if the input (including $G$ itself) belongs to some language, with as few turns of interaction and as few bits exchanged between nodes and the prover as possible. There are several results showing that the size of certificates can be reduced drastically with a constant number of interactions compared to non-interactive distributed proofs. In this paper, we introduce the quantum counterpart of distributed interactive proofs: certificates can now be quantum bits, and the nodes of the network can perform quantum computation. The first result of this paper shows that by using quantum distributed interactive proofs, the number of interactions can be significantly reduced. More precisely, our result shows that for any constant~$k$, the class of languages that can be decided by a $k$-turn classical (i.e., non-quantum) distributed interactive protocol with $f(n)$-bit certificate size is contained in the class of languages that can be decided by a $5$-turn distributed quantum interactive protocol with $O(f(n))$-bit certificate size. We also show that if we allow to use shared randomness, the number of turns can be reduced to 3-turn. Since no similar turn-reduction \emph{classical} technique is currently known, our result gives evidence of the power of quantum computation in the setting of distributed interactive proofs as well.