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) ..