robjsoftware.info

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.