Publications
Researchers from the National Quantum Information Centre (KCIK) publish their scientific resultsin the top journals around the world. The KCIK Publications database provides access to scientific literature
that has been authored or co-authored by KCIK researchers.
Scientific highlights
QUANTUM BIDDING IN BRIDGE
Sadiq Muhammad, Armin Tavakoli, Maciej Kurant, Marcin Pawłowski, Marek Żukowski, and Mohamed Bourennane
Phys. Rev. X 4, 021047 - Published 12 June 2014
Quantum methods allow us to reduce communication complexity of some computational tasks, with several separated partners, beyond classical constraints. Nevertheless, experimental demonstrations of this have thus far been limited to some abstract problems, far away from real-life tasks. We show here, and demonstrate experimentally, that the power of reduction of communication complexity can be harnessed to gain an advantage in a famous, immensely popular, card game—bridge. The essence of a winning strategy in bridge is efficient communication between the partners. The rules of the game allow only a specific form of communication, of very low complexity (effectively, one has strong limitations on the number of exchanged bits). Surprisingly, our quantum technique does not violate the existing rules of the game (as there is no increase in information flow). We show that our quantum bridge auction corresponds to a biased nonlocal Clauser-Horne-Shimony-Holt game, which is equivalent to a 2→1 quantum random access code. Thus, our experiment is also a realization of such protocols. However, this correspondence is not complete, which enables the bridge players to have efficient strategies regardless of the quality of their detectors.QUANTUM COMMUNICATION COMPLEXITY ADVANTAGE IMPLIES VIOLATION OF A BELL INEQUALITY
Harry Buhrman, Łukasz Czekaj, Andrzej Grudka, Michał Horodecki, Paweł Horodecki, Marcin Markiewicz, Florian Speelman, and Sergii Strelchuk
PNAS 113, 3191-3196 (2016)
SignificanceFor many communication complexity problems the quantum strategies, distinguished by using Bell nonlocal correlations, provide exponential advantage over the best possible classical strategies. Conversely, for any Bell nonlocal correlations there exists a communication complexity problem that is solved more efficiently using the former. Despite many efforts, there were only two problems for which one could certify that any strategy that outperforms the classical one must harbor Bell nonlocal correlations. We prove that any large advantage over the best known classical strategy makes use of Bell nonlocal correlations. Thus, we provide the missing link to the fundamental equivalence between Bell nonlocality and quantum advantage.
Abstract
We obtain a general connection between a large quantum advantage in communication complexity and Bell nonlocality. We show that given any protocol offering a sufficiently large quantum advantage in communication complexity, there exists a way of obtaining measurement statistics that violate some Bell inequality. Our main tool is port-based teleportation. If the gap between quantum and classical communication complexity can grow arbitrarily large, the ratio of the quantum value to the classical value of the Bell quantity becomes unbounded with the increase in the number of inputs and outputs.