## Profile
## Outputs
Title | Category | Date | Authors |
Bounded-error quantum state identification and exponential separations in communication complexity University of Calgary | Publication | 2006-01-01 | D. Gavinsky, J. Kempe, O. Regev, R. d. Wolf | Quantum solution to the hidden subgroup problem for poly-near-Hamiltonian groups University of Calgary | Publication | 2003-01-01 | D. Gavinsky | Two exponential separations in communication complexity through bounded-error quantum state indistinguishabilityWe 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. University of Calgary | Presentation | 2006-01-11 | D. Gavinsky | Quantum communication cannot simulate a public coinWe study the simultaneous message passing model of communication complexity. Building on the quantum fingerprinting protocol of Buhrman et al., Yao recently showed that a large class of efficient classical public-coin protocols can be turned into efficient quantum protocols without public coin. This raises the question whether this can be done always, i.e., whether quantum communication can always replace a public coin in the SMP model. We answer this question in the negative, exhibiting a communication problem where classical communication with public coin is exponentially more efficient than quantum communication. Together with a separation in the other direction due to Bar-Yossef et al., this shows that the quantum SMP model is incomparable with the classical public-coin SMP model. In addition we give a characterization of the power of quantum fingerprinting by means of a connection to geometrical tools from machine learning, a quadratic improvement of Yao's simulation, and a nearly tight analysis of the Hamming distance problem from Yao's paper. University of Calgary | Presentation | 2005-01-15 | D. Gavinsky | Quantum Algorithms for Evaluating Min-Max Trees University of Calgary | Publication | 2008-01-01 | R. Cleve, D. Gavinsky, D. L. Yonge-Mallo |
| |