Quantum computing device hints at powerful future

http://www.bbc.co.uk/news/science-environment-12811199

60 35 15 years ago

bbc.co.uk

Does anyone have any info as to how the art of programming might change with quantum technology ?

Devilboy• 15 years ago

I'm no expert on the topic but I guess the real nuts and bolts will be abstracted away from the developers. One example is a new LIKE implementation in your SQL database that uses a quantum algorithm for approximate search hits (from a DWave paper iirc)

sunkencity• 15 years ago

One of the major changes is that you cannot inspect the process of computation until it's done, because looking at the cubits collapses them into bits..

So no debuggers/stepping I assume :)

Estragon7• 15 years ago

That's getting a bit ahead of where they're at. To the best of my knowledge, the fundamental assumption behind the QC paradigm, the Copenhagen Interpretation, has never really been tested.[1] It is possible that a device like this will constitute the definitive test. The question will be whether such a system can actually perform a calculation across a superposition of states. In the systems I am aware of where such a calculation has been claimed, what actually happened was that a large number of atoms were manipulated simultaneously, and the "superposition" was potentially across the specific states in those individual atoms.

My own opinion is that the QC scenario is a reductio ad absurdum for the Copenhagen Interpretation, and that when a true QC calculation is set up, it will fail. This is actually an optimistic view, because the Copenhagen Interpretation is a fundamentally pessimistic assumption: that because we don't know what's behind a certain observed random distribution, we can't. See the following link for more details. (But IAMAP, and I'm not really keeping up with this area.)

[1] For more on how the Copenhagen Interpretation evolved, and just how little empirical basis there is for it, see http://books.google.com/books?id=tTN4HuUNXjgC&lpg=PP1...

gjm116• 15 years ago

Quantum computation does not in any way depend on the Copenhagen interpretation.

Estragon7• 15 years ago

  > But IAMAP,

Gah, that should be IANAP. (Too late to edit it.)

rayboyd• 15 years ago

Some info at Quantiki: http://www.quantiki.org/

http://www.quantiki.org/search/google?query=programming

gjm116• 15 years ago

Here's one concrete proposal: http://arxiv.org/PS_cache/cs/pdf/0103/0103009v3.pdf

I strongly suspect, though, that the answer is: The quantum magic will be packaged up into small black boxes that perform a modest range of tasks faster than they could be done classically, and programming will continue to consist mostly of writing classical code; it's just that there will be superfast implementations of a few useful things.

That might change if the number of qubits we can put into a quantum computer ever gets comparable to the number of ordinary bits we can put into a classical computer. That'll take a while.

(My suspicions and guesses are merely suspicions and guesses. I am not a quantum computing expert.)

Panoramix• 15 years ago

Very valid question, just keep in mind that quantum computers are not meant to and will not likely replace CMOS. Quantum computers will probably suck at the tasks where your laptop excels and vice versa.

kondro• 15 years ago

Yay, probabilistic computing.

You have a 99.5% chance that your PayPal transaction has succeeded. A bit like using a NoSQL database.

sukuriant2• 15 years ago

It's more useful for problems in the NP-Complete set, where you can write an algorithm that should take a very long time to perform, but takes very little time to check.

Take the 3-sat problem, for example. It takes a very long time for conventional algorithms to produce a correct answer; but, given a potential solution, it takes very little time to check for correctness. It's this area that quantum computers could shine in. Get a potential answer from the machine and check its accuracy very quickly. If wrong, try again.

[edit: if I misunderstand quantum computers, forgive me. This is just what I thought their allure was]

gjm116• 15 years ago

Quantum computers are not known to be able to solve NP-complete problems in polynomial time. (Assuming for the sake of argument that we can actually build them.)

There are problems -- factorization, as others have already said, is the commonest example -- that (1) are not known to be solvable classically in a reasonable amount of time and (2) are known to be solvable by a quantum computer in a reasonable amount of time. But they aren't NP-complete problems.

wladimir• 15 years ago

A bit like any hardware/software combo. Nothing in life is 100% reliable. If you make the probability of failure small enough, and are able to detect and fix errors (very important), it will be good enough.

exit• 15 years ago

this article doesn't get into what kind of future quantum computing will enable.

can anyone describe a program which cannot be written (efficiently) today, which might run on quantum computers eventually?

wlievens• 15 years ago

Shor's algorithm is the classic (pun intended) example: http://en.wikipedia.org/wiki/Shors_algorithm

Jach2• 15 years ago

I think this is a better writeup: http://www.scottaaronson.com/blog/?p=208

retube• 15 years ago

Factorisation is the common example. You'll be able to factor gigantic numbers like an RSA public key pretty much instantaneously, as thanks to a qubit's super-position of states you can operate on all possible states at once. But in general it's all about parallelisation - being able to perform an operation on all states (ie numbers) at once. Due to the probabilistic/uncertain nature of measurements of a quantum system though I believe operations have to be performed a number of times in order to build statistics around the "right" answer.

trotsky2• 15 years ago

While the other answer about factorization hit the nail on the head, let me say it again in more direct terms. There is a strong belief among those who pay serious attention to encryption (NSA, etc.) that quantum computing would/will render all traditional encryption (minus things like one time pads) obsolete. An actor with a sufficiently advanced quantum computer would be able to break everyone else's comms.

maggit2• 15 years ago

I understand how quantum computers can break RSA; by factoring numbers quickly. That's exploiting a known "weakness" in RSA.

I'm curious as to how quantum computers would break other encryption algorithms like AES or ElGamal. Do you have any details?

danparsonson• 15 years ago

You might find this useful: http://michaelnielsen.org/blog/quantum-computing-for-everyon...

Quantum computing device hints at powerful future

Related Stories