The pattern matrix method for lower bounds on quantum communication

ABSTRACT

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/4->{0,1} and let A be the Boolean matrix whose columns are each an application of f to some subset of the variables x₁,x₂,...,x_n. We prove that the communication complexity of A in the bounded-error quantum model with and without prior entanglement is Omega(d), where d is the approximate degree of f. From this result, Razborov's lower bounds follow easily. Our result also establishes a large new class of total Boolean functions whose quantum communication complexity (regardless of prior entanglement) is at best polynomially smaller than their classical complexity. Our proof method is a novel combination of two ingredients. The first is a certain equivalence of approximation and orthogonality in Euclidean n-space, which follows by linear-programming duality. The second is a new construction of suitably structured matrices with low spectral norm, the pattern matrices, which we realize using matrix analysis and the Fourier transform over (Z₂)ⁿ. The method of this paper has recently inspired important progress in multiparty communication complexity.

REFERENCES

• 1: S. Aaronson and Y. Shi. Quantum lower bounds for the collision and the element distinctness problems. J. ACM, 51(4):595--605, 2004.
• 2: A. Ambainis, L. J. Schulman, A. Ta--Shma, U. V. Vazirani, and A. Wigderson. The quantum communication complexity of sampling. SIAM J. Comput., 32(6):1570--1585, 2003.
• 3: R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf. Quantum lower bounds by polynomials. J. ACM, 48(4):778--797, 2001.
• 4: H. Buhrman and R. de Wolf. Communication complexity lower bounds by polynomials. In CCC, pages 120--130, 2001.
• 5: H. Buhrman, N. K. Vereshchagin, and R. de Wolf. On computation and communication with small bias. In CCC, pages 24--32, 2007.
• 6: A. Chattopadhyay. Discrepancy and the power of bottom fan-in in depth-three circuits. In FOCS, 2007.
• 7: A. Chattopadhyay and A. Ada. Multiparty communication complexity of disjointness. In Electronic Colloquium on Computational Complexity (ECCC), January 2008. Report TR08-002.
• 8: M. David and T. Pitassi. Separating NOF communication complexity classes RP and NP. In Electronic Colloquium on Computational Complexity (ECCC), February 2008. Report TR08-014.
• 9: R. de Wolf. Personal communication, October 2007.
• 10: R. A. DeVore and G. G. Lorentz. Constructive Approximation, volume 303. Springer-Verlag, Berlin, 1993.
• 11: D. Gavinsky, J. Kempe, and R. de Wolf. Strengths and weaknesses of quantum fingerprinting. In CCC, pages 288--298, 2006.
• 12: R. A. Horn and C. R. Johnson. Matrix analysis. New York, 1986.
• 13: P. Hoyer and R. de Wolf. Improved quantum communication complexity bounds for disjointness and equality. In STACS, pages 299--310, 2002.
• 14: A. D. Ioffe and V. M. Tikhomirov. Duality of convex functions and extremum problems. Russ. Math. Surv., 23(6):53--124, 1968.
• 15: H. Klauck. Lower bounds for quantum communication complexity. In FOCS, pages 288--297, 2001.
• 16: H. Klauck, A. Nayak, A. Ta-Shma, and D. Zuckerman. Interaction in quantum communication and the complexity of set disjointness. In STOC, pages 124--133, 2001.
• 17: I. Kremer. Quantum communication. Master's thesis, Hebrew University, Computer Science Department, 1995.
• 18: E. Kushilevitz and N. Nisan. Communication complexity. Cambridge University Press, New York, 1997.
• 19: T. Lee and A. Shraibman. Disjointness is hard in the multi-party number-on-the-forehead model. In CCC, 2008. To appear.
• 20: T. Lee, A. Shraibman, and R. Spalek. A direct product theorem for discrepancy. In CCC, 2008. To appear.
• 21: N. Linial and A. Shraibman. Lower bounds in communication complexity based on factorization norms. In STOC, pp. 699--708, 2007.
• 22: N. Linial and A. Shraibman. Learning complexity vs. communication complexity. In CCC, 2008. To appear.
• 23: M. L. Minsky and S. A. Papert. Perceptrons: expanded edition. MIT Press, Cambridge, Mass., 1988.
• 24: R. Paturi. On the degree of polynomials that approximate symmetric Boolean functions. In STOC, pages 468--474, 1992.
• 25: A. A. Razborov. Quantum communication complexity of symmetric predicates. Izvestiya: Mathematics, 67(1):145--159, 2003.
• 26: A. A. Razborov. Personal communication, June 2007.
• 27: T. J. Rivlin. An Introduction to the Approximation of Functions. Dover Publications, New York, 1981.
• 28: A. Schrijver. Theory of linear and integer programming. John Wiley & Sons, Inc., New York, 1998.
• 29: A. A. Sherstov. Separating AC0 from depth-2 majority circuits. In STOC, pages 294--301, 2007.
• 30: Y. Shi and Y. Zhu. Quantum communication complexity of block-composed functions. Available at arXiv:0710.0095v1, 29 September 2007.
• 31: A. C.-C. Yao. Quantum circuit complexity. In FOCS, pages 352--361, 1993.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.0 GENERAL

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

General Terms:
Theory

Keywords:
approximate degree of boolean functions, bounded-error communication, lower bounds, quantum communication complexity