7
$\begingroup$

I hope this question is not too vague.

For classical bit generators there is the classical statistical definition which (informally) states that a source is ideally random if its output $X_1,X_2,\ldots$ is a sequence of uniform i.i.d. bits.

There is also the alternative Kolmogorov Complexity definition in which an individual string's complexity (informally analogous to randomness) is expressed by its compressibility which is defined as the length of the shortest computer program (w.r.t. a Universal Turing Machine) which will generate the string.

Another definition relates the randomness of the string to the computational complexity of predicting it. This is used, e.g., in the Blum-Blum-Shub generator, where it can be shown that its next output bit can be predicted with probability $(1/2 + \varepsilon)$ for some $\varepsilon>0$ if and only if the RSA problem (given 2 randomly chosen n bit primes $p,q$, form their product $N=pq$ and erase $p$ and $q$; how difficult is it to obtain $p$ and $q$ from $N$?) has an efficient solution polynomial in $n.$

I think some quantum randomness generators use photonic processes to generate bits at their output. However, what is the standard (if any) definition of quantum randomness? I don't know much about quantum theory, but if a quantum system is undergoing the normal Hermitian evolution it seems to me that the output obtained from such a system will not be very random.

$\endgroup$
  • $\begingroup$ the following question/answers might also be of interest: cstheory.stackexchange.com/questions/450/… $\endgroup$ – Artem Kaznatcheev May 2 '11 at 14:35
  • $\begingroup$ @artem & @joe, Thanks a lot, your answers were very helpful (I am not sure how to put in a comment, maybe I need some repuration points, sorry to enter this as another answer). $\endgroup$ – user4943 May 2 '11 at 23:10
7
$\begingroup$

The randomness used in quantum computing comes from quantum mechanics and is postulated to be an inherent 'randomness' of nature (and one of the problems Einstein, for instance, had with QM). If you take a state like

$|+\rangle = \frac{|0\rangle + |1\rangle}{\sqrt{2}}$

and measure it in the computational basis, there is absolutely nothing you can do to predict the result (assuming our standard pictures of QM is not horribly wrong). Half the time you will measure $0$ and half the time you will measure $1$. Of course, if you measure in the Hadamard ($|+\rangle$, $|-\rangle$) basis, then your result will always be $+$.

I don't think there is a standard notion of quantum randomness, mostly because how random a state looks depends on your choice of measurement. Once you choose a particular basis to measure in, then you might as well start talking about the classical probabilities associated with the results and then you can do your standard classical tests of randomness.

Usually when someone talks about the 'quantumness' of a state, they try to capture ideas like entanglement.

$\endgroup$
  • $\begingroup$ Sorry, I was typing my answer before you posted, so I didn't see you had already answered. $\endgroup$ – Joe Fitzsimons May 2 '11 at 15:06
6
$\begingroup$

In quantum mechanics, the state of the system is given by a vector $v$ such that $v^\dagger v = 1$. For a closed system the evolution is unitary, and for a constant Hamiltonian (the total energy function for the system) is given by $U(t) = e^{-\frac{i H t}{\hbar}}$. Note that it is the Hamiltonian, rather than the time evolution operator that is Hermitian.

So this is all well and good, and we have deterministic evolution of $v$, since $v(t) = e^{-\frac{i H t}{\hbar}} v(0)$. What brings randomness into the picture is the fact that when you measure a quantum system, you do not get to learn the entire state of the system (i.e. $v$). Instead, for the simplist kind of measurements (known as projective measurements) when you make a measurement on the system, you are effectively imposing an orthonormal basis on the system. For some a given orthonormal measurement basis $\{b_i\}$, the outcome of the measurement is $b_j$ randomly with probability $|b_j^\dagger v|^2$. After such an outcome, the state of the measured system is then $b_j$, and any further information about $v$ is lost.

To give a concrete example, we can consider a qubit (a two-state quantum system) which is originally prepared in state $|0\rangle$ (this is just a notation used by physicists to denote vectors representing quantum states, in this case 0 is equivalent to the bit value 0). Next, we consider what happens when the qubit is exposed to a Hamiltonian $H=[0 ~-i; i ~~0]$ for time $t=\hbar \pi/4$. In this case, we have $v_{final} = e^{-\frac{i H t}{\hbar}} |0\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle - |1\rangle\right)$. So, up to here the evolution has been entirely deterministic. Now, the question is what happens when we choose our measurement basis as $\{|0\rangle,|1\rangle\}$. In this case, we see that the result is either 0 or 1 random with equal probability (0.5). So the resuting bit is uniformly random.

A photon passing through a beam splitter is undergoing a very similar process, though quantum optics are a little more time consuming to explain explicitly.

$\endgroup$
4
$\begingroup$

"Quantum randomness" is just the concept that measurement outcomes in quantum mechanics (and quantum computation) may not be deterministic for a given choice of measurement which you perform on the system. Of course, this actually has deep implications for physics (our understanding of radioactive decay is rooted in this concept, for instance, and is well-modelled as a Poisson process).

We have a perfectly good mathematical formalism, which Joe describes in his answer, for determining what probability distributions arise for a given measurement, having prepared a system in a particular state. However, it does not describe why it should be in a given probability distribution, beyond just the mathematical formalism of e.g. the Schrödinger equation. "Why"-answers usually amount to interpretations of quantum mechanics, which is in principle a branch of philosophy at the foundations of physics.

But for any measure of randomness that you can name — Kolmogorov complexity of measurement outcomes, for instance — you can apply that same measure to the outcomes of measurements. For instance, the example provided by Artem would be a random variable which is uniformly randomly distributed (with multiple trials giving independent results in principle).

You can view the formalism of quantum mechanics (Hilbert space, Schrödinger equation, and all) as describing a new kind of "quantum randomness", if you like, and explore topics such as quantum logic in order to describe the foundations of a new probability theory. But as far as the measurement outcomes themselves are concerned, it's perfectly valid to regard the "randomness" of quantum mechanics as being good-old 'classical' randomness, which just happens to arise through what you may regard as 'peculiar' physical processes — such as those on which the transistors in modern electronics depend.

$\endgroup$
3
$\begingroup$

I think some quantum randomness generators use photonic processes to generate bits at their output. However, what is the standard (if any) definition of quantum randomness? I don't know much about quantum theory, but if a quantum system is undergoing the normal Hermitian evolution it seems to me that the output obtained from such a system will not be very random.

Other people have already explained quantum randomness well, so I will point out that even classically, your final sentence is not quite the right.

You are of course perfectly correct that the volume of phase space is invariant under the action of the Hamiltonian. However, the result of a classical process can still be random! Intuitively, while Liouville's theorem ensures that the volume of phase space will be preserved, it cannot guarantee that this volume will not become very wiggly and stretched out through the whole phase space. Then if your measurement apparatus has any limits to its resolution, it will look like the size of the phase space is growing. (This can happen very fast, with mixing happening in time logarithmic with your measurement apparatus's resolution.) This is called "Hamiltonian chaos", or more familiarly the second law of thermodynamics.

$\endgroup$
  • $\begingroup$ thanks for that comment, it seems to me this aspect of quantum randomness is, well, as the term you use implies "chaotic", i.e., similar to classical chaos. $\endgroup$ – kodlu May 3 '11 at 11:02
  • $\begingroup$ Uhm, could you elaborate on the connection between the precision issues here, and the standard statements of the second law of thermodynamics? $\endgroup$ – Abel Molina May 4 '11 at 23:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.