3
$\begingroup$

Problem. Is it true that any 2-party communication problem $f(x,y)$ of poly-logarithmic complexity in the quantum simultaneous message passing model ($Q''$) has complexity $n^{o(1)}$ (i.e., strongly sub-polynomial) in the classical 2-way communication model ($R$)?

(This problem was written 13.09.2018 by Dmitry Gavinsky from Prague on page 57 of Volume 2 of the Lviv Scottish Book).

Improve this question
$\endgroup$

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.