The nature of randomness and fundamental physical limits of secrecy

People have always been fascinated by randomness and intrigued by the fundamental question – is any outcome that appears random to us only so by virtue of our ignorance, or do there exist experiments whose outcome is inherently unpredictable to any observers, no matter how powerful or omniscient they might be?

Quantum theory, which rules out sharp predictions of measurement outcomes, does not necessarily imply that nature is truly random. Even Bell inequalities, violation of which excludes the possibility for quantum phenomena to be explained by a hidden deterministic theory, tacitly assume that experimentalists are able to make free, that is random and independent, choices during each run of their experiments. That is, in order to get randomness out, they need to put randomness in. However, it has been shown that this can at least be done with a net benefit – randomness can be amplified and expanded.

Randomness amplification has triggered a flurry of research activity, culminating in a striking result: any process that is not completely deterministic can be leveraged to generate arbitrarily long sequences of perfectly random bits. This can be achieved while placing minimal assumptions on the physical devices used to achieve this remarkable feat; in particular, while correctness of quantum mechanics is assumed, no further a priori assumption on any of the processes involved in the randomness amplification task is needed.

The main goal of the project is to understand the extent to which the most fundamental laws of physics can be used to certify the nature of any device performing an a priori un-characterized information-theoretic task, be it cryptographic (such as the generation of randomness), computational (whether a device performs a certain computation), or information-theoretic (whether a device “decouples” information from an environment, as some models of black holes predict they should).

Project leader(s):
  • Artur Ekert (University of Oxford and National University of Singapore)
STIAS fellow(s):
  • Renato Renner (ETH Zürich)
  • Miklos Santha (Université Paris Diderot - Paris 7)
  • Umesh Vazirani (University of California at Berkeley)
  • Thomas Vidick (California Institute of Technology)

Leave a Reply