Received 26 November 2015; accepted 19 March 2016; published 22 March 2016
We are ultimately able to make choices, independently of the world that surrounds us. This is free will, a belief which is so deeply rooted in our culture, that we generally take it for granted without even noticing. The assumption that one can make an independent decision is, however, crucial in many logical reasonings and algorithms.
Making a decision is a physical process. Being able to make a random choice implies that there is a physical setup that provides random outcomes, which can be represented―without loss of generality―as numbers. Independent random choice implies the existence of a physical setup that provides random numbers that are independent of the rest of the universe.
It is already known that one can expand an initial random number thanks to quantum algorithms known as Private Randomness Expansion  -  , whose aim is to increase (in entropy) randomness using untrusted devices. Private Randomness Expansion does, however, not deal with the generation of the initial random number, as it is proved  that one cannot generate random number from scratch with untrusted devices, but can only expand an initial random number.
The scope of this paper is different: we study the feasibility of actual generation of random numbers using trusted devices, which does not assume the presence of initial random numbers serving as a seed. Based on the law of quantum mechanics, and the fact that the state of the overall system including the setup and its environment can never be known, we prove that such generation cannot be guaranteed to be truly independent of the rest of the universe.
The paper is organized as follows: we start by considering a simple setup that is usually believed to generate independent random numbers. We show, however, that such setup can be entangled with its environment prior to the experiment, and as such, the random numbers returned by the setup can never be guaranteed in theory to be independent of the environment.
We show that this result can be generalized to any physical setup that could be conceived to generate random numbers. Independence of random number generation cannot be guaranteed, and we discuss the theoretical consequences of such limitation.
2. Case Study
Throughout this paper, our question will be the following: can we conceive a source of random binary number that is guaranteed to be independent of the rest of the universe?
The usual setup that comes to mind when one wants a random source of binary number is the following. Consider a qubit and let be its canonical basis. If we had a certified way of preparing the qubit in the state
where, then we could measure such qubit in the basis. If the state is observed
in the state then we say that the setup generated the random number 0. If the state is observed in the state then the random number is 1. The process is guaranteed to generate a random bit that is independent of the rest of the universe.
But how do we prepare the state in practice? The setup that is usually employed works as follows: The measured qubit is prepared in some state, and is first observed in the basis. We know that the measured qubit is now in either the state or state, information which must be explicitly kept (otherwise the effect of the measurement can be cancelled, as shown in the Quantum Eraser experiment  ). This state is then measured in the basis.
The whole setup can be represented as in Figure 1: The qubit P represents the outcome of the first measurement (P stands for “projection”), whereby the first qubit is measured in the state or the state. We look at the value returned from the measurement of M, given the outcome of the measurement of P.
Note that although we find it natural to describe the measurement of P as being prior to the measurement of M, it actually does not matter whether M is measured before or after P.
With such a setup, we generally assume that measurement of M leads to a random binary outcome, which is completely independent of the rest of the universe. This belief is natural if one accepts that the initial state of the setup is known, or at least, that the initial state of the setup is not entangled with the rest of the universe.
However, in theory, the initial quantum state of a given experimental setup is never known. One can choose arbitrarily the basis for the Hilbert space describing the system under study, but one cannot guarantee that the system under study is not entangled with the rest of the universe. Said differently, there is no theoretical guarantee that a physical system under study had not been entangled at an earlier point with another part of the universe.
Suppose for instance that the setup above was entangled initially with a third qubit, which is part of the rest of the universe and is not known to us. Let’s denote this third qubit E (Figure 2).
Suppose now that the initial state of the resulting system is:
then, calculation shows that the final state of the system is, after going through the experimental setup:
which is identical to the initial state and which can be rewritten as:
Figure 1. An usual setup for random bit generation.
Figure 2. The same setup taking into account the environment.
In other words, whichever result is observed for the projection qubit P, the measured qubit M and the environment qubit E are perfectly entangled. Measurement outcome at M and E will be perfectly correlated if we use the same measurement basis for M and E.
We see that the proposed setup, which is usually used as a random and independent source of random number, cannot actually be guaranteed to be independent of the rest of the universe.
3. General Case
We saw in the section above that a setup that was believed to generate independent random choices could actually not be guaranteed to be independent.
Our next question is: can any setup in general produce random numbers that are guaranteed to be independent of the rest of the universe?
However complex such a setup can be, it can be described as follows: the setup is a physical system, made of two subcomponents M and P, that interact and evolve possibly in a most general and complex manner. The subcomponents M and P are then observed. We denote by U the unitary map describing the evolution of M and P. The outcomes of these observations are denoted m and p respectively. The generation of the random number is deemed successful if p is part of a pre-agreed set S corresponding to “successful” outcomes. In such a case, the random number is given by a pre-agreed deterministic function of m and p, f(m, p). The setup is represented in Figure 3.
Now, whatever the size of the setup, we assume that it is sufficiently small compared to the entire universe. Consequently we can define a quantum system E that is part of the rest of the universe, described by a Hilbert space of the same dimensionality as M. We denote by the unitary operator that applies U on the system and leaves E unchanged (Figure 4).
Consider the following state for the combined physical system made of M, P and E:
where is a state for P that leads to a successful fixed outcome, and and are bases for M and E, respectively. The number N is a normalization factor.
By construction, if the initial state of the entire system is in the state then the experiment returns the state in which M and E are perfectly entangled, and with which the measurement at P leads to a successful result. Measurement of E leads to the same outcome as the measurement of M, and the outcome f(m, p) can be completely deduced from the measurement outcome of E. Therefore, there exists at least one initial state with which the proposed setup does not return independent random numbers.
Figure 3. General setup for random number generation.
Figure 4. General setup taking into account environment.
As such no physical setup can guarantee generation of independent random numbers. We have demonstrated the following:
Property 1 No generation of random choices can be guaranteed to be independent of the remaining part of the universe.
We have proven that―at least in theory―no random choice can be guaranteed to be independent of the rest of the universe. This is mainly due to the fact that, if we consider the state of any physical setup together with its environment, then such state is unknown. One could argue that, statistically, no relevant impact can be expected from these entanglements that are only theoretical possibilities. One could also argue that the likelihood that the overall state of the universe is such that it precisely introduces dependence between the generated random number and its environment is dim. However, we cannot rely on statistical argument when independence of random choices is itself under question.
The fact that we cannot guarantee independence of random choices has many consequences, few of them are discussed below.
4.1. On the Positive-Operator Valued Measure
Positive-Operator Valued Measure  is considered to be the most general formulation of a measurement in quantum mechanics. It allows the introduction of probability weights between different projective measurements, as if it was possible to choose randomly between these projective measurements. However, we have just seen that the random choice between these different projective measurements cannot be guaranteed to be independent of the rest of the universe. Therefore, the mathematical description using POVM is misleading, in the sense that it introduces the false belief that independent random choice is possible. Our view in this paper is that the most fundamental description of measurement remains the law based on projection of quantum states onto the measurement basis.
4.2. On Bell’s Theorem and Its Interpretation
The experimental violation of Bell’s inequality  is generally considered as a confirmation that laws of nature cannot be described by local hidden variables. However, existence of local hidden variable is not the only assumption which is necessary in the derivation of Bells inequality   . In particular, Bell assumes that random and independent decisions can be taken at the two distant locations. We suggest in this paper that, what could be forbidden by the violation of the Bell’s inequality is actually not the existence of local hidden variable, but rather the true independence between the observed system and the way that system is observed. In other words, violation of Bell’s inequality could be interpreted as the demonstration that one cannot make decisions that are fully independent of the environment.
4.3. On Algorithms Relying on the Independence of Random Choices
Many algorithms, such as the Monte Carlo integration, error-correction and cryptography to name a few, rely on the ability to generate random numbers that are independent. The theoretical possibility that some remaining part of the universe may be correlated to these random numbers may, or may not be relevant. In any case, for theoretical completeness, one should not take for granted that sources of random choices are truly independent of the rest of the universe. Impact of potential dependence of such sources with the rest of the universe should be analyzed.
We generally assume that one can take a random decision (using if necessary a device as described in the case study above), and that such decision can be taken independently of all the rest of the universe. This is free will, the common belief that one is always able to make a decision independently of one’s environment.
We have shown in this paper that no random choice can be guaranteed to be independent of the rest of the universe. For practical purposes, the theoretical possibility that one part of the universe may be correlated with our experimental setup may have little importance. This being said, if we believe that our current universe expands from a single common state, then we cannot dismiss the possibility that any experimental setup under study is entangled with another observable part of the universe.
The author thanks Norbert Lütkenhaus for his comments on the initial version of this paper and for pointing to the existing work on Private Randomness Expansion.
 Colbeck, R. and Kent, A. (2011) Private Randomness Expansion with Untrusted Devices. Journal of Physics A: Mathematical and Theoretical, 44, 095305.
 Pironio, S., Acín, A., Massar, S., Boyer de la Giroday, A., Matsukevich, D.N., Maunz, P., Olmschenk, S., Hayes, D., Luo, L., Manning, T.A. and Monroe, C. (2010) Random Numbers Certified by Bell’s Theorem. Nature, 464, 1021-1024.
 Kim, Y.H., Yu, R., Kulik, S.P., Shih, Y. and Scully, M.O. (2000) Delayed “Choice” Quantum Eraser. Physical Review Letters, 84, 1.
 Aspect, A., Grangier, P. and Roger, G. (1982) Experimental Realization of Einstein-Podolsky-Rosen-Bohm Gedankenexperiment: A New Violation of Bell’s Inequalities. Physical Review Letters, 49, 91.