CS Paper Radar

Reducing Provers in Distributed Quantum Verification

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

cs.DC quant-ph ·submitted 2026-11-09 15:47 UTC · v1

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)$.

Comment
22 pages (including references), 4 figures. Submitted to SIROCCO 2027

Closest papers

Nearest neighbours by meaning across the whole index.

Quantum Advantage in Local Certification of Graph Properties

cs.DC ·2026-11-05 ·Benjamín Jáuregui, Masayuki Miyamoto
theoryhot direction similarity 0.74
Abstract · Shortened abstract for arXiv

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.

0.29

Distributed Quantum Property Testing with Quantum Carrier Pigeons

cs.DS quant-ph ·2026-09-08 ·Kenny Chen, Mina Doosti, Ryan Sweke, Chirag Wadhwa
theory similarity 0.73
Abstract · Merges and subsumes arXiv:2604.05962 and arXiv:2606.31753, and includes additional/improved results. 67 pages, 1 figure, 1 table

We introduce a framework for distributed quantum inference under communication constraints. In our model, $m$ distributed nodes each receive one copy of an unknown $d$-dimensional quantum state $ρ$, before communicating via a constrained one-way communication channel with a central node, which aims to infer some property of $ρ$. This framework generalizes the classical distributed inference framework introduced by Acharya, Canonne, and Tyagi [COLT 2019], by allowing quantum resources such as quantum communication and shared entanglement. Within this setting, we focus on the fundamental problem of quantum state certification: Given a complete description of some state $σ$, decide whether $ρ=σ$ or $\|ρ-σ\|_1\geq ε$. Additionally, we focus on the case of limited communication between distributed nodes and the central node: we assume each communication channel is limited to only $n_c$ bits and $n_q$ qubits with $n_c + n_q \leq \log d$. When all nodes can make use of a shared source of randomness, we show that the copy complexity of distributed state certification is $Θ(\frac{d^2}{2^{n_q} 2^{n_c/2}ε^2})$. We further demonstrate that shared randomness is necessary to achieve the above complexity, by proving an $Ω(\frac{d^3}{4^{n_q} 2^{n_c} ε^2})$ lower bound in the $\textit{private-coin}$ setting. Moreover, we develop a private-coin algorithm that matches this bound up to a $\sqrt{\log d}$ factor, showing this complexity is near-optimal. Together, our work establishes a general framework for distributed quantum inference with communication constraints and characterizes the complexity of distributed state certification with limited communication.

0.45

On quantum interactive proofs with a laconic prover

cs.CC quant-phcs.CR ·2026-09-30 ·Zihan Hu, Yupan Liu
theory similarity 0.70
Abstract · 66 pages, 4 protocols, 2 algorithms, 3 circuits, 4 tables. v2: Minor changes

