We consider the problem of implementing two-party interactive quantum

communication over noisy channels, a necessary endeavor if we wish to

fully reap quantum advantages for communication.

For an arbitrary protocol with n messages, designed for

noiseless qudit channels, our main result is a simulation method that fails with probability less than

$2^{-\Theta(n\epsilon)}$ and uses a qudit channel $n(1 + \Theta

(\sqrt{\epsilon}))$ times, of which an $\epsilon$ fraction can be

corrupted adversarially.

The simulation is thus capacity achieving to leading order, and

we conjecture that it is optimal up to a constant factor in

the $\sqrt{\epsilon}$ term.

Furthermore, the simulation is in a model that does not require

pre-shared resources such as randomness or entanglement between the

communicating parties.

Surprisingly, this outperforms the best-known overhead of $1 +

O(\sqrt{\epsilon \log \log 1/\epsilon})$ in the corresponding

\emph{classical} model, which is also conjectured to be optimal

[Haeupler, FOCS'14].

Our work also improves over the best previously known quantum result

where the overhead is a non-explicit large constant [Brassard \emph{et

al.}, FOCS'14] for low $\epsilon$.

JA - Annual ACM Symposium on the Theory of Computing STOC 2018
UR - http://acm-stoc.org/stoc2018/STOC-2018-Accepted.html
ER -
TY - JOUR
T1 - Raz-McKenzie simulation with the inner product gadget
JF - Electronic Colloquium on Computational Complexity (ECCC)
Y1 - 2017
A1 - Xiaodi Wu
A1 - Penghui Yao
A1 - Henry Yuen
AB - In this note we show that the Raz-McKenzie simulation algorithm which lifts deterministic query lower bounds to deterministic communication lower bounds can be implemented for functions f composed with the Inner Product gadget 1ip(x, y) = P i xiyi mod 2 of logarithmic size. In other words, given a function f : {0, 1} n → {0, 1} with deterministic query complexity D(f), we show that the deterministic communication complexity of the composed function f ◦ 1 n ip is Θ(D(f) log n), where f ◦ 1 n ip(x, y) = f(1ip(x 1 , y 1 ), . . . , 1ip(x n , y n )) where x = (x 1 , . . . , x n ), y = (y 1 , . . . , y n ) and each x i and y i are O(log n) bit strings. In [RM97] and [GPW15], the simulation algorithm is implemented for functions composed with the Indexing gadget, where the size of the gadget is polynomial in the input length of the outer function f.

UR - https://eccc.weizmann.ac.il/report/2017/010/ ER - TY - CONF T1 - Exponential Separation of Quantum Communication and Classical Information T2 - 20th Annual Conference on Quantum Information Processing (QIP) Y1 - 2016 A1 - Anurag Anshu A1 - Dave Touchette A1 - Penghui Yao A1 - Nengkun Yu AB -We exhibit a Boolean function for which the quantum communication complexity is exponentially larger than the classical information complexity. An exponential separation in the other direction was already known from the work of Kerenidis et. al. [SICOMP 44, pp. 1550-1572], hence our work implies that these two complexity measures are incomparable. As classical information complexity is an upper bound on quantum information complexity, which in turn is equal to amortized quantum communication complexity, our work implies that a tight direct sum result for distributional quantum communication complexity cannot hold. The function we use to present such a separation is the Symmetric k-ary Pointer Jumping function introduced by Rao and Sinha [ECCC TR15-057], whose classical communication complexity is exponentially larger than its classical information complexity. In this paper, we show that the quantum communication complexity of this function is polynomially equivalent to its classical communication complexity. The high-level idea behind our proof is arguably the simplest so far for such an exponential separation between information and communication, driven by a sequence of round-elimination arguments, allowing us to simplify further the approach of Rao and Sinha.

As another application of the techniques that we develop, we give a simple proof for an optimal trade-off between Alice's and Bob's communication while computing the related Greater-Than function on n bits: say Bob communicates at most b bits, then Alice must send n/exp(O(b)) bits to Bob. This holds even when allowing pre-shared entanglement. We also present a classical protocol achieving this bound.