Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Quantum communication complexity:
TR07-100 | 25th September 2007
Alexander A. Sherstov

The Pattern Matrix Method for Lower Bounds on Quantum Communication

In a breakthrough result, Razborov (2003) gave optimal
lower bounds on the communication complexity of every function f
of the form f(x,y)=D(|x AND y|) for some D:{0,1,...,n}->{0,1}, in
the bounded-error quantum model with and without prior entanglement.
This was proved by the _multidimensional_ discrepancy method. We
give an entirely ... more >>>

TR10-024 | 21st February 2010
Henning Wunderlich, Stefan Arnold

On a singular value method in quantum communication complexity

Comments: 1

We introduce a new lower bound method for bounded-error quantum communication complexity,
the \emph{singular value method (svm)}, based on sums of squared singular values of the
communication matrix, and we compare it with existing methods.

The first finding is a constant factor improvement of lower bounds based on the
spectral ... more >>>

TR10-143 | 19th September 2010
Bo'az Klartag, Oded Regev

Quantum One-Way Communication is Exponentially Stronger Than Classical Communication

In STOC 1999, Raz presented a (partial) function for which there is a quantum protocol
communicating only $O(\log n)$ qubits, but for which any classical (randomized, bounded-error) protocol requires $\poly(n)$ bits of communication. That quantum protocol requires two rounds of communication. Ever since Raz's paper it was open whether the ... more >>>

TR11-040 | 22nd March 2011
Alexander A. Sherstov

Strong Direct Product Theorems for Quantum Communication and Query Complexity

A strong direct product theorem (SDPT) states that solving $n$ instances of a problem requires $\Omega(n)$ times the resources for a single instance, even to achieve success probability $2^{-\Omega(n)}.$ We prove that quantum communication complexity obeys an SDPT whenever the communication lower bound for a single instance is proved by ... more >>>

TR15-081 | 12th May 2015
Mark Braverman, Ankit Garg, Young Kun Ko, Jieming Mao, Dave Touchette

Near-optimal bounds on bounded-round quantum communication complexity of disjointness

We prove a near optimal round-communication tradeoff for the two-party quantum communication complexity of disjointness. For protocols with $r$ rounds, we prove a lower bound of $\tilde{\Omega}(n/r)$ on the communication required for computing disjointness of input size $n$, which is optimal up to logarithmic factors. The previous best lower bound ... more >>>

TR16-016 | 30th January 2016
Zi-Wen Liu, Christopher Perry, Yechao Zhu, Dax Enshan Koh, Scott Aaronson

Doubly infinite separation of quantum information and communication

We prove the existence of (one-way) communication tasks with a subconstant versus superconstant asymptotic gap, which we call "doubly infinite," between their quantum information and communication complexities. We do so by studying the exclusion game [C. Perry et al., Phys. Rev. Lett. 115, 030504 (2015)] for which there exist instances ... more >>>

TR16-072 | 4th May 2016
Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika G\"o{\"o}s, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha

Separations in communication complexity using cheat sheets and information complexity

While exponential separations are known between quantum and randomized communication complexity for partial functions, e.g. Raz [1999], the best known separation between these measures for a total function is quadratic, witnessed by the disjointness function. We give the first super-quadratic separation between quantum and randomized
communication complexity for a ... more >>>

TR17-051 | 16th March 2017
Mark Bun, Justin Thaler

A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$

The approximate degree of a Boolean function $f \colon \{-1, 1\}^n \rightarrow \{-1, 1\}$ is the least degree of a real polynomial that approximates $f$ pointwise to error at most $1/3$. We introduce a generic method for increasing the approximate degree of a given function, while preserving its computability by ... more >>>

ISSN 1433-8092 | Imprint