Archive for June 2010
A quickie post this time:
I mentioned a while back that the ACM’s monthly magazine Communications had taken a radical turn for the better.
Recently they had one of the most interesting articles I’ve yet read in any magazine, being a straightforward description of what quantum information is like to compute with.
The core idea is that a classical system is an N x M function, taking a state of size O(N) and converting it into a (potentially smaller) state of size M. So the state evolution matrix of a classical system is an N x M matrix.
Quantum systems, on the other hand, are reversible. This means that information is not lost in a quantum system; it is just transformed. So the state evolution matrix of a quantum system is an N x N matrix, and moreover a unitary matrix that preserves magnitude (though not distribution). Hence quantum computations are fundamentally affected by interference patterns; they gave an example of how a quantum random walk winds up with a very different distribution from a classical random walk.
It seems that the problems quantum computers are best at involve symmetries. Since a quantum computer is a very efficient way of transforming a configuration, it makes intuitive sense that it would therefore be a fast way to determine symmetry. Factoring large prime numbers is an example of finding such a symmetry (corresponding to the factorization itself).
It’s a fascinating article and explains all this much better than I am. Reversible computing is one of those Holy Grails that I truly hope arrives some year in a fashion I am capable of programming. It could be the real answer to energy issues in computing. On the other hand, it could cost more energy to create a quantum system with the right unitary matrix in the first place than you get back when reversibly running it. I very much hope we’ll find out in the next two or three decades.