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

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.