Bounded-error quantum state identification and exponential separations in communication complexity

ABSTRACT

We consider the problem of bounded-error quantum state identification: given either state α₀ or state α₁, we are required to output '0', '1' or 'DONO' ("don't know"), such that conditioned on outputting '0' or '1', our guess is correct with high probability. The goal is to maximize the probability of not outputting 'DONO'. We prove a direct product theorem: if we're given two such problems, with optimal probabilities a and b, respectively, and the states in the first problem are pure, then the optimal probability for the joint bounded-error state identification problem is O(ab). Our proof is based on semidefinite programming duality and may be of wider interest.Using this result, we present two exponential separations in the simultaneous message passing model of communication complexity. First, we describe a relation that can be computed with O(log n) classical bits of communication in the presence of shared randomness, but needs Ω(n^1/3) communication if the parties don't share randomness, even if communication is quantum. This shows the optimality of Yao's recent exponential simulation of shared-randomness protocols by quantum protocols without shared randomness. Second, we describe a relation that can be computed with O(log n) classical bits of communication in the presence of shared entanglement, but needs Ω((n/log n)^1/3) communication if the parties share randomness but no entanglement, even if communication is quantum. This is the first example in communication complexity where entanglement buys you much more than quantum communication does.

REFERENCES

• 1: A. Ambainis. Communication complexity in a 3-computer model. Algorithmica, 16(3):298--301,1996.
• 2: 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
• 3: Ziv Bar-Yossef , T. S. Jayram , Iordanis Kerenidis, Exponential separation of quantum and classical one-way communication complexity, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007379]
• 4: Ziv Bar-Yossef , T. S. Jayram , Ravi Kumar , D. Sivakumar, Information Theory Methods in Communication Complexity, Proceedings of the 17th IEEE Annual Conference on Computational Complexity, p.93, May 21-24, 2002
• 5: R. Bhatia. Matrix Analysis. Number 169 in Graduate Texts in Mathematics. Springer, 1997.
• 6: H. Buhrman. Quantum computing and communication complexity. EATCS Bulletin, 70:131--141, Feb. 2000.
• 7: H. Buhrman. Personal communication, Nov. 2003.
• 8: H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf. Quantum fingerprinting. Physical Review Letters, 87(16), Sep. 26, 2001.
• 9: R. Cleve and H. Buhrman. Substituting quantum entanglement for communication. Physical Review A, 56(2):1201--1204, 1997.
• 10: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 11: Y. C. Eldar. A semidefinite programming approach to optimal unambiguous discrimination of quantum states. IEEE Transactions on Information Theory, 49:446--456, 2003.
• 12: D. Gavinsky. A note on shared randomness and shared entanglement in communication. quant-ph/0505088, 12 May 2005.
• 13: D. Gavinsky, J. Kempe, and R. de Wolf. Quantum communication cannot simulate a public coin. quant-ph/0411051, 8 Nov 2004.
• 14: D. Gavinsky, J. Kempe, O. Regev, and R. de Wolf. Bounded-error quantum state identification and exponential separations in communication complexity. quant-ph/0511013, 2 Nov 2005.
• 15: A. Golinsky and P. Sen. A note on the power of quantum fingerprinting. quant-ph/0510091, Dec. 2003.
• 16: A. S. Holevo. Bounds for the quantity of information transmitted by a quantum communication channel. Problemy Peredachi Informatsii, 9(3):3--11, 1973. English translation in Problems of Information Transmission, 9:177--183, 1973.
• 17: C. King and M-B. Ruskai. Comments on multiplicativity of maximal p-norms when p=2. In O. Hirota, editor, Quantum Information, Statistics, Probability (Festschrift for A. Holevo). Rinton Press, 2004.
• 18: H. Klauck. Quantum communication complexity. In Proceedings Workshop on Boolean Functions and Applications at 27th ICALP, p.241--252, 2000.
• 19: Ilan Kremer , Noam Nisan , Dana Ron, On randomized one-round communication complexity, Computational Complexity, v.8 n.1, p.21-49, June 1999 [doi>10.1007/s000370050018]
• 20: Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
• 21: L. Lovász. Semidefinite programs and combinatorial optimization. At http://research.microsoft.com/users/lovasz/notes.htm, 2000.
• 22: 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
• 23: 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]
• 24: 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]
• 25: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 26: Lieven Vandenberghe , Stephen Boyd, Semidefinite programming, SIAM Review, v.38 n.1, p.49-95, Mar. 1996 [doi>10.1137/1038003]
• 27: Ronald de Wolf, Quantum communication and complexity, Theoretical Computer Science, v.287 n.1, p.337-353, 25 September 2002 [doi>10.1016/S0304-3975(02)00377-8]
• 28: A. C-C. Yao. Quantum circuit complexity. In Proceedings of 34th IEEE FOCS, p. 352--360, 1993.
• 29: Andrew Chi-Chih Yao, On the power of quantum fingerprinting, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780554]

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Formal models of communication

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity measures

General Terms:
Algorithms, Theory

Keywords:
communication complexity, entanglement, quantum computing, randomness, state identification