ECCC-Report TR07-100https://eccc.weizmann.ac.il/report/2007/100Comments and Revisions published for TR07-100en-usSat, 13 Oct 2007 15:32:47 +0200
Paper TR07-100
| The Pattern Matrix Method for Lower Bounds on Quantum Communication |
Alexander A. Sherstov
https://eccc.weizmann.ac.il/report/2007/100 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 different proof of Razborov's result, using the
original, _one-dimensional_ discrepancy method. This refutes the
commonly held intuition (Razborov 2003) that the original discrepancy
method fails for functions such as DISJOINTNESS.
More importantly, our communication lower bounds hold for
a much broader class of functions for which no methods were available.
Namely, fix an arbitrary function f:{0,1}^{n/2} ->{0,1} and let A
be the Boolean matrix whose rows are each an application of f to
some subset of the variables x_1, NOT x_1, ..., x_n, NOT x_n. We
prove that the communication complexity of A in the bounded-error
quantum model with and without entanglement is \Omega(d), where d
is the (1/3)-approximate degree of f. From this result, Razborov's
lower bounds follow easily.
Our proof technique is novel and has two ingredients. The
first is a certain equivalence of approximation and orthogonality
in Euclidean n-space, which we establish using linear-programming
duality. The second is a new construction of suitably structured
matrices with low spectral norm, which we realize using matrix
analysis and the Fourier transform over (Z_2)^n.
Sat, 13 Oct 2007 15:32:47 +0200https://eccc.weizmann.ac.il/report/2007/100