The recent discussion of random number generators reminded me of
something that I've been meaning to write a note about. A couple of
years back, John Conway and Simon Kochen proved what they nicknamed
the Free Will Theorem. Its informal statement is: Given three very
simple axioms (which seem to be fundamentally part of any physical
theory even remotely consistent with relativity and quantum
mechanics), "if you have free will, then electrons do, too." This
statement of the theorem is deliberately set up to highlight one set
of philosophical consequences. A different, more straightforward
statement is: The result of a QM measurement cannot be computed by
any function of the entire pre-measurement state of the universe.
Informally, the full pre-existing state of the universe does not
determine the result of a quantum measurement.
Conway gave a series of lectures on these results that are available
free from iTunes - look at iTunes U listings for Princeton. *Well*
worth listening to. Towards the end, he makes a very interesting and
subtle point: We've viewed the unpredictability of QM measurements as
matters of randomness. People always quote Einstein's complaint that
"God doesn't play dice with the universe". Conway and Kocher's
theorem, however, show that this view is very fundamentally wrong. If
QM results were randomly determined, then we could play the same game
in our description of the universe that we play with randomizing
Turing machines: Rather than add randomness to the machine/universe,
simply provide a deterministic machine/universe with access to a pre-
computed "set of random coin tosses" that they call on whenever they
need to make a "random" choice. But if you try this approach with QM,
then Conway and Kocher will argue that the pre-determined tape can now
be considered part of "the complete pre-existing state of the
universe" - and their theorem shows that that cannot be sufficient to
predict the result of a QM measurement!
So QM's indeterminism is subtly different from randomness: It's an
unpredictable choice that "isn't made until the exact moment of
measurement". It irreducibly cannot be determined in advance. Conway
goes on to say that he doesn't *understand* what the distinction
really means - but then he says he doesn't really understand what
randomness means anyway. If John Conway feels this way, what are we
poor mortals to think?
If you think about the use of randomness in cryptography, what matters
isn't really randomness - it's exactly unpredictability. This is a
very tough to pin down: What's unpredictable to me may be predictable
to you, and unpredictability "collapses" as soon as the random value
is "known" ("measured?"). QM unpredictability as described by Conway
seems much closer to the kind of thing you really need to get crypto
results.
-- Jerry
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [email protected]
