Randomness is not something we usually look upon as a vital natural resource, to be carefully conserved lest our grandchildren run short of it. On the contrary, as a close relative of chaos, randomness seems to be all too abundant and everpresent. Everyone has a closet or a file drawer that offers an inexhaustible supply of disorder. Entropy—another cousin of randomness—even has a law of nature saying it can only increase. And, anyway, even if we were somehow to use up all the world’s randomness, who would lament the loss? Fretting about a dearth of randomness seems like worrying that humanity might use up its last reserves of ignorance. Nevertheless, there is a case to be made for the proposition that high-quality randomness is a valuable commodity. Many events and processes in the modern world depend on a steady supply of the stuff. Furthermore, we don’t know how to manufacture randomness; we can only mine it from those regions of the universe that have the richest deposits, or else farm it from seeds gathered in the natural world. So, even if we have not yet reached the point of clear-cutting the last proud acre of old-growth randomness, maybe it’s not too early to consider the question of longterm supply.
Randomness is not something we usually look upon as a vital natural resource, to be carefully conserved lest our grandchildren run short of it. On the contrary, as a close relative of chaos, randomness seems to be all too abundant and everpresent. Everyone has a closet or a file drawer that offers an inexhaustible supply of disorder. Entropy—another cousin of randomness—even has a law of nature saying it can only increase. And, anyway, even if we were somehow to use up all the world’s randomness, who would lament the loss? Fretting about a dearth of randomness seems like worrying that humanity might use up its last reserves of ignorance. Nevertheless, there is a case to be made for the proposition that high-quality randomness is a valuable commodity. Many events and processes in the modern world depend on a steady supply of the stuff. Furthermore, we don’t know how to manufacture randomness; we can only mine it from those regions of the universe that have the richest deposits, or else farm it from seeds gathered in the natural world. So, even if we have not yet reached the point of clear-cutting the last proud acre of old-growth randomness, maybe it’s not too early to consider the question of longterm supply.
In the last two chapters, we talked about computational complexity up till the early 1970s. Here, we'll add a new ingredient to our already simmering stew – something that was thrown in around the mid-1970s, and that now pervades complexity to such an extent that it's hard to imagine doing anything without it. This new ingredient is randomness . Certainly, if you want to study quantum computing, then you first have to understand randomized computing. I mean, quantum amplitudes only become interesting when they exhibit some behavior that classical probabilities don't : contextuality, interference, entanglement (as opposed to correlation), etc. So we can't even begin to discuss quantum mechanics without first knowing what it is that we're comparing against. Alright, so what is randomness? Well, that’s a profound philosophical question, but I’m a simpleminded person. So, you’ve got some probability p , which is a real number in the unit interval [0, 1]. That’s randomness. But wasn’t it a big achievement when Kolmogorov put probability on an axiomatic basis in the 1930s? Yes, it was! But in this chapter, we’ll only care about probability distributions over finitely many events, so all the subtle questions of integrability, measurability, and so on won’t arise. In my view, probability theory is yet another example where mathematicians immediately go to infinite-dimensional spaces, in order to solve the problem of having a nontrivial problem to solve! And that’s fine – whatever floats your boat. I’m not criticizing that. But in theoretical computer science, we’ve already got our hands full with 2n choices. We need 2ℵ0 choices like we need a hole in the head.
The topic of this session is “physical randomness”. It might be doubted whether such a subject exists, for definitions of randomness have hitherto almost all been mathematical in nature. The only exceptions of which I am aware are the preceding paper by Benioff and a paper by Wesley Salmon. These attempts to inject some empirical content into randomness are highly desirable. But anyone attempting to formulate a physically based definition of randomness should at some point make clear what the connection is (if any) with a more traditional notion of disorder - that of indeterminism. Repeated reference to quantum mechanical examples whenever physical randomness is discussed indicates that a primary motivation for considering physical randomness to be important is because of the current belief that data sequences associated with quantum mechanical experiments are irreducibly random. (As an indication of this, in any situation in which physical randomness is discussed, translate the remarks about quantum phenomena into remarks about coin tossing, and they will lose much of their interest.)
Consider the following: A scientist studying atoms, is a group of atoms studying themselves. A strange way of looking at reality. To understand, we have to travel through the world of the infinitesimal, governed by rules and laws, different from the ones we know from our classical world. We have to enter the world of information. Max Born created the measurement problem with his statistical interpretation of the quantum mechanical wave-function: the strange connection between the collapse of a quantum mechanical wavefunction and measurement, observation, interaction with the environment, with projection into a single concrete reality in a classical world. Where a measurement or observation creates the relevant past history, John Wheeler’s eye. The universe urges for an increase in entropy and information processing. This increase makes the universe a bustling place where life such as ours can arise. The biochemistry of all life we know, has an essential basic property as the sole islands in the known universe succeeding in keeping its own entropy low: life is capable of violating the second law of thermodynamics. Life manages to prevent equally distribution of matter and energy in which case all biochemical processes stop and life ends. Growing old and dying, for every solely living thing on Earth, means being not able anymore to keep its entropy low, leading to a malfunction in the biochemical machinery, failing fundamental processes, wear and ultimately death. Keeping its entropy low, is a basic property of life. Entropy describes a system on a microscopic level and is closely related to information, the Shannon entropy, combined to as Infotropy. They are 2 parts of the same coin, closely connected with the statistics governing the rules of the universe. An average human body contains about 7 octillion (a 7 with 27 zeros) atoms and they all ‘know’ exactly what to do and how to interact. Hidden webs of information guide the atoms and molecules in their biochemical reactions, while obeying the strange laws of quantum physics: every chemical and biochemical reaction depends on the interplay of electrons. This all is guided by communication between and information streams and exchange in the subsystems of the cellular machinery. The universe produced brains, so why can’t the universe itself be a giant super brain. All we call real is made up out of things which cannot be considered as real. Our senses are biochemical measuring instruments in our interaction with the environment. They don’t serve to reveal us reality but to help us to survive. Their information is interpreted in the brain as a ‘reality vital to life.’ The brain holds a mask in front of reality behind which the real world, the world of information and quanta lies concealed. The qubits, the quantum information that makes up the universe, do not signify anything concrete, but are transformed by biochemical projection and neural interpretation into apparent reality, as electrical circuits and software do in creating a 3D virtual reality. The deepest layer of reality consists out of information. Information is the building block of the universe, although a qubit is not a physical object but contains information about the physical object. Information is real and has to obey physical laws. Consciousness, emerging from the exchange of information via chemical and electrical signals, allowing life to have a notion or awareness of its environment, is the appearance of a world trough biochemical information projection and neural interpretation. The brain, the most complex piece of matter in the known universe, creates reality. Which brings us to the question: How can we possibly know what there is out there, if we ourselves, are locked up in complete darkness in a small box. Graphical Abstract: Saldesign.
Is it possible to emulate sampling from an arbitrary efficiently-samplable distribution using an efficient deterministic procedure which is initially fed with a short random seed and increments a counter after each query? Yes, under minimal cryptographic assumptions (the existence of one-way functions) as shown by a sequence of celebrated results in the 80s. Equivalently, one can view this problem as the goal to compress a large number of (seemingly) random samples into a short random seed. But what happens when multiple parties want, given short correlated random seeds distributed in a one-time initialization step, to deterministically and non-interactively obtain correlated samples that cannot be distinguished (even by a subset of the participants themselves) from random samples from a joint distribution? In other words, can cryptography help us compress (seemingly) random correlated samples? Our knowledge of this natural generalization of the problem is considerably more limited, and there is much more that we don't know than we know! Nevertheless, many special cases of this question have been explored in recent (and not so recent) works, motivated in part by numerous applications to other cryptographic tasks. In this article, I provide an introductory exposition of the topic, recasting a number of results originally introduced using various formalisms, under the lens of compressed samplers for multiple parties.
Randomness is crucial for a variety of applications, ranging from gambling to computer simulations, and from cryptography to statistics. However, many of the currently used methods for generating randomness do not meet the criteria that are necessary for these applications to work properly and safely. A common problem is that a sequence of numbers may look random but nevertheless not be truly random. In fact, the sequence may pass all standard statistical tests and yet be perfectly predictable. This renders it useless for many applications. For example, in cryptography, the predictability of a randomly" chosen password is obviously undesirable. Here, we review a recently developed approach to generating true | and hence unpredictable | randomness.
If the concept of “free will” is reduced to that of “choice” all physical world share the latter quality. Anyway the “free will” can be distinguished from the “choice”: The “free will” involves implicitly certain preliminary goal, and the choice is only the mean, by which it can be achieved or not by the one who determines the goal. Thus, for example, an electron has always a choice but not free will unlike a human possessing both. Consequently, and paradoxically, the determinism of classical physics is more subjective and more anthropomorphic than the indeterminism of quantum mechanics for the former presupposes certain deterministic goal implicitly following the model of human freewill behavior.The choice is usually linked to very complicated systems such as human brain or society and even often associated with consciousness. In its background, the material world is deterministic and absolutely devoid of choice. However, quantum mechanics introduces the choice in the fundament of physical world, in the only way, in which it can exist: All exists in the “phase transition” of the present between the uncertain future and the well-ordered past. Thus the present is forced to choose in order to be able to transform the coherent state of future into the well-ordering of past. The concept of choice as if suggests that there is one who chooses. However quantum mechanics involves a generalized case of choice, which can be called “subjectless”: There is certain choice, which originates from the transition of the future into the past. Thus that kind of choice is shared of all existing and does not need any subject: It can be considered as a low of nature.There are a few theorems in quantum mechanics directly relevant to the topic: two of them are called “free will theorems” by their authors, Conway and Kochen, and according to them: “Do we really have free will, or, as a few determined folk maintain, is it all an illusion? We don’t know, but will prove in this paper that if indeed there exist any experimenters with a modicum of free will, then elementary particles must have their own share of this valuable commodity” “The import of the free will theorem is that it is not only current quantum theory, but the world itself that is non-deterministic, so that no future theory can return us to a clockwork universe”.Those theorems can be considered as a continuation of the so-called theorems about the absence of “hidden variables” in quantum mechanics.