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

          @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}}
          }
          

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.