Shared randomness and device-independent dimension witnessing Articles uri icon

publication date

  • January 2017


  • 1(012340)


  • 95

International Standard Serial Number (ISSN)

  • 2469-9926

Electronic International Standard Serial Number (EISSN)

  • 2469-9934


  • It has been shown that the conditional probability distributions obtained by performing measurements on an uncharacterized physical system can be used to infer its underlying dimension in a device-independent way both in the classical and the quantum setting. We analyze several aspects of the structure of the sets of probability distributions corresponding to a certain dimension, taking into account whether shared randomness is available as a resource. We first consider the so-called prepare-and-measure scenario. We show that quantumness and shared randomness are not comparable resources. That is, on the one hand there exist behaviors that require a quantum system of arbitrarily large dimension in order to be observed while they can be reproduced with a classical physical system of minimal dimension together with shared randomness. On the other hand, there exist behaviors that require exponentially larger dimensions classically than quantumly even if the former is supplemented with shared randomness. We also show that in the absence of shared randomness, the sets corresponding to a sufficiently small dimension are negligible (zero measure and nowhere dense) both classically and quantumly. This is in sharp contrast to the situation in which this resource is available, and it explains the exceptional robustness of dimension witnesses in the setting in which devices can be taken to be uncorrelated. We finally consider the Bell scenario in the absence of shared randomness, and we prove some nonconvexity and negligibility properties of these sets for sufficiently small dimensions. This shows again the enormous difference induced by the availability (or lack thereof) of this resource.


  • communication; complexity exponential; separation; quantum; nonlocality