On the Power of Quantum Distributed Proofs

最近，Fraigniaud、Le Gall、Nishimura和Paz（ITCS 2021）将量子非确定性分布式计算作为dQMA（分布式量子Merlin-Arthur）协议引入。在dQMA协议中，通过量子证明和本地通信，网络上的节点验证网络的全局属性。Fraigniaud等人表明，当网络规模较小时，对于相等问题，分布式经典和量子验证协议之间的证明大小存在指数差异。在本文中，我们进一步研究和描述了dQMA协议在各种决策问题中的能力。首先，我们提供了一个更有效的dQMA协议，用于相等问题，并进行了更简单的分析。这是通过在每个节点上添加对称化步骤并利用置换测试的性质完成的，置换测试是SWAP测试的一般化。我们还展示了在路径网络上，即使网络规模较大，相等问题的量子优势仍然存在，通过考虑极端节点之间的“中继点”来实现。其次，我们展示即使在一般网络中，存在有效的dQMA协议，用于排名验证问题、汉明距离问题和更多源自有效量子单向通信协议的问题。第三，在线网络中，我们构建了一个有效的dQMA协议，用于一个具有有效的双方QMA通信协议的问题。最后，我们获得了对dQMA协议的证明和通信成本的第一个下界。为了证明相等问题的下界，我们展示了任何具有节点之间纠缠证明的dQMA协议都可以通过使用Raz和Shpilka（CCC 2004）引入的一个QMA通信完备问题，用节点之间的可分离证明模拟。

研究分布式量子计算中的dQMA协议的能力和效率，探索其在不同决策问题中的应用。

提出更高效的dQMA协议解决相等性问题，并在路径网络和一般网络中展示了dQMA协议的有效性。同时，构建了一种新的dQMA协议，并首次给出了dQMA协议的证明和通信成本下界。

论文提出了更高效的dQMA协议解决相等性问题，并在路径网络和一般网络中展示了dQMA协议的有效性。同时，构建了一种新的dQMA协议，并首次给出了dQMA协议的证明和通信成本下界。

近期相关研究包括Fraigniaud等人的dQMA协议的提出，以及Raz和Shpilka的QMA通信完备问题的研究。