Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNon-locality and Communication Complexity
153
0
0.0
(
0
)
Authors
Harry Buhrman
Ask ChatGPT about the research
No Arabic abstract
Quantum information processing is the emerging field that defines and realizes computing devices that make use of quantum mechanical principles, like the superposition principle, entanglement, and interference. In this review we study the information counterpart of computing. The abstract form of the distributed computing setting is called communication complexity. It studies the amount of information, in terms of bits or in our case qubits, that two spatially separated computing devices need to exchange in order to perform some computational task. Surprisingly, quantum mechanics can be used to obtain dramatic advantages for such tasks. We review the area of quantum communication complexity, and show how it connects the foundational physics questions regarding non-locality with those of communication complexity studied in theoretical computer science. The first examples exhibiting the advantage of the use of qubits in distributed information-processing tasks were based on non-locality tests. However, by now the field has produced strong and interesting quantum protocols and algorithms of its own that demonstrate that entanglement, although it cannot be used to replace communication, can be used to reduce the communication exponentially. In turn, these new advances yield a new outlook on the foundations of physics, and could even yield new proposals for experiments that test the foundations of physics.
rate research
Read More
Two parts of an entangled quantum state can have a correlation in their joint behavior under measurements that is unexplainable by shared classical information. Such correlations are called non-local and have proven to be an interesting resource for information processing. Since non-local correlations are more useful if they are stronger, it is natural to ask whether weak non-locality can be amplified. We give an affirmative answer by presenting the first protocol for distilling non-locality in the framework of generalized non-signaling theories. Our protocol works for both quantum and non-quantum correlations. This shows that in many contexts, the extent to which a single instance of a correlation can violate a CHSH inequality is not a good measure for the usefulness of non-locality. A more meaningful measure follows from our results.
We give the first exponential separation between quantum and classical multi-party communication complexity in the (non-interactive) one-way and simultaneous message passing settings. For every k, we demonstrate a relational communication problem between k parties that can be solved exactly by a quantum simultaneous message passing protocol of cost O(log n) and requires protocols of cost n^{c/k^2}, where c>0 is a constant, in the classical non-interactive one-way message passing model with shared randomness and bounded error. Thus our separation of corresponding communication classes is superpolynomial as long as k=o(sqrt{log n / loglog n}) and exponential for k=O(1).
According to quantum theory, the outcomes obtained by measuring an entangled state necessarily exhibit some randomness if they violate a Bell inequality. In particular, a maximal violation of the CHSH inequality guarantees that 1.23 bits of randomness are generated by the measurements. However, by performing measurements with binary outcomes on two subsystems one could in principle generate up to two bits of randomness. We show that correlations that violate arbitrarily little the CHSH inequality or states with arbitrarily little entanglement can be used to certify that close to the maximum of two bits of randomness are produced. Our results show that non-locality, entanglement, and the amount of randomness that can be certified in a Bell-type experiment are inequivalent quantities. From a practical point of view, they imply that device-independent quantum key distribution with optimal key generation rate is possible using almost-local correlations and that device-independent randomness generation with optimal rate is possible with almost-local correlations and with almost-unentangled states.
Contextuality is often referred to as a generalization of non-locality. In this work, using the hypergraph approach for contextuality we show how to associate a contextual scenario to a general k-partite non local game, and consider the reverse direction: how and when is it possible to represent a general contextuality scenario as a non local game. Using the notion of conditional contextuality, we show that it is possible to embed any contextual scenario in a two players non local game. We also discuss different equivalences of contextuality scenarios and show that the construction used in the proof is not optimal by giving a simpler bipartite non local game when the contextual scenario is a graph instead of a general hypergraph.
It is shown that the possibility of using Maxwell demon to cheating in quantum non-locality tests is prohibited by the Landauers erasure principle.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
