Exponential separation of quantum and classical one-way communication complexity

ABSTRACT

We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HMn: Alice gets as input a string x ∈ (0, 1)ⁿ and Bob gets a perfect matching M on the n coordinates. Bob's goal is to output a tuple [i,j,b] such that the edge (i,j) belongs to the matching M and b = xi ⊕ xj. We prove that the quantum one-way communication complexity of HMn is O(log n), yet any randomized one-way protocol with bounded error must use Ω(√n) bits of communication. No asymptotic gap for one-way communication was previously known. Our bounds also hold in the model of Simultaneous Messages (SM) and hence we provide the first exponential separation between quantum SM and randomized SM with public coins.For a Boolean decision version of HMn, we show that the quantum one-way communication complexity remains O(log n) and that the 0-error randomized one-way communication complexity is Ω(n). We prove that any randomized linear one-way protocol with bounded error for this problem requires Ω(√[3] n log n) bits of communication.

REFERENCES

• 1: Scott Aaronson, Limitations of Quantum Advice and One-Way Communication, Proceedings of the 19th IEEE Annual Conference on Computational Complexity, p.320-332, June 21-24, 2004 [doi>10.1109/CCC.2004.16]
• 2: Andris Ambainis , Leonard J. Schulman , Amnon Ta-Shma , Umesh Vazirani , Avi Wigderson, The Quantum Communication Complexity of Sampling, SIAM Journal on Computing, v.32 n.6, p.1570-1585, 2003 [doi>10.1137/S009753979935476]
• 3: L. Babai , P. G. Kimmel, Randomized Simultaneous Messages: Solution Of A Problem Of Yao In Communication Complexity, Proceedings of the 12th Annual IEEE Conference on Computational Complexity, p.239, June 24-27, 1997
• 4: H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf. Quantum fingerprinting. Physical Review Letters, 87(16), 2001.
• 5: Harry Buhrman , Richard Cleve , Avi Wigderson, Quantum vs. classical communication and computation, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.63-68, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276713]
• 6: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 7: P. Frankl and R. M. Wilson. Intersection theorems with geometric consequences. Combinatorica, 1(4):357--368, 1981.
• 8: M. Karchmer and A. Wigderson. Monotone circuits for connectivity require super-logarithmic depth. SIAM J. on Computing, 26(5):255--265, 1990.
• 9: Iordanis Kerenidis , Ronald de Wolf, Exponential lower bound for 2-query locally decodable codes via a quantum argument, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780560]
• 10: Hartmut Klauck, On quantum and probabilistic communication: Las Vegas and one-way protocols, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.644-651, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335396]
• 11: I. Kremer. Quantum Communication. Master's Thesis, The Hebrew University of Jerusalem, 1995.
• 12: Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
• 13: Ilan Newman, Private vs. common random bits in communication complexity, Information Processing Letters, v.39 n.2, p.67-71, July 31, 1991 [doi>10.1016/0020-0190(91)90157-D]
• 14: Ilan Newman , Mario Szegedy, Public vs. private coin flips in one round communication games (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.561-570, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.238004]
• 15: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 16: Ran Raz, Exponential separation of quantum and classical communication complexity, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.358-367, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301343]
• 17: Pranab Sen , S. Venkatesh, Lower Bounds in the Quantum Cell Probe Model, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.358-369, July 08-12, 2001
• 18: Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, v.26 n.5, p.1484-1509, Oct. 1997 [doi>10.1137/S0097539795293172]
• 19: Andrew Chi-Chih Yao, Some complexity questions related to distributive computing(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.209-213, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804414]
• 20: A. C. -C. Yao. Lower bounds by probabilistic arguments. In Proceedings of the 24th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 420--428, 1983.
• 21: A. C. -C. Yao. Quantum circuit complexity. In Proceedings of the 34th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 352--361, Los Alamitos, CA, 1993.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

General Terms:
Theory

Keywords:
communication complexity, hidden matching, quantum computation, separation