Interaction in quantum communication and the complexity of set disjointness

ABSTRACT

One of the most intriguing facts about communication using quantum states is that these states cannot be used to transmit more classical bits than the number of qubits used, yet in some scenarios there are ways of conveying information with exponentially fewer qubits than possible classically [3, 26]. Moreover, these methods have a very simple structure---they involve only few message exchanges between the communicating parties.We consider the question as to whether every classical protocol may be transformed to a “simpler” quantum protocol---one that has similar efficiency, but uses fewer message exchanges. We show that for any constant k, there is a problem such that its k+1 message classical communication complexity is exponentially smaller than its k message quantum communication complexity, thus answering the above question in the negative. This in particular proves a round hierarchy theorem for quantum communication complexity, and implies via a simple reduction, an \Omega(N^{1/k}) lower bound for k message protocols for Set Disjointness for constant~k.Our result builds on two primitives, local transitions in bi-partite states (based on previous work) and average encoding which may be of significance in other contexts as well.

REFERENCES

• 1: Dorit Aharonov , Alexei Kitaev , Noam Nisan, Quantum circuits with mixed states, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.20-30, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276708]
• 2: Andris Ambainis, A new protocol and lower bounds for quantum coin flipping, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.134-142, July 2001, Hersonissos, Greece [doi>10.1145/380752.380788]
• 3: A. Ambainis , L. J. Schulman , A. Ta-Shma , U. Vazirani , A. Wigderson, The Quantum Communication Complexity of Sampling, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.342, November 08-11, 1998
• 4: C.H.Bennett and S.J.Wiesner.Communication via one-and two-particle operators on Einstein- Podolsky-Rosen states.Physical Review Letters 69:2881 -2884,1992.
• 5: Ethan Bernstein , Umesh Vazirani, Quantum Complexity Theory, SIAM Journal on Computing, v.26 n.5, p.1411-1473, Oct. 1997 [doi>10.1137/S0097539796300921]
• 6: 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]
• 7: Harry Buhrman , Ronald de Wolf, Communication Complexity Lower Bounds by Polynomials, Proceedings of the 16th Annual Conference on Computational Complexity, p.120, June 18-21, 2001
• 8: Richard Cleve , Wim van Dam , Michael Nielsen , Alain Tapp, Quantum Entanglement and the Communication Complexity of the Inner Product Function, Selected papers from the First NASA International Conference on Quantum Computing and Quantum Communications, p.61-74, February 17-20, 1998
• 9: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 10: Pavol Duris , Zvi Galil , Georg Schnitger, Lower bounds on communication complexity, Information and Computation, v.73 n.1, p.1-22, April 1987 [doi>10.1016/0890-5401(87)90037-X]
• 11: C.A.F chs and J.van de Graaf.Cryptographic distinguishability measures for q ant m-mechanical states.IEEE Transactions on Information Theory 45(4):1216 -1227,1999.
• 12: R.Jozsa.Fidelity for mixed q ant m states.Journal of Modern Optics 41(12):2315 -2323,1994.
• 13: H. Klauck, Lower Bounds for Computation with Limited Nondeterminism, Proceedings of the Thirteenth Annual IEEE Conference on Computational Complexity, p.141, June 15-18, 1998
• 14: 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]
• 15: H.Kla ck.On rounds in quantum communication. LANL Preprint archive,q ant-ph/0004100,2000.
• 16: E.K shilevitz and N.Nisan.Communication Cambridge University Press,1997.
• 17: Hoi-Kwong Lo , H. F. Chau, Why quantum bit commitment and ideal quantum coin tossing are impossible, Physica D, v.120 n.1-2, p.177-187, Sept. 1998
• 18: D.Mayers.Unconditionally secure q ant m bit commitment is impossible.Physical Review Letters 78:3414 -3417,1997.
• 19: Peter Bro Miltersen , Noam Nisan , Shmuel Safra , Avi Wigderson, On data structures and asymmetric communication complexity, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.103-111, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225093]
• 20: Ashwin Nayak, Optimal Lower Bounds for Quantum Automata and Random Access Codes, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.369, October 17-18, 1999
• 21: A.Nayak,A.Ta-Shma,and D.Z ckerman. Interaction in quantum communication and the complexity of set disjointness.Technical report TR 2000-36,DIMACS Center,R tgers University. Earlier version q ant-ph/0005106,2000.
• 22: Noam Nisan , Avi Wigderson, Rounds in communication complexity revisited, SIAM Journal on Computing, v.22 n.1, p.211-219, Feb. 1993 [doi>10.1137/0222016]
• 23: Christos H. Papadimitriou , Michael Sipser, Communication complexity, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.196-200, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802192]
• 24: Stephen J. Ponzio , Jaikumar Radhakrishnan , S. Venkatesh, The communication complexity of pointer chasing: applications of entropy and sampling, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.602-611, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301413]
• 25: J.Preskill.Lect re notes. http://www.theory.caltech.ed /people/preskill/ph229/.
• 26: 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]
• 27: A.Uhlmann.The 'transition probability' in the state space of a algebra.Reports on Mathematical Physics 9:273 -279,1976.
• 28: A.C.-C.Yao.Q ant m circuit complexity.In Proceedings of the 34th Annual Symposium on Foundations of Computer Science pp.352-361,1993.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Set theory

General Terms:
Measurement, Performance, Theory, Verification