CS Paper Radar

Closest papers

Nearest neighbours by meaning across the whole index.

On the quantum communication complexity of total functions

cs.CC quant-ph ·2026-08-19 ·Dmytro Gavinsky
highly cited similarity 0.70
Abstract

We present a total function with a polylogarithmic two-message quantum protocol, whereas every randomised protocol, even with arbitrarily many rounds, requires polynomial communication.

0.44

$\mathsf{BQP} \subseteq \mathsf{IP}$ Does Not Relativize

cs.CC quant-ph ·2026-09-22 ·Adam Bouland, Andrew Huang, Anand Natarajan, Itay Shalit, Avishay Tal
similarity 0.64
Abstract

We construct an oracle relative to which $\mathsf{BQP} \not\subseteq \mathsf{IP}$, resolving a long-standing open question in quantum complexity theory. Together with recent work due to Aaronson et al., our work also gives the first oracle separation between $\mathsf{IP}$ and $\mathsf{MIP}$, answering a question dating back to Fortnow's thesis. Our separation is based on the Forrelation problem, where given Boolean functions $f$ and $g$, the goal is to determine if $f$ is correlated with the Fourier spectrum of $g$. While this task is solvable by a query-efficient quantum algorithm, we show that it admits no classical interactive protocol with polynomial communication and a polynomial-query verifier. Our proof is based on (i) a new structural result showing how to approximate Avg-Max circuits (which are well-known to capture the power of interactive proofs in the oracular setting) by convex functions with small first and second derivatives and (ii) a novel analysis establishing that the Forrelation distribution suggested by Aaronson and Ambainis fools such functions. Our results imply that any prover-efficient classical interactive protocol for $\mathsf{BQP}$ must rely on non-relativizing techniques. This might serve as a partial explanation for the lack of progress towards doubly-efficient, unconditionally sound classical verification of quantum computation.

0.42

Constant-round quantum advantage in communication complexity for total functions

cs.CC quant-ph ·2026-08-20 ·Atsuya Hasegawa, François Le Gall
similarity 0.63
Abstract · 13 pages

We show that there exists a total function for which there is a polynomial gap between the randomized and the constant-round quantum communication complexity. Previously, such a separation was known only for quantum protocols using polynomially many rounds.

0.39

Quantum Advantage in Local Certification of Graph Properties

cs.DC ·2026-11-05 ·Benjamín Jáuregui, Masayuki Miyamoto
theoryhot direction similarity 0.60
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

Nonuniform QCPH Collapse Implies QCPH Collapse

cs.CC quant-ph ·2026-10-03 ·Jeremy Ahrens Huang
hot direction similarity 0.59
Abstract · 8 pages

Despite the importance of the non-uniform Polynomial-Time Hierarchy (PH/poly) in classical complexity understanding the collapse conditions of the Polynomial-Time Hierarchy (PH), a quantum equivalent of PH/poly has yet to be studied in the literature. We introduce the non-uniform computational Quantum Polynomial-Time Hierarchy (QCPH/mpoly), the quantum equivalent of PH/poly, and show that it collapses if and only if QCPH, the quantum equivalent of PH introduced by Gharibian et al. (comput. complex. 2022), also collapses. We also show that QCPH collapses if coQCMA is contained in QCMA/mpoly. These results are analogous to those of Yap (TCS 1983) commonly used to invoke the collapse of PH in classical complexity. QCPH/mpoly is analogous to QCPH with non-uniform quantum verifier circuits.

0.37

The Commuting Local Hamiltonian Problem: Relativized Evidence Against BQP-Hardness

cs.CC quant-ph ·2026-09-30 ·Itay Shalit, Mark Zhandry
hot direction similarity 0.58
Abstract

The commuting local-Hamiltonian (CLH) problem is a restriction of the local-Hamiltonian problem, in which the terms of the Hamiltonian are required to pairwise commute. A long line of work has shown that the problem lies in $\mathsf{NP}$ for certain families of commuting local Hamiltonians. Nevertheless, there has been no formal evidence against the possibility that the general CLH problem is $\mathsf{QMA}$-complete. CLH is complete for the complexity class $\mathsf{QIMA}$, defined through quantum verifiers whose local gates commute. Therefore, CLH is $\mathsf{QMA}$-complete if and only if $\mathsf{QIMA}=\mathsf{QMA}$. In this work, we introduce a classical-oracle analogue $\mathsf{QIMA}^{\mathcal{O}}$ and construct a classical oracle $\mathcal{O}$ such that $\mathsf{BQP}^{\mathcal{O}}\not\subseteq\mathsf{QIMA}^{\mathcal{O}}$. Since $\mathsf{BQP}^{\mathcal{O}}\subseteq\mathsf{QMA}^{\mathcal{O}}$ for any classical oracle $\mathcal{O}$, this implies $\mathsf{QIMA}^{\mathcal{O}}\neq\mathsf{QMA}^{\mathcal{O}}$ for our constructed oracle. Thus, our result provides relativized evidence against the possibility that the general commuting local-Hamiltonian problem is $\mathsf{BQP}$-hard, and hence also against the possibility that it is $\mathsf{QMA}$-complete.

0.27

Optimal and Verifiable Quantum Advantages in Communication Complexity

cs.CC quant-ph ·2026-10-04 ·Ryan Anselm, Michelle Ding, Dar Gilboa, Sabee Grewal
hot direction similarity 0.58
Abstract · 65 pages

We establish optimal quantum-classical separations in communication complexity for search problems. We introduce a total search problem called Pelagic Fourier Fishing and show that it admits an $n$-qubit quantum one-way protocol, whereas every randomized two-way protocol requires $Ω(2^n)$ bits of communication. We then introduce a variant of this problem whose solutions can be verified in polynomial time. This variant also admits an $n$-qubit quantum one-way protocol, while every randomized one-way protocol requires $Ω(2^n)$ bits of communication. We also construct a family of efficiently verifiable total search problems achieving an $n$ versus $Ω_d(n^d)$ separation between quantum one-way and randomized one-way communication for every fixed $d \ge 2$. In the quantum protocol, Alice prepares her message using a single unitary from the $d$th level of the Clifford hierarchy, and Bob performs a Clifford measurement. This separation is asymptotically optimal under this restriction on Alice's message. For $d = 2$, Alice's message is a stabilizer state and Bob's measurement is Clifford, so the protocol uses no magic, yet achieves an optimal quadratic quantum advantage. Finally, we discuss how these separations can be adapted to near-term quantum advantage experiments in which the demonstrated advantage is both unconditional and efficiently verifiable.

0.47

$\mathsf{EQP}\subseteq\mathsf{IP}$ Does Not Relativize

cs.CC quant-ph ·2026-11-09 ·Sinan Oral, Supartha Podder
similarity 0.58
Abstract · 50 pages, 1 figure, 2 tables

We construct a recursive oracle $O$ and a unary language $L\in\mathsf{EQP}^O\setminus(\mathsf{IP}^O\cup\mathsf{PH}^O)$, strengthening the $\mathsf{BQP}$ versus $\mathsf{IP}$ oracle separation of Bouland et al. to exact quantum computation. The separation is based on a variant of the Forrelation problem in which the normalized correlation of one Boolean function with the Fourier transform of another is promised to be exactly $+1/2$ or $-1/2$. The main technical contribution is a repair method that constructs distributions supported on these exact levels while preserving the indistinguishability needed for the $\mathsf{IP}$ and $\mathsf{PH}$ lower bounds. A uniform polynomial-time quantum algorithm distinguishes the two cases with certainty using only three oracle queries.

0.19