First fully end-to-end quantum computer is a reality UPDATED

[silverpig]

Originally posted by: f95toli

Originally posted by: silverpig

Originally posted by: verndewd
Yup ;if you can afford the liquid nitrogen to cool it and program the cpu to run windows ,you are in like flynn.

LN2 is cheaper than bottled water...

Yes, but LHe4 is not. I think it is somewhat cheaper in the US than here in Europe but a dilution fridge still uses about 200-300 liters of it per week (it depends on the model, wiring etc) meaning the total running costs of a fridge is still probably something in the range $1000-2000 per week.

LN2 is unfortunately nowhere near cold enough to cool down a solid state quantum computer.

It's about $10 a liter here. LHe3 is another story though IIRC. I was mainly commenting on the LN2 cost.

 

[nortexoid]

If this is physically possible, it would be amazing. It embodies what is known in computability theory as nondeterministic computation. It would allow the relatively fast computation of polynomial time problems and perhaps manageable (time-wise) computation of non-deterministic polynomial time problems.

Suppose P(x1,...,xn) is a decidable predicate in n free variables. Given current polynomial time computation, if the complexity of solving P is super-polynomial, it could take longer than is physically feasible to determine for given values of x1,...,xn whether P(x1,...,xn) is true or false. For a concrete example, take P(x1,...,xn) to be the predicate "x1,...,xn-1 is a sequence of formulas of a first-order language that is a deduction in the calculus T of xn". Actually we needn't even get as complex as first-order languages and its corresponding deducibility relation. It is known that the complexity of deducibility for propositional logic is exponential time. (Specifially, there are 2*m computations for a given problem in the class, where m = max(x1,...,xn) = the formula xi with the greatest (not necessarily unique, though I use the definite article) number of distinct free variables. This would give rise to a new generation of theorem provers capable of proving non-trivial theorems in P-time!

 

[sdifox]

Flee, Flee, NP Completeness..... The nightmares are back...

 

[Blouge]

>Suppose P(x1,...,xn) is a decidable predicate in n free variables

I find your post a bit confusing. To me, "decidable" means you can make up your mind on whether the particular predicate is true or false for particular values x1...xn. Is this what you meant? Also, I'm not sure how to "solve" a predicate.

Perhaps you simply meant that the statement "P(x1,...,xn)=0" has a solution?

If so, then you've tried to sweep a big problem under the rug: in practice you usually don't know if there is a solution. So you try to solve P AND q = 0, where q is another free variable. This is guaranteed to have a solution no matter what, with q = 0, and only maybe with q=1. If you now try to measure q using the quantum computer, you will find that it is zero almost all of the time, because q=0 appears in so many combinations, 2^N of them in fact! Thus you need to make roughly 2^N measurements until you encounter q=1 and then you found a solution to your original problem. If you never find q=1 don't give up, maybe try 100^N measurements and you'll get your answer, honest!

Again, how is this better than a conventional computer?? What am I missing???

I assume you can't FORCE the value of q=1 to appear. (What if there is no solution P=0? Would your quantum computer just blow up?)

 

[nortexoid]

Originally posted by: Blouge
>Suppose P(x1,...,xn) is a decidable predicate in n free variables

I find your post a bit confusing. To me, "decidable" means you can make up your mind on whether the particular predicate is true or false for particular values x1...xn. Is this what you meant? Also, I'm not sure how to "solve" a predicate.

Perhaps you simply meant that the statement "P(x1,...,xn)=0" has a solution?

'Decidable' means that its characteristic function is total; that is, for any given sequence of values as argument, there is an effective procedure for determining whether *or not* that sequence satisfies the predicate. That is what I said when I said "...it could take longer than is physically feasible to determine for given values of x1,...,xn whether P(x1,...,xn) is true or false" with respect to decidability.

To "solve" for P means to provide an algorithm (effective procedure) that determines for any given sequence of values whether or not that sequence satisfies the predicate. The existence of such a solution is known as a solution to the decision problem for P. The decision problem for a predicate is a class of questions of the form "Is P(x1,...,xn) true for the values x1=a1,...,xn=an?", where each ai is a member of the elements of the domain of a given structure (possibly of the intended interpretation of P).

The statement 'P(x1,..,xn)=0' is not well-formed when P is a predicate and '=' denotes a relation between individuals, not classes of n-tuples of individuals. So no, that's not what I meant. You seem to be thinking in terms of the characteristic function of P which is defined as:

f(x1,...,xn) = {1 if P(x1,...,xn) is true; 0 otherwise.

But that is not called the 'decision problem' for P. It's the computation problem for its corresponding characteristic function.

Originally posted by: Blouge
If so, then you've tried to sweep a big problem under the rug: in practice you usually don't know if there is a solution.

That is why I restricted attention to *decidable* predicates, as I stated in my original post. Now given the class of decidable predicates, such as the deducibility relation for propositional logic (as I already mentioned), quantum computing would allow solving for very complex sequences of formulas in faster than exponential time. Suppose you have a sequence of formulas x1,...xn-1 and you want to find out whether xn is deducible from them. Moreover, suppose max(x1,..,xn)=m, so that there are 2^m rows of a truth-table to compute. If m is even relatively small, it could forever to compute. But what if we could compute every 2^m permutation of the value of the variables simultaneously?

 

[Molondo]

So whos going? Better take lots of pictures and bring back some souveniers!

 

[Cattlegod]

Anyone have a link to a video feed from the demonstration or some other type of 3rd party review?

 

[silverpig]

I'm going tomorrow. It's at 4pm PST. I'll try to bring a camera, but my guess is there's not going to be anything interesting to see in terms of hardware as the QC itself is in a lab a few km away.

 

[pm]

I saw this as a top news item on Yahoo (who'd have thought Yahoo news readers would recognize a quantum computer if they tripped over it).

http://news.yahoo.com/s/ap/20070214/ap_on_hi_te/techbit_quantum_quandary

Quantum computing is such an elusive goal that even the company claiming to have the "world's first commercial quantum computer" acknowledged it isn't entirely sure the machine is performing true quantum calculations. And independent quantum computing researchers said they are dubious of some of the claims made by D-Wave Systems Inc. because the privately held Canadian company has not yet submitted its findings for peer review, a standard step for gaining acceptance in scientific circles.

There's also a good article at The Register. Note that it's two pages long (I almost missed this) - and there's video clips on the second page.
http://www.theregister.co.uk/2007/02/13/dwave_quantum/