PIRSA:06010001

Two exponential separations in communication complexity through bounded-error quantum state indistinguishability

Gavinsky, D. (2006). Two exponential separations in communication complexity through bounded-error quantum state indistinguishability. Perimeter Institute. https://pirsa.org/06010001

Gavinsky, Dmitry. Two exponential separations in communication complexity through bounded-error quantum state indistinguishability. Perimeter Institute, Jan. 11, 2006, https://pirsa.org/06010001 

          @misc{ pirsa_PIRSA:06010001,
            doi = {10.48660/06010001},
            url = {https://pirsa.org/06010001},
            author = {Gavinsky, Dmitry},
            keywords = {Quantum Information},
            language = {en},
            title = {Two exponential separations in communication complexity through bounded-error quantum state indistinguishability},
            publisher = {Perimeter Institute},
            year = {2006},
            month = {jan},
            note = {PIRSA:06010001 see, \url{https://pirsa.org}}
          }

Dmitry Gavinsky

Institute for Quantum Computing (IQC)

Talk number
PIRSA:06010001
Collection
Talk Type
Subject
Abstract
We consider the problem of bounded-error quantum state identification: given one of two known states, what is the optimal probability with which we can identify the given state, subject to our guess being correct with high probability (but we are permitted to output "don't know" instead of a guess). We prove a direct product theorem for this problem. Our proof is based on semidefinite programming duality and the technique may be of wider interest. Using this result, we present two new exponential separations in the simultaneous message passing model of communication complexity. Both are shown in the strongest possible sense: -- 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; -- we describe a relation that can be computed with O(log n) classical bits of communication in the presence of shared entanglement, but needs (almost) n^(1/3) communication if the parties share randomness but no entanglement, even if communication is quantum.