Older blog entries for TheBean (starting at number 1)

harrisj wrote:

I did know that quantum computers would do factoring in P. How do they work against other NP-complete problems (like Hamiltonians)? Also, is there a class of problems which quantum computers can not do in polynomial time (eg, how well do they do against EXPTIME)?

An overview (by The Man himself, Peter Shor) of some of QC's known capabilities can be found here.

To quote:

So far, we have only discovered a few techniques which can produce speed up versus classical algorithms. It is not clear yet whether the reason for this is that we do not have enough intuition to discover more techniques, or that there are only a few problems for which quantum computers can significantly speed up the solution.

I think "the reason" lies not in our lack of intuition .. but in the phrasing of the problem. I think that a fundamental barrier to further advances in quantum computing lies in our current notations and representations. Yes, quantum computing is radical and requires a new and different view of the world .. but not so radical that one can never hope to grasp it.

How many of you are familiar with the I/V characteristics of a CMOS transistor? Yet you can program a computer that relies fundamentally on this technology? How can that be? The answer lies in abstraction! But in the current state of quantum computing, that is right where you are .. dealing with the I/V curve of Hilbert spaces and matrix algebra. This might be OK for physicists and the truly great minds of our time .. but wouldn't it be better if even average minds could somehow contribute to solving the problem?

What if there were a different way of looking at the problem? One that was closer to home for computer scientists and engineers? The result would be many more great minds applying tried and true techniques to new and challenging problems in a new domain. That is why I am developing QDD.

Let me leave you with a quick challenge problem:

Let A and B be Boolean variables and W,X,Y, and Z be the
following Boolean expressions in A and B:

 W == FALSE;
X == A;
Y == B;
Z == !(A & B);

 Compute the value of W as a result of the following sequence of
operations (operators are as they appear in C++):

 X ^= !Z;
Y ^= !Z;

 W ^= X & Y;
W ^= TRUE;

 

If you can solve this problem, I claim that you have a good start on your contribution to the advancement of quantum computing. (Extra credit if you can characterize the values of the expressions for X and Y :) Answer and explainations in my next diary entry (which, at this rate, should be sometime around Christmas) ..

I am in the middle of developing a new quantum algorithm and testing/debugging it using QDD and QCL.

I once had a discussion with a friend in which we concluded that the best tool developers are those who use their own tools. Perhaps this sounds obvious, but it isn't always so. I remember a conversation I was involved in with an individual developing software to assist in the software development process. (are you with me? :) The individual was asked if they used their own software to develop their software. They replied that their own software was too complex for their own tool. Hmm ..

Anyway, it has been interesting using QDD in the development process .. you really begin to appreciate what your software needs once you start to use it. Perhaps this is what makes "free" software so good .. the people who write it are writing it to use it. Perhaps this is also what makes free software documentation so poor .. you already know how it works, why write it down? (I am guilty of this in spades).

QDD is pretty good (from a quantum computing standpoint) at the one task it was originally designed to perform .. quantum factoring using Shor's algorithm .. and I never have claimed that QDD was an accurate model of quantum physics. However, I am finding that I do need it to be better and more accurate than it currently is in order to be useful for developing/debugging quantum algorithms.

So .. back to work!