Quantum Communication Advantage in TFNP

2024/11/05 by Mika Göös, Tom Gur, Göös, Mika +4 · 5 citations
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Quantum-Dot Cellular Automata

paper · pdf · doi:10.48550/arxiv.2411.03296

openalex publication_date 2024/11/05 · openalex created_date 2024/11/15 · openalex updated_date 2026/07/30

Abstract

We exhibit a total search problem with classically verifiable solutions whose communication complexity in the quantum SMP model is exponentially smaller than in the classical two-way randomized model. Our problem is a bipartite version of a query complexity problem recently introduced by Yamakawa and Zhandry (JACM 2024). We prove the classical lower bound using the structure-vs-randomness paradigm for analyzing communication protocols.

Cited by

• A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity
• Pseudodeterministic Communication Complexity
• Space-Bounded Communication Complexity of Unitaries
• Magic and communication complexity
• Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication

Related

• Separations in query complexity for total search problems
• Quantum versus classical simultaneity in communication complexity
• Quantum Communication-Query Tradeoffs
• Quantum vs. Classical Communication and Computation
• The one-way communication complexity of the Boolean Hidden Matching Problem