$100,000 Prize: Prove Quantum Computers Impossible

mikejuk writes "Quantum computing is currently a major area of research — but is this all a waste of effort? Now Scott Aaronson, a well-known MIT computer scientist, has offered a prize of $100,000 for any proof that quantum computers are impossible: 'I'm now offering a US$100,000 award for a demonstration, convincing to me, that scalable quantum computing is impossible in the physical world.' Notice the two important conditions — 'physical world' and 'scalable.' The proof doesn't have to rule out tiny 'toy' quantum computers, only those that could do any useful work."

Re:D-Wave sold a commercial Quantum computer in 20

[Ken_g6]

D-Wave uses quantum annealing [wikipedia.org]. This works for minimization problems, although it's unclear whether it's better than "simulated annealing". This does not work for problems like factoring integers, which "real" quantum computers can do.

gazillion dollar counter prize

[damn_registrars]

Prove there is a god

... prove there isn't.

I'm willing to bet all I own that neither will ever be successfully claimed. You need faith to accept either to be met.

Re:You can't prove a negative

[Anonymous Coward]

'You can't prove a negative'

If that were true, it would be unprovable. But, anyway, it's not true. Some of the most important (and proven) results in 20th century mathematics were negative: Goedel's proof that arithmetic is INcomplete, Church's proof that polyadic first-order logic is UNdecidable, Tarski's proof that truth is UNdefinable, Cohen's proof that the continuum hypothesis is UNprovable in ZFC, etc.

Re:Sorry, what?

[quantaman]

A similar question could have been asked of perpetual motion machines, and in that case there would have been a payout, which I think is partially his point

The impetus for this prize was a post on Dick Lipton’s blog, entitled “Perpetual Motion of the 21st Century?” (See also this followup post.) [...] Anyway, in the comments section of the post, I pointed out that a refutation of scalable QC would require, not merely poking this or that hole in the Fault-Tolerance Theorem, but the construction of a dramatically-new, classically-efficiently-simulable picture of physical reality: something I don’t expect but would welcome as the scientific thrill of my life.

I think he's saying that while a general quantum computer might be a very long way off, the underlying theory that allows such a thing to exist is on very solid ground (which is why he's putting up the money). Of course this prize might still cost him since if the news of the prize goes viral he's going to spend the next decade getting spammed by kooks.

Re:Sorry, what?

[LargeMythicalReptile]

There's some needed context.

Aaronson himself works on quantum complexity theory. Much of his work deals with quantum computers (at a conceptual level--what is and isn't possible). Yet there are some people who reject the idea the quantum computers can scale to "useful" sizes--including some very smart people like Leonid Levin [bu.edu] (of Cook-Levin Theorem fame)--and some of them send him email, questions, comments on his blog, etc. saying so. These people are essentially asserting that Aaronson's career is rooted in things that can't exist. Thus, Aaronson essentially said "prove it."

It's true that proving such a statement would be very difficult, and you raise some good points as to why. But the context is that Aaronson gets mail and questions all the time from people who simply assert that scalable QC is impossible, and he's challenging them to be more formal about it.

He also mentions, in fairness, that if he does have to pay out, he'd consider it an honor, because it would be a great scientific advance.

Re:Like the cat

[PaladinAlpha]

This is a gross misunderstanding of the Schrodinger's cat thought experiment, and something of a fallacious presentation of it.

I don't think there was ever any doubt that a cat locked in a box for a sufficient length of time would expire. That is neither in doubt nor interesting.

The formulation deals with the status of a cat in a box present with some measuring apparatus capable of detecting decay of some isotope, linked to a sealed capsule of some poison, in a sealed container with a cat. Supposing the isotope has a roughly 50% chance of decaying in the next five minutes, and iff it decays the poison is released (killing the cat), after five minutes is the cat alive or dead?

The "collapse the waveform pseudo-science b***s***" here is simply translating the simultaneous probabilistic states into a single actual one. The reason this is relevant is in quantum mechanics there are real, measurable effects that occur as a result of the probabilistic waveform that differ from the effects of the collapsed state -- once you know whether the cat is alive or dead, in other words, you have a fundamentally different system than before it was observed.

Re:I think quantum computers do not scale

[ImprovOmega]

It's not logarithmic, it's sqrt(). For a given number of bits (n) adding 1 extra bit requires n additional entanglements. Thus for n-qubits you must have n(n-1)/2 = (n^2 - n) / 2 entanglements. Doubling that increases the difficulty quadratically instead of linearly, but it's not the exponential growth in difficulty that you're implying.