Publication

Quantum Communication Advantage in TFNP

Mika Tapani Göös
2025

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.

Official source

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Quantum Communication Advantage in TFNP

Chat with Graph Search

Bayesian tomography of high-dimensional on-chip biphoton frequency combs with randomized measurements

Localizing the Source of an Epidemic Using Few Observations

Multiple Query Optimization on the D-Wave 2X Adiabatic Quantum Computer