Interactive proof systems with a laconic prover, studied by Goldreich, Vadhan, and Wigderson (CC, 2002), capture problems verifiable with logarithmic prover communication in the classical setting. For two-message quantum analogs, even a single-bit prover response contains quantum statistical zero-knowledge ($\sf QSZK$), introduced by Watrous (FOCS 2002). However, restricting the verifier's question to classical public coins collapses the corresponding class to $\sf BQP$, as shown by Beigi, Shor, and Watrous (ToC, 2011). We further study two-message quantum interactive proof systems with a laconic prover. To this end, we introduce the class ${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$, where $\ell$ is the length of the prover's response, and establish: 1. A natural complete characterization of ${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$ by Multi-State Distinguishability. In particular, Quantum State Distinguishability (QSD) is ${\sf QIP}_{\rm bit}$-complete. Since QSD is $\sf QSZK$-hard, our result places ${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$, for $\ell\geq 2$, in a landscape "just above" $\sf QSZK$. 2. Easy regimes for ${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$ collapsing to $\sf QSZK$. We prove that QSD$[a,b]$ (and thus ${\sf QIP}_{\rm bit}[a,b]$) is in $\sf QSZK$ when $a(n)-b(n)\geq 1/O(\log n)$, and combine this with an answer compression from ${\sf QIP}_{\ell\text{-}{\rm bit}}[2,c,s]$ to ${\sf QIP}_{\rm bit}$ to obtain another easy regime when $2c>(1+2^{\ell/2})s$. Remarkably, our improved polarization applies to SD and $\sf SZK$, resolving an open problem in Sahai and Vadhan (JACM, 2003). 3. Quantum public coins also make the interaction useless: ${\sf qc}\text{-}{\sf QAM}[O(\sqrt{\log{n}})]$ with constant gap is in $\sf BQP$, where ${\sf qc}\text{-}{\sf QAM}[\ell]$ is a subclass of ${\sf QIP}_{\ell\text{-}{\rm bit}}(2)$ in which the verifier's question is exactly halves of EPR pairs.

0.48

Zero Knowledge Proofs in Quantum Networks

cs.CR quant-phcs.SImath-ph ·2026-09-28 ·Tuhin Paul, Srijani Das, Manasi Patra, Ramij Rahaman
similarity 0.69
Abstract · 18 pages, 1 figure

Zero-knowledge proofs (ZKPs) enable the verification of a statement without revealing any information beyond its validity and constitute a fundamental primitive in cryptography and information theory. However, existing constructions rely on computational assumptions and are predominantly confined to bipartite settings, leaving their information-theoretic realization in bipartite or network scenarios largely unexplored. Here we develop a framework for zero-knowledge verification based on the indistinguishability of quantum states under operational constraints. Exploiting the fundamental limitations imposed by local operations, we show that a verifier is inherently restricted from extracting information about the underlying state while retaining the ability to verify correctness. We construct explicit protocols for multiparty quantum networks that achieve information-theoretic security, ensuring that no subset of collaborating parties can gain knowledge beyond the validity of the statement, independent of their joint computational power.

0.36

Classical Verification of Quantum Computation Beyond the Polynomial Hierarchy

cs.CC quant-phcs.CR ·2026-10-27 ·Atul Mantri
theory similarity 0.67
Abstract

It is not known whether a classical polynomial-time verifier can verify arbitrary polynomial-time quantum computations with an efficient quantum honest prover without computational assumptions. We show that, relative to a classical oracle, such verification is possible for a language beyond the polynomial hierarchy that is decided exactly in quantum polynomial time. The protocol is public-coin, with perfect completeness and soundness error at most 1/4. To our knowledge, no language with such a proof system was previously proved to lie outside AM relative to an oracle. For every unbounded polynomial-time computable function, the oracle can be chosen so that the message count and the oracle query counts of the quantum algorithm, verifier, and honest prover are bounded by this function of the input length. The message count is optimal up to a constant factor, since for a suitable oracle every interactive proof system for the language uses at least a constant fraction of the messages of our protocol on infinitely many lengths, with a constant depending on its verifier. The language is a variant of recursive Fourier sampling in which code tables encode secrets that address data tables. The tables are evaluated recursively, and the oracle stores only the leaves. The quantum algorithm recovers every secret exactly, and the verifier checks the prover's secrets recursively against random code entries. The recursion restricts the input in a correlated way, as the same secret fixes the code bits and chooses the free coordinate, so Håstad's switching lemma does not apply. We prove a switching theorem for these restrictions, which may be of independent interest. For instances of sufficient height, no constant-depth circuit of size $2^{\mathrm{poly}(n)}$ changes its output with probability above $2^{-Ω(n)}$ when the answer of a random instance is flipped by changing a single leaf.

0.30

Certified Randomness without Structure Against Shallow-Query Adversaries

cs.CR quant-ph ·2026-08-25 ·Dakshita Khurana, Bhaskar Roberts, Avishay Tal
top venuetheory similarity 0.67
Abstract · To be published at FOCS 2026

In a recent breakthrough, Yamakawa and Zhandry (J. ACM 2024) constructed a proof of quantumness in the quantum random oracle model (QROM) in which the quantum prover samples a codeword preimage of a publicly computable function H. They conjectured that given any H, a successful prover must sample their preimage from a high-entropy distribution over possible answers. If true, this would give a certifiable randomness protocol in the quantum random oracle model. As partial evidence for their conjecture, Yamakawa and Zhandry proved the security of their certifiable randomness protocol assuming the Aaronson-Ambainis conjecture. We prove the security of the certifiable randomness protocol of Yamakawa-Zhandry unconditionally, without relying on the unproven Aaronson-Ambainis conjecture, against low query-depth quantum adversaries: specifically, adversaries that make up to o(\log λ) adaptive quantum queries to the random oracle.

0.43

QMA(2) with Limited Shared Entanglement

cs.CC quant-ph ·2026-09-30 ·Alex Della Schiava, Ranitha Mataraarachchi
hot direction similarity 0.66
Abstract · 27 pages (including appendices), 1 table, 0 figures. v3: updated arXiv metadata

In $\mathsf{QMA}(2)$, two computationally unbounded provers submit unentangled quantum witnesses to a polynomial-time quantum verifier. We ask whether allowing limited shared entanglement between the two provers changes the power of $\mathsf{QMA}(2)$. To this end, we formalize $\mathsf{QMA}(2;h)$, a variant in which the provers initially share $h$ EPR pairs, as suggested by Aaronson, Beigi, Drucker, Fefferman, and Shor (ToC~2009). We show that polynomially many shared EPR pairs give the provers no cheating advantage: $\mathsf{QMA}(2)\subseteq\mathsf{QMA}(2;h)$ for $h=\operatorname{poly}(n)$. For logarithmically many pairs, the power of $\mathsf{QMA}(2)$ remains unchanged, strengthening this inclusion to $\mathsf{QMA}(2)=\mathsf{QMA}(2;h)$ for $h=O(\log n)$. Finally, we introduce a variant that also allows classical communication between the provers when preparing the witnesses. This setting is particularly revealing for logarithmic-size witnesses: assuming $\mathsf{NP}\nsubseteq\mathsf{BQP}$, we show that superlogarithmically many shared EPR pairs strictly reduce the model's computational power.

0.34

Quantum Interactive Proofs of Proximity

cs.CC ·2026-11-06 ·Kenan Wood
theoryhot direction similarity 0.66
Abstract

We initiate the systematic study of quantum interactive proofs of proximity (QIPPs). These are quantum interactive proof systems with sublinear communication, where the verifier accepts inputs in a property $Π$ and rejects inputs $\varepsilon$-far from $Π$, while only querying the input a sublinear number of times. 1. We show that all logspace-uniform $\mathbf{NC}$ properties admit QIPPs with query, communication and time complexity all $\widetilde{O}(n^{2/5})$. This improves on the best known classical total complexity of $\widetilde{O}(\sqrt n)$, which is optimal in the worst case for polynomial-time verifiers under the PRG assumption of Kalai and Rothblum (CRYPTO, 2015). This resolves an open question of Dall'Agnol, Gur, Roy Moulik, and Thaler (Quantum, 2022) in the affirmative. 2. Assuming the existence of a post-quantum subexponentially secure PRG computable in logspace-uniform $\mathbf{NC}$, we prove that, for every nondecreasing, logspace-computable query bound $q(n)\le n^{1/2-Ω(1)}$, there exists a property $Π$ in logspace-uniform $\mathbf{NC}$ and a constant $\varepsilon>0$ such that no polynomial-time $\varepsilon$-QIPP for $Π$ can achieve query complexity $q(n)$ and communication complexity $c(n)$ satisfying $q(n)+c(n)=o(n^{1/3})$. 3. We establish a bi-directional connection between QIPPs for logspace-uniform $\mathbf{NC}$ and query-model QIPs for parity. A QIP for $k$-bit parity with total complexity $k^{2/3-Ω(1)}$ yields QIPPs for every logspace-uniform $\mathbf{NC}$ property with total complexity $n^{2/5-Ω(1)}$. Conversely, achieving total complexity $o(n^{2/5})$ within the standard $\mathsf{PVAL}$-based framework requires improving the known query-communication tradeoff for parity. Additionally, we show that almost every size-$2^{βn}$ property ($0<β<1$) requires linear total QIPP complexity at constant proximity.

0.27