Uncertainity Principle(s)

Most people know a formulation of the uncertainity principle in quantum mechanics (by Heisenberg), where it basically gives a bound (in terms of the standard deviations of ~) for simultaneous measurements of complementary properties (i.e. measurement operators with non-negative commutator).

There are a number of other places where the principce turns up. It comes from an application of the cauchy schwarz inequality to the fourier transformation. Here's a set of (german) slides from a lecture. Recently Terry Tao posted on a a formulation of the principle due to Mongomery, which has applications in analytic number theory.

Random Numbers and Certified Randomness

A rather recent edition of the ACM TechNews contained a short report/link on a German team which developed a hardware random number generator [1], that

uses an extra layer of randomness by making a computer memory element, a flip-flop, twitch randomly between its two states 1 or 0. Immediately prior to the switch, the flip-flop is in a "metastable state" where its behaviour cannot be predicted. At the end of the metastable state, the contents of the memory are purely random.

Whereas this device gives me more security, it does not solve the problem of someone sending me supposedly "random numbers" which he might have prepared in advance to even pass statistical tests. A neat solution is provided by quantum mechanics which allows to check randomness of numbers via the violation of the Bell inequality [2] using entangled states.


[1] "A meta-level true random number generator" in Int. J. Critical Computer-Based Systems, 2010, 1, 267-279

[2] Random Numbers Certified by Bell's Theorem

Some results in quantum computing

Just some points to (rather) recent results in complexity theory with regard to quantum computing:

• Quantum Interative Proofs equals Polynomial Space class: QIP = PSPACE
  
• On the relation of the BQP class to the PH class; furthermore a separating decision problem would follow from the Generalized Linial-Nisan Conjecture: BQP vs PH

QML

QML is a functional language for quantum computation on finite types.
See http://sneezy.cs.nott.ac.uk/QML/index.html for the project homepage. Check the phd-thesis for extensive information on it: http://sneezy.cs.nott.ac.uk/qml/compiler