Significant Advance in Quantum Computing

wcitech writes "Apparently scientists have been able to create circuitry that mimics the behavior of atom pairs by using superconductors." From the article: "The work, reported in the Feb. 25 issue of the journal Science, demonstrates that it is possible to measure the quantum properties of two interconnected artificial atoms at virtually the same time. Until now, superconducting qubits--quantum counterparts of the 1s and 0s used in today's computers--have been measured one at a time to avoid unwanted effects on neighboring qubits." The second Quantum computing revelation this month, in fact.

Comments

Phew

[qw0ntum]

Before I go worrying about quantum computers, I need to get my own working. But in a quantum world, I guess they are working AND messed up at the same time.

Re:Phew

[Pax00]

Before I go worrying about quantum computers, I need to get my own working. But in a quantum world, I guess they are working AND messed up at the same time.

Broken and working at the same time.. how is that different than running windows?

Re:Phew

[datadictator]

Simple 32 Qbit quantum computer:

32 Boxes
32 Cats
32 Proton emitters

Shroedinger would have been so proud

Re:Phew

[FireFury03]

Windows doesn't usually seem to have the "working" bit...

Re:Phew

[StikyPad]

Wouldn't they actually be neither broken nor working? Until you tried to use it, of course, at which point you'll have to decide whether to make funeral arrangements or provide a saucer of milk.

I'm not a quantum engineer

[GreyWolf3000]

This question may be stupid but...

Would we need to read 32 quantum states at a time to get '32-bit' registers to build basic processors??

Re:I'm not a quantum engineer

[Jeff DeMaagd]

I don't think it works that way.

"Two entangled qubits, meanwhile, can simultaneously evaluate four inputs. Put another way, a traditional memory register with eight bits can store only one of a possible 28, or 256, digital "words," but a quantum register with eight qubits can represent and compute with all 256 words at once."

link

If you could have 32 entangled qubits, you could simultaneously evaluate 2^32 inputs, which is more than 4 billion possibilities.

Re:I'm not a quantum engineer

[kernel_dan]

Wikipedia has a good comparison of the differences between a traditional register and a quantum register (qubits).

Re:I'm not a quantum engineer

[CajunArson]

A quantum computer will probably never have 'registers' in the conventional sense since deterministic I/O like in a standard register would alter the quantum state every time a photon hit the qubits. In fact, beyond solving certain specific types of problems don't expect a quantum computer to be running minesweeper anytime soon. IANAP but from what I've seen of current experiments, the results aren't even exact like you would expect from a regular CPU, rather, a whole crapload of qubit runs are executed at once, and the most probable realized state is considered to be the 'answer'. I'm not even sure if it is possible to 'reset' the qubits after the operation without destroying them. Physcists, feel free to chime in now.

Re:I'm not a quantum engineer

[PurpleFloyd]

Sort of. While it would be necessary to have 32 qubits to build a 32-bit processor, that processor would be radically different from the one that's probably in your computer right now.

Quantum computers probably won't ever displace conventional computers completely; while there are some tasks at which they excel, they would be incredibly inefficient for typical computer tasks. A more realistic role for a quantum computer would be a coprocessor - when the host CPU is presented with a problem that could be better solved by a quantum computer, it offloads that problem to a dedicated quantum computer to which it is attached.

It would be a tremendous waste of technology to use a quantum computer to evaluate operations which are serial, rather than parallel, in nature. While this may someday change - there was, after all, a day when all the computers in the world didn't have as many transistors as are in a single modern desktop - it is likely that for the forseeable future, quantum computers will remain far too valuable and rare to be used for anything a more conventional computer could do as well.

Re:I'm not a quantum engineer

[MOBE2001]

"Two entangled qubits, meanwhile, can simultaneously evaluate four inputs. Put another way, a traditional memory register with eight bits can store only one of a possible 28, or 256, digital "words," but a quantum register with eight qubits can represent and compute with all 256 words at once."

So, If you get all possible answers simultaneously, how do you tell which one is the right answer to the problem you're working on?

Re:I'm not a quantum engineer

[oftheapes]

sort of...but the concepts of bits are different

using 32 qubits gives you ((2^32)-1) and the ability to examine 4'294'967'295 solutions simultaneously you'd need 6 qubits to examine at least 32 states and no more than 63 states

Re:I'm not a quantum engineer

[nacturation]

Here's a thought: how about when we've mastered the technology, we could create entire atoms and, eventually, entire components using entangled particles. So if the NSA had one computer and I had the same computer with an entangled network interface or video card, would I be able to surreptitiously spy on the NSA without them ever knowing?

At the very least, it'd make a neat premise for a novel if someone hasn't written something like that already.

Re:I'm not a quantum engineer

[Jeff DeMaagd]

From my understanding, you aren't getting all possible answers simultaneously. You are evaluating all possible answers simultaneously and statistically getting the "right" answer.

Re:I'm not a quantum engineer

[bman08]

Yes, and NSA would be able to look at your porn. The result would be you spying on spys spying on your own porn. I think I just developed quantum masturbation... I'm going to go clear some shelf space for my Nobel.

Re:I'm not a quantum engineer

[MOBE2001]

From my understanding, you aren't getting all possible answers simultaneously. You are evaluating all possible answers simultaneously and statistically getting the "right" answer.

So are you saying that you already know the probability of the right answer before you compute it? Or are you saying that the QC already knows what answer you're looking for and somehow futzes with the probabilities so that when you collapse the wave function, voila! the correct answer is revealed, as if by magic?

You know, the more I read about this quantum computer stuff, the more I am convinced that it's nothing but rancid snake oil. Just one man's opinion, of course.

Re:I'm not a quantum engineer

[FooAtWFU]

http://en.wikipedia.org/wiki/Quantum_computer#Bits _vs_qubits sez of an example 3-bit quantam operation...

Upon termination of the algorithm, the 8-dimensional complex vector stored in the register must be somehow read off from the qubit register by a quantum measurement. However, by the laws of quantum mechanics, that measurement will yield a random 3 bit string (and it will destroy the stored state as well). This random string can be used in computing the value of a function because (by design) the probability distribution of the measured output bitstring is skewed in favor of the correct value of the function. By repeated runs of the quantum computer and measurement of the output, the correct value can be determined, to a high probability, by majority polling of the outputs. See quantum circuit for a more precise formulation. In brief, quantum computations are probabilistic.

Re:I'm not a quantum engineer

[Anonymous Coward]

The previous poster was right. The q-registers are QM wavefunctions where the eigenstates represent possible solutions to the problem being computed. You are allowed to manipulate the wave function via quantum (hamiltonian IIRC) operators to your heart's content, but you can only measure one of the eigen states at a time. the tricky part is manipulating a q-register wave function such that the right answers are represented by eigenstates that are more probable than the ones that are wrong. It solves probablistic algorithms, and you don't a QC to do that. What a QC gives you is a way of operating on all possible states at once, whereas a regular turing machine type of computer can only act on one state at a time. This ability allows for a greater range of problems to be tackled in polynomial time by QM probablistic algorithms, such as, famously, factoring a number into its primes.

Re:I'm not a quantum engineer

[timothyr]

You've hit on the basic power of quantum computing. In rough terms, while we have to go from 32 to 64 bits to double the processing power of a classical computer, we double the power of a quantum computer by adding just one more bit. This change in scaling allows you to do things like search a database in O(Sqrt[N]) time and factor a large number in polynomial time.

Re:I'm not a quantum engineer

[timothyr]

That's the trick of designing a quantum algorithm. You set things up so that the "right" answer results in constructive interference, while the "wrong" answers interfere destructively. At the end of the quantum computation, all the probability rests in the answer, but in the course of the computation the system has explored many more possibilities through superposition.

Re:I'm not a quantum engineer

[Creepy Crawler]

... so that when you collapse the wave function, voila! the correct answer is revealed, as if by magic?

Most of the time.

Re:I'm not a quantum engineer

[aprilsound]

You actually only get one answer, but all possibilities have been "computed" and the probabiliy that the answer you get is the correct one is atleast above 50%. So, if you need to be certain, you repeat.

It basic computational theory terms, it is a true non-deterministic fintite automata. For example, suppose you want to compute the sortest route covering all the edges on a graph (if you dont understand that, imagine streets as edges, and that you want to travel down every street).
This is a classic NP problem, the traveling salesman problem. It is very simple to devise a method of computing a solution, but for a graph of N nodes, the complexity is O(x^n), or exponential growth. In other words, 2 nodes isnt bad, but 10 nodes takes x^8 times as long (x is some constant btw), so for any non trivial TSP, that is quite a long time.
A quantum computer, however, can solve it in roughly O(N) time, because it computes all possible paths at once, and then the shortest is "probably" the resulting state.
Simple in concept, but implemention is another thing... Google for Shor's algorithm if you want more information.

Re:I'm not a quantum engineer

[Anonymous Coward]

Ok, it works like this: you start off by initializing your qubits to a uniform superposition of states. That is every different possible string of 1s and 0s of a length n has an equal chance of occurring if you take a measurement at this point. Then you perform an operation on this state. The Cliff's notes version of things is that you should pick an operation that transforms each state onto one that is likely to be the answer. Then when you measure the outcome you are likely to get the answer you're looking for. So long as the probability of getting the wrong answer has some upper bound less than one you can just rerun the algorithm until you have get the right answer.

All of the basic theoretical work is in place. We've got algorithms, we've got error correcting methods, we've got quantum programming languages and we have every reason to believe it will work. Based on other experiments in quatum mechanics all of the basic principles work.

The biggest problem with quantum computing is that it's going to be expensive for a long time. These systems are fragile and must be shielded from outside events. Implimentation hasn't caught up with theory yet. We've got problems such as storing a qubit for an extended period of time and it may be a while before useful memory densities are achieved.

There's a lot left to be done, but quantum computing isn't a scam.

Re:I'm not a quantum engineer

[Chmarr]

What you actually need is a function that flags 'this is the right answer', and then you just read off the inputs.

For example, with a sufficiently large QC, you could find an input that matches a particular SHA-256 input INSTANTLY. Ie, "Give me the input where the output is equivalent to this hash".

Re:I'm not a quantum engineer

[Boronx]

Quantum computers would actually achieve a major goal for minesweeper development: the ability to dynamically change the mines to maximize frustration without invalidating previous moves and all in constant time.

Re:I'm not a quantum engineer

[Deanalator]

Shor's factoring algorithm has two registers, which are pretty much seperate parts of the algorithm. One register you hit with a hadamard to put n bits in a superposition of all possible states, and the other is what you run through an algoritm to do all the exponents and mods etc, then you do the quantum FFT at the end and get the period.

Also I think DWave has been doing doing this thing with superconductors for quite a while now. NMR quantum computers have never really been proposed as practical implimentations, its just really cheap to build smaller ones.

Re:I'm not a quantum engineer

[drgonzo59]

Is there a way to use the quantum computer for TSP? The only quantum algorithms I know of is Shor's factoring and Grover's algorithm. That sort of put me off going too much into the QC area, aside from taking 2 or 3 classes on the subject (I have a comp sci degree). I know that searching and factoring are very important algorithms but what about others like: sorting, graph algorithms, SAT or fast matrix multiplication .

Re:I'm not a quantum engineer

[zootm]

Here's a question -- does this "solve" P = NP (or P =/= NP) in any sense? I guess not since they aren't defined as "physical" models of computation, but I think it's an interesting angle on this (I'd been thinking about quantum = NP before, but I'm really not qualified enough to make a real comment).

Re:I'm not a quantum engineer

[clambake]

So, If you get all possible answers simultaneously, how do you tell which one is the right answer to the problem you're working on?

Shhh! You'll screw with thier grant applications.

Re:I'm not a quantum engineer

[anthony_dipierro]

It seems that TSP, if not directly expressible as a searching algorithm, could certainly be expressed as one. In the end I guess we'll have to have a regular computer and quantum computer all within the same box, most likely with the quantum computer as a side processor kind of like an FPU (though presumably with a much more complex instruction set).

Re:I'm not a quantum engineer

[anthony_dipierro]

It would be a tremendous waste of technology to use a quantum computer to evaluate operations which are serial, rather than parallel, in nature.

When I hear this, I immediately think "AI". In that sense it might make sense not to tightly couple the devices so closely, but instead hook them both up to the same network independent of one another. After all, the brain seems to do a good enough job with just the parallel processing parts, using computers to handle the serial processing. Likewise maybe a quantum computer could just have a login account to a few standard computers and just run (or write!) a program to handle some tough calcuation bits (It would of course contain a basic multiplication table and addition table just like our human brains do for the simple stuff). Sure, I guess you could increase the network speed by putting them in the same box, but with a smart enough algorithm it shouldn't require too much in the way of communication back and forth.

Of course, I never even got to take a course in quantum computing when I earned my degree, so maybe I'm taking too much meaning out of the description of a quantum computer as a parallel device. I'm certainly looking farther ahead into the future than the initial configuration of these things.

it is likely that for the forseeable future, quantum computers will remain far too valuable and rare to be used for anything a more conventional computer could do as well.

Fortunately the internet is much further along today than it was in the days of the supercomputers, so it might not be too unreasonable for scientists all over the world to get a timeslice on one (not implying the same one).

Re:I'm not a quantum engineer

[rbarreira]

Well, if we wanted to show that a QC can solve all NP problems in polynomial time, it would suffice to prove that one of the problems which QC's can solve in polynomial time is NP complete. If I know correctly, the problems which are known to have this characteristic (solvable in poly. time with a QC), are not known to be NP complete.

For example, the best algorithms currently known for factoring (on normal computers) are of sub-exponential time, not polynomial. But they aren't known to be NP complete, so with current knowledge, building a QC wouldn't allow us to solve any NP problem quickly with it...

Re:I'm not a quantum engineer

[Smidge204]

So it works kinda like a Pentium, then?

=Smidge=

Re:I'm not a quantum engineer

[MarkPNeyer]

It's not really a true non-deterministic finite automata - with an NFA you can just check to see if the machine is in an accepting state at the end of feeding it your input. Determining whether the quantum computer is in an accepting state at the end of feeding it your input is one of the most difficult parts of developing quantum computers - you have to somehow get non-accepting states to 'cancel each other out' so that the probability of their being measured is as close to zero as possible. An ideal quantum computer could find out how long it takes to travel every path, simultaneously in O(n) time, and then discard all of paths that weren't the best in O(1). Quantum comptuers we develop are going to take some time to get rid of all the bad solutions. For example, using the current model for a quantum computer to find a given name out of a phone book of 'n' takes takes the quantum algorithm O(sqrt(n)) time; it should take a NDFA only O(n) time. So there are some differences.

Re:I'm not a quantum engineer

[Daniel]

You can analyze the probability of an algorithm's success without knowing the answer it'll produce. This is a well-known technique even outside the realm of quantum computing. Here's a simple example: I have a number between 1 and 100; try to guess it. Of course, there's the standard O(log n) technique (which is probably the best one in this case!), but you could also just guess randomly until you find the number. In this case, you have a certain chance of finding the answer within, say, 200 steps (can't remember offhand but it should be fairly high). If you decide to arbitrarily terminate the search at this point, you can calculate the probability of the algorithm succeeding. Standard practice is to just prove that you have at least a 50% chance of success (at which point you can achieve an arbitrarily high chance of success by iterating the algorithm enough times) -- of course, 50% is an arbitrary number; any number above 0% would work from a theoretical point of view.

An example of a real algorithm that works this way is primality testing. There's an easy test that returns "false" for all primes, and returns "false" or "true" with equal probability for composites. (search for "Solovay-Strassen") Since the probability of a false negative is 50% (when you have a composite) if you pick enough samples and they all fail, you can say that there's a "high probability" that the number is prime. (for instance, 256 tests will get you odds of 1/(2^256) that the answer is wrong)

I don't pretend to understand quantum computing, but I do know that the basic processes are probabilistic, so it's not surprising that you end up with a probability of finding the right answer. Also bear in mind that there are only two (last time I checked, anyway) known algorithms for quantum computers, or at least only two that are significantly faster than the "standard" version, so it's not like QC is claimed to solve every open problem in computer science (despite what some guy above was saying).

Daniel

Re:I'm not a quantum engineer

[zootm]

Yes, but the parent mentioned non-deterministic Turing Machines (I think...), which is how NP systems are defined.

Re:I'm not a quantum engineer

[mothz]

O(x^n) sounds pretty good, if only we could get x below 1.

Re:I'm not a quantum engineer

[grammar fascist]

Is there a way to use the quantum computer for TSP?

Nobody knows, as far as I know.

TSP is NP-complete. As nifty as Shor's algorithm is, it only solves an NP problem in polynomial time. That implies either 1) nothing about solving other NP problems in polynomial time, 2) that it might be possible to solve other NP problems, or 3) that integer factorization is not NP - it's either P or some other computational class we haven't discovered yet.

Re:I'm not a quantum engineer

[zootm]

Yeah, most people at my University are of that opinion too. It's fairly obvious why it's such a difficult thing to decide when you look at what you're actually trying to prove in that case.

For what it's worth, I've done two courses (well, one and a half) on this, but Quantum Computers haven't been mentioned, I just wondered how they fit in.

And the winner is...

[dfn5]

Number 3 in a quantum finish

No fair! You changed the outcome by measuring it!

Re:And the winner is...

[grasshoppa]

Bravo, excellent joke. I salute your geekiness!

Re:And the winner is...

[HazE_nMe]

Thats Prof. Farnsworth from Futurama. Funny thing is I was JUST watching that episode.

Re:And the winner is...

[mothz]

Funny thing is I was JUST watching that episode. Actually, the quote is the funny thing. I doubt anyone got any enjoyment out of knowing that you've seen that one recently.

Re:And the winner is...

[HazE_nMe]

Funny doesn't always mean humorous. It can sometimes mean strange. You score no geek points, do not pass go, and may god have mercy on your soul.

I'm guessing...

[OneOver137]

the whole paradigm of 'xx-bit processor' will go out the window once the technology matures and software makes full use of the capabilities.

applicable quote

[Triumph The Insult C]

"So, computers. I hear they basically break down to a bunch of ones and zeroes. I don't know how that means I can see naked women on my screen, but God bless you people"

Related Quantum News: The Slashdot Effect

[Nova Express]

Scientists also announced that they had discovered a principle similar to Von Neuman's Catastrophe, namely The Slashdot Effect. This effect makes it impossible to both link to the story from Slashdot and read the story thus linked, as the very act of linking it renders the story impossible to read. To isolate these quantum fluctuations from the greater Slashdot Effect, scientists have suggested calling this specific quantum problem Commander Taco's Catastrophe...

Re:Advances?

[Anonymous Coward]

Fool, It's both simultaneously...

Re:Advances?

[JDevers]

Well, obviously it isn't ready but there are steps between "hey, I've got a good idea" and "you want to buy this product from me???"

Re:Advances?

[Anonymous Coward]

Actually, it can also be in a superposition of being both ready and not at the same time

Not so soon, may be never

[karvind]

A non BS critical review.

Quantum computing: a view from the enemy camp

Quantum computing relies on processing information within a quantum system with many continuous degrees of freedom. The practical implementation of this idea requires complete control over all of the 2^n independent amplitudes of a many-particle wavefunction, where n>1000. The principles of quantum computing are discussed from the practical point of view with the conclusion that no working device will be built in the forseeable fu

Re:Nice cray icon

[CAlworth1]

Indeed - first article in the supercomputing section. Is anyone else kind of suprised that it has taken this long?

Re:Advances?

[nacturation]

If your idea of quantum computing is a computer only capable of a handful of bits and costing millions, then yes... the technology is ready. Would you like fries with that?

Religious implications

[SemioticGhost]

Man reminds me more and more of God every day. Creation in our own image, no?

Re:Religious implications

[ulatekh]

Of course! We created God...in our image and likeness, no less.

Re:Religious implications

[(el)Capitan.Nick]

that "perfect being" wasn't so much a God as a standard we go for, society's personality goal. Too bad It's quite Schizophrenic.

Re:Religious implications

[rbarreira]

Because it is. It may also be obvious for some, I don't contest that.

And a Beowulf Cluster wiped out my credit card

[ABeowulfCluster]

Damn magnets. Seriously though, they're 'mimicking' a quantum effect, not using real quantum states. If it doesn't say 'Quantum' on the box then it's not quantum.

Re:And a Beowulf Cluster wiped out my credit card

[Anonymous Coward]

wait a sec buddy... flux quantization is definitely a quantum effect and that is what this is based on at the core....hell superconductivity is a quantum in nature. Quantum != small... nano==small. So although this is not a nonoscale implementation of a quantum bit(s), it is a quantum bitbit(s). Plus this is macroscopic implementation so it can be easily fabricated using standard photolith techniques.

What's the point?

[jholzer]

From http://en.wikipedia.org/wiki/Quantum_computer#Bits _vs_qubits
"This dramatic advantage of quantum computers is currently known to exist for only those three problems: factoring, discrete log, and quantum physics simulations."

I don't see Quake 10 on the list, so what's the point?

Re:What's the point?

[Anonymous Coward]

"I don't see Quake 10 on the list, so what's the point?"

accurate video game physics down to the quantum level

Re:What's the point?

[Jerf]

I don't see Quake 10 on the list, so what's the point?

The point, of course, is to solve the factoring, discrete log, and quantum physics simulation problems.

Whether that is worth the resources being thrown at it is an exercise for the reader.

(The more I learn about quantum computing, the less likely I think it is and the more I wonder what all the fury is about. I expect this will collapse in about two years and be remembered right next to the "great" AI era of the 80's. Hey, maybe I'm wrong... and hey, maybe 80's style AI programming really is the path to strong AI and we just didn't try hard enough... but I'm not holding my breath and the burden of proof remains on the researchers.

It reminds me of FTL or teleportation; with every little "advance" physics fanboys crow about how much "closer" we are, whereas I see an ever-refined understanding of why the thing we are looking for is still impossible and the potential loopholes slamming shut.

Preparing for "-1, troll" from physics fanboys in five... four... three...)

Re:What's the point?

[Zeinfeld]

"This dramatic advantage of quantum computers is currently known to exist for only those three problems: factoring, discrete log, and quantum physics simulations."

Actually it is slightly more general. Having spoken with some high powered cryptographers (i.e. the ones with the Turing awards) there is a strong suspiscion that any problem which allows a public key cryptosystem to be created will turn out to be efficient on a QC machine.

There seems to be something pretty fundamental going on there. The really wierd part is that the speedup does not appear to apply to symmetric ciphers. So AES is secure even if RSA is bust.

Re:What's the point?

[rjh]

You need to check with better cryptographers; a massive speedup does apply to symmetric ciphers, in the form of Grover's Algorithm. It reduces the keyspace you have to search by an exponential factor of 0.5, meaning breaking 128-bit symmetric crypto by brute force is within the realm of well-funded private citizens.

Re:What's the point?

[Haydn Fenton]

"accurate video game physics down to the quantum level"

Not to nitpick, but what's the point in that? Is any normal human being capable of being able to tell what's going on at the quantum level?
Im afraid not, "quantum foam" (the distortion of space and time and seemingly impossible random things happening) is very volatile and unpredictable, however, like quantum computers, the randomness in all of this ends up with the one most likely result at the macroscopic level (things big enough that we can see them).
For example, when you throw a ball, you pretty much know where it's going to go and how long it will take, but inside and around the ball, at the quantum level, things are going in all sorts of directions, and probably even through time and dimensions which we are unaware of (see String Theory). Therefore having physics that complex in a game would be nothing but an immense waste of time and computing power.

Re:What's the point?

[Zeinfeld]

You need to check with better cryptographers; a massive speedup does apply to symmetric ciphers, in the form of Grover's Algorithm. It reduces the keyspace you have to search by an exponential factor of 0.5, meaning breaking 128-bit symmetric crypto by brute force is within the realm of well-funded private citizens.

But attempting to apply it to AES or even DES requires a vast quantum computer, you have to essentially unroll all the loops and apply it as hardware. So the complexity is much higher than breaking RSA.

Reducing O(N) to O(N^.5) is not that significant. SHA-1 was recently broken on a collision attack which due to the birthday 'paradox' begins with a complexity of the root of the keyspace using brute force.

If you went after 128-bit RC4 using the algorithm you still have a 2^64 complexity and you cannot perform the search in parallel plus you have only a probabalistic chance of the result being right.

256-bit AES has 2^128 complexity which is almost certainly beyond the capability of a QC machine, the key size was not chosen by accident and certainly not out of concern that someone would brute force the 128 bit key size.

If there is a concern we can in any case generate a symmetric algorithm of any desired strength simply by adding on bits. The only difference is we now need twice as many. A 512 bit key would be entirely practical.

Re:What's the point?

[thechao]

Dude, Quake 10 has been out for YEARS.

Re:What's the point?

[Tyler Durden]

(The more I learn about quantum computing, the less likely I think it is and the more I wonder what all the fury is about. I expect this will collapse in about two years and be remembered right next to the "great" AI era of the 80's. Hey, maybe I'm wrong... and hey, maybe 80's style AI programming really is the path to strong AI and we just didn't try hard enough... but I'm not holding my breath and the burden of proof remains on the researchers.

It reminds me of FTL or teleportation; with every little "advance" physics fanboys crow about how much "closer" we are, whereas I see an ever-refined understanding of why the thing we are looking for is still impossible and the potential loopholes slamming shut.

You should try learning more because you have no idea what you're talking about.

Small-scale quantum computing has been happening for a while now. The only problem now is overcoming physical challenges to scale them up for solving larger-scale problems. And more strides are being made to overcome them all of the time.

FTL is crap because the "things" that are cited as travelling faster than light cannot be used to send information faster than light. How QC reminds you of FTL is beyond me since the situations are completely different.

It wouldn't take a "physics fanboy" (whatever that is) to mod you down. Just someone fond of facts and reason would suffice.

Re:What's the point?

[Jerf]

Read that page, knew everything on it, assumption of ignorance wrong, mind not changed by pop-science overview.

I think the "problems" you wave away with such glibness are exponential, and the most power we'll ever be able to being to bear on the problem is polynomial. Current research has done nothing to dissuade me of this, and the fact that such computers remain "small" are exactly what I mean; for small values we can hold it together, but it says little about our ability to build at large values. When someone builds a 100-qubit machine that works (i.e., solves a problem significantly faster than a conventional computer could) reliably, I'll concede I was wrong. In the meantime, I see the current strides as people vigorously clearing brush in the jungle away... while all the while trying to get to the moon.

Ref that other paper someone linked on skepticism about QM. I am aware of the fact that a couple of his numbers have been found wrong, actually, but his argument doesn't suffer for just bumping his lower limit by a factor of 3 or 4, which isn't a good sign for QC.

Re:What's the point?

[CTachyon]

All you have to do with symmetric crypto is double the bits to defeat Grover's algorithm. After the initial doubling, you're back to the same "arms race" between crypto and Moore's Law. That's a trivial situation compared to public key crypto. (Although, Shor's algorithm does require a QC with roughly 2n coherent qubits for an n-bit prime, which provides public key crypto with a bit of a reprieve. If the number of qubits in a QC follows the same pattern of growth that memory size has, another arms race might result. If the number of qubits goes up in sudden spurts, RSA and its relatives might go extinct, because a "safe" number of bits for a future date cannot be estimated.)

Wishful thinking.

[dauthur]

It's only a matter of time before my quantum computer is produced, and it's powered by Lucky Charms and Beer.

But in reality, I wonder if there's any advances in superconductivity?

Re:Wishful thinking.

[Evil Pete]

It's only a matter of time before my quantum computer is produced, and it's powered by Lucky Charms and Beer.

... or a really good cup of strong tea. [ oblig. Hitchiker's reference ] Though that was for the infinite improbability drive I think.

Re:Wishful thinking.

[Cliff.Braun]

Brownian motion generator.

cray icon

[pulgabm89]

This is very interesting. Where does /.'ers get their ideas from? http://hilbert.math.uni-mannheim.de/~seiler/cray.j pg/

Serious question.

[hot_Karls_bad_cavern]

Will some one give me an idea of what this means for our current encryption systems and me as a private citizen ... kinda wishing to keep things still, ya know, private and without having access to the same horsepower?

Re:Serious question.

[Planesdragon]

Nothing.

No, wait. It means that we're going to have to stop lying to ourselves, admit that no communication mechanism can ever be capital-S secure, and listen to the geeks who've been saying that security needs to be convincing people not to try, detecting when they do, and being able to recover from any intrusion.

Re:Advances?

[ggvaidya]

Welcome to the world of quantam mechanics - the technology is both ready AND not ready!

Booor-ing...

[Goonie]

Why merely crack RSA and radically speed up quantum physics simulations? That's aiming far too low.

Instead, Tien Kieu from my university wants to solve arbitrary Diophantine equations using quantum effects. If he's a) correct, and b) it becomes possible to create the required quantum behaviours for arbitrary equation, the following problems become solvable:

• The halting problem for arbitrary Turing machines, with all that that would imply.
• The Riemann hypothesis.
• Goldbach's conjecture

  Needless to say, to say people are sceptical of Kieu's ideas is an understatement, but it's fun to speculate about the "what if"...

Re:Booor-ing...

[captain1010]

No.

Quantum computers can change the rate at which problems are solved, but not whether or not a solution is technically achievable through computation.

Goldbachs' conjecture and the Riemann hypothesis might be provable through an accelerated brute forcing of all possible proofs if, for example, P=NP and algorithmic degrees and coefficients are reasonable, but this is only because such a brute force may be doable already with a sufficiently ginormous length of time (assuming that they are in fact provable to begin with, which some true propositions are not (unless our math is internally inconsistent)).

The halting problem cannot be solved for arbitrary Turing machines. Period. No algorithm, as we think of them, using quantum computers or not, will get around the fact that such a solution would create a logical inconsistency (a program could determine whether or not it itself would halt, and then do the opposite, but then it would have been wrong, which it can't be by assumption, and so reality bursts into flames). The only possible catch is that a technique that cannot be encoded in a Turing machine would not cause this particular logical inconsistency to arise. Basically this leaves an opportunity for solution through revelation. Or not, depending on your philosophical persuasion towards flaimbait and the rest of existence.

Again, though, quantum computers do not allow one to execute algorithms that are beyond simulation (albeit more slowly) on classical computers. What ifs are fun, but this one, at least in part, is worse than baseless.

Re:Booor-ing...

[IWannaBeAnAC]

Interesting. I am somewhat familiar with the 'Quantum Adiabatic Theorem', but you need to remember that it is a 'theorem' in the physics sense, not mathematical. ie, there isn't a proof, and moreover, a lot of people (including me) have doubts about it.

Originally the theorem was proposed as a means of solving NP-complete problems on a quantum computer. ie. to show that for a quantum computer, P=NP. I don't think many people actually believe that, and there are no known algorithms for NP problems. That is wild enough, but it is *really* wild that Kieu is saying that it can solve the halting problem. If the adiabatic theorem really imples that the halting problem is solvable, then I think it is just a very big nail in the coffin of the 'theorem'.

Aside: I thought the Reimann Hypothesis was formally undecidable? I also don't understand how the proof of Goldbach's conjecture would work. How can a finite computer test that the theorem is true for arbitarily large numbers? A symbolic proof is maybe possible, but then where does the computation come in? I guess I should read his paper....

Re:Booor-ing...

[aprilsound]

Ummm... the halting problem is PROVEN to be unsolvable. Check any introductory computational theory text.

Re:Booor-ing...

[Chandon Seldon]

Actually, you could easily solve the halting problem for computers with a metacomputer.

Now all you need to do is make that last sentance mean something.

Re:Booor-ing...

[maxwell demon]

Maybe his device contains a time machine as integral part. :-)

Re:Booor-ing...

[Daniel]

Needless to say, to say people are sceptical of Kieu's ideas is an understatement...

Given that you have to start by throwing out the Church-Turing thesis, I'd think that's hardly surprising.

The halting problem for arbitrary Turing machines, with all that that would imply.
The Riemann hypothesis.
Goldbach's conjecture

So.....is he planning to do this before or after he proves that integer mathematics is logically consistent? ;-)

Daniel

Re:Booor-ing...

[Splab]

"I don't think many people actually believe that, and there are no known algorithms for NP problems."
Ahrem, there are no known polynominal algorithms - you can bruteforce them given enough time, and therefore there is an algorithm.

Re:Booor-ing...

[IWannaBeAnAC]

D'oh. Look at the context in which I said that:

Originally the theorem was proposed as a means of solving NP-complete problems on a quantum computer. ie. to show that for a quantum computer, P=NP. I don't think many people actually believe that, and there are no known algorithms for NP problems.

The point is, that exponential-time problems are usually not solvable, because while it is completely obvious to every man and his dog that there are simple, dumb, brute-force algorithms to do so, the running time increases exponentially (duh) with the input size; so for any such problem it doesn't take long to get a running time of the age of the universe.

Please, can we take it for granted here, on Slashdot, that "solving NP-complete problems" means solving them in polynomial time?

Is it just me

[jessecurry]

or does the guy in the picture look a lot like one of the creators of south park?

Re:Quantum Logic

[Khakionion]

"Tangled oscillations" also brings to mind this one crazy pr0n I saw a while back. wtf lol right? kthxbye

I had a French Arabic math prof...

[MAdMaxOr]

who said "rectun" for rectangle, and "enitrate" for integrate, etc.

He tried to say:
"To integrate, you use small rectangles instead of large rectangles in your Riemann sum because they work better."

but ended up sounding like:
"To penetrate, you use small rectums instead of big rectums when your wiener's up because they work better."

True story

Re:Advances?

[aztektum]

Both of which are, at some point, are usually followed by "in 5-10 years." :P

More to it than that...

[Goonie]

The halting problem cannot be solved for arbitrary Turing machines. Period. No algorithm, as we think of them, using quantum computers or not, will get around the fact that such a solution would create a logical inconsistency (a program could determine whether or not it itself would halt, and then do the opposite, but then it would have been wrong, which it can't be by assumption, and so reality bursts into flames). The only possible catch is that a technique that cannot be encoded in a Turing machine would not cause this particular logical inconsistency to arise.

You've got it in one. According to Kieu, his system is a non-computable process; you can't simulate what it does on a Turing machine. Hence your objection doesn't apply to his claims.

However, there are apparently lots of other objections.

Re:More to it than that...

[xenocide2]

Now there's a useful device; one you can't simulate. I bet that's awesome for developers and designers ;)

That Blue Icon?

[TheLetterPsy]

What is that blue image representing this story supposed to be? Is it a cluster? Is it some sort of control center? Is anyone else wondering this?

Re:That Blue Icon?

[2centplain]

It's an old Cray supercomputer. http://cray.com/about_cray/history.html/

At last!

[mtec]

Now I can sleep.

This isnt right either..

[rufusdufus]

A quantum register does not actually represent all possible inputs. It represents a superposition of all possible inputs; this is a very important distinction.

When the register is 'read' after a computation, it contains exactly one result representing the results of one random possible input. Using a classical algorithm with the register would be exactly like a normal computer with a random setting as the input.

Getting anything special from a calculation from a qubit register is extremely tricky. Shor's algorithm does a special quantum fourier transform on the register to get the most common possible output [this is a metaphor] and only works because the values of the qbits are not independent (and thus do not represent all possibilites). The algorithm must be run several times to even get a statistically meaningful result.

Quantum computing isn't the holy grail

[guitaristx]

Look, people, you'd be a lot less impressed with quantum computing if you actually had an idea of what it does compared to traditional FET technology.

Here are some links that explain a bit about how quantum computers (specifically, Quantum Cellular Automata (QCAs) work:

Beware of PDF

Another PDF

It's not about blazing fast processing or seemingly infinite scalability, it's about simpler design. It takes 11(correct me if I'm wrong) FET items to make an AND gate, whereas it only takes 5 quantum cells. Furthermore, there are ways to make coplanar "wire" crossings. The problem is timing, since a signal has to propogate through a QCA like a set of dominos. There, IMHO, is too much hype surrounding quantum computing.

Re:Quantum computing isn't the holy grail

[Anonymous Coward]

You don't get it. This is Slashdot. The kids here watch a lot of the Sci-Fi Channel and anime DVDs. While generally agnostic or atheist in matters of mainstream religion, the idea of quantum computing ties together all the accumulated nonsense which fills their heads. Much like the "grace" of conventional religion, "quantum computing" provides the "magic potion" which can justify their belief in hobbits, wookies, and so on -- "Well if quantum computing can exist maybe that other stuff is true too . . ."

Remember, the average Slashdot reader doesn't have a degree in physics or electrical engineering. They are typically dropouts from junior college CS programs. If they are lucky enough, they drift into a job administering Windows machines at a non-profit organization. Chatting about "quantum computing" lifts their spirits, however briefly, and distracts them from their humdrum lives.

Re:Quantum computing isn't the holy grail

[maxwell demon]

Thode PDFs don't speak about quantum computers. They speak about using quantum devices to build more efficient classical computers (the fact that they call it quantum cellular automata doesn't mean that it is a quantum computer, it just uses quantum dots for operation). Indeed, they depend on inelastic processes, exactly those processes which actually pose the biggest problem in quantum computing.

Not every computing which uses quantum mechanics is quantum computing (indeed, otherwise our current computers would have to be quantum computers since semiconductor physics just cannot be done classically).

Quantum computers are computers which specifically work with quantum information (i.e. superpositions and entanglement). The papers you cited use quamtum dots to more efficiently process classical information.

Now that doesn't mean that the QCA work is less important (indeed, I think it's far more probable that you'll at some time work with computers based on QCAs than that you'll ever see a real quantum computer in your life). It's just that QCAs are not QCs.

And yes, I am a quantum physicist (although I don't work on quantum computing).

Re:Quantum computing isn't the holy grail

[guitaristx]

Could you post some links?

Re:Quantum computing isn't the holy grail

[maxwell demon]

Well, just googling for quantum computer gave me as very first hit http://www.cs.caltech.edu/~westside/quantum-intro. html, which looks quite good to me.

Also under the first links is http://www.qubit.org/library/intros/comp/comp.html , which also looks quite good to me. (the whole www.qubit.org is interesting, BTW).

If you want to go a bit more in depth, I think http://www-users.cs.york.ac.uk/~schmuel/comp/comp. html looks good.

And if you can't wait to program a QC, then you might be interested in QCL, the quantum computation language. Yes, you can download a compiler there (which of course only simulates a QC, since current computers don't yet come with quantum processors :-)).

sounds like rainman autistic computer....

[cheekyboy]

Is that how autistic people work? their brain is really a quantum computer, it just does all combinations instantly, but they get the correct one or know the correcy one, where us normal humans just dont know which is which or have no tap into the QC

Re:sounds like rainman autistic computer....

[ByteSlicer]

The similarity between brains and a quantum computer comes from the fact that the neurons in the brain also process the data in parallel. There is no quantum computing going on inside the brain. There recently was an article about an autistic savant explaining his calculation skills. Numbers are just shapes to him, and multiplying them means he just merges them in his head and reads back the emerged shape. Probably his visual cortex is doing the parallel operations on the shapes here (maybe similar to using the shader engines on your graphics card for doing calculations).

Re:sounds like rainman autistic computer....

[Thing 1]

What leads you to believe that the brain does not take advantage of quantum effects?

I read an article about 5 years ago that said that the human brain does take advantage of quantum effects, so if we want to design a computer as powerful as the brain, we will have to understand not only chemical, electrical, and biological processes, but quantum as well.

So if you've heard differently, please share.

Re:sounds like rainman autistic computer....

[ByteSlicer]

I'm not saying there are no quantum effects happening in the brain, just that the brain doesn't work as a quantum computer. The current understanding is that signaling between neurons is electro-chemical. Artificial neural nets were modelled after this, and although far from perfect, seem capable of doing things real brains can do (like recognizing faces). Neural networks don't work the same way quantum computers do. Their power comes from over 10^11 neurons working in parallel, each having maybe 1000 connections to other neurons. In a quantum computer, you don't need this massive parallel computing. The quantum bits there are in a superimposed state of both 0 and 1. This cause quantum operations performed on them to take in account all possible combinations, creating the same effect as performing all these calculations in parallel.

Re:I'm not a quantum engineer, no one is

[Avishalom]

its called a quantum mechanic.

Pedant alert

[nih]

measured virtually the same time = measured one at a time

so in that respect nothings changed...

Re:Advances?

[maxwell demon]

Actually, I never heared anyone saying: "hey, I've got a good idea in 5-10 years."

We already know what they will look like

[jgardn]

There's no need to speculate on how a quantum computer will work. We already have working examples, and we already know the generic properties of them. Instead of trying to figure it out on your own, go read the vast amounts of information on the topic available.

The three properties of the QC that are most important:

1. You can set the state of the qubits to whatever you like.

2. You have some transformation that the qubits will go through. This can be arbitrarily complex, and will be the most interesting part of the machine.

2. You can get a really good estimate of the state by doing the operation from the same initial state several times. See, when you go to measure a quantum state, you get one possibility of many. You have to make a lot of measurements to figure out what is really happening.

The best comparison is to think of the single-slit experiments you did in High School physics. You take a parallel light source (sunlight, laser, light from a distance) and have it strike a plate with a very thin slit. Then you hold a piece of paper where the light comes out. You will see bands of light, and some chromatic aberrations (you will see colors).

If you consider a single photon travelling from the light source and approaching the slit, passing "through" the slit, and then travelling off into any one of the finite number of directions, you ask the question: How can we predict which way it will go?

The answer is you can't. You have to do it a lot (like with a beam of light) and you can easily see what the probabilities are from that.

You can probably think of the experiment I described above as a very simple form of a quantum computer. You set the input - the light travelling into the slit. You have the transformation - the slit. And you can read the results by doing it several times.

That's all quantum computing will do for you. It's up to the really smart guys in white lab coats to figure out how to turn that into something useful.

I believe this will all be abstracted away from your eyes, just like today you don't worry about which register your integers is stored in and such. You will merely say, "Run the calculations on this set of data and give me the result" and it will do it before you can blink.

Heck, ordinary people won't even get to own a quantum computer until two things happen: (1) We find a better use for them than hacking into banks and stealing people's identities, and (2) we have built up enough of a reportoire of transformations that some subset of that is actually useful to solve the problems we face in computing today.

Re:We already know what they will look like

[sethjk1]

c-span showed a interesting talk from the library of congress Digital Future series. There is a link at http://www.c-span.org/congress/digitalfuture.asp (it is the one from Monday, January 24) There were very few really good questions, but a very bright scientist explains the basics. I would have liked to know if there is any P=NP optimism...

Re:We already know what they will look like

[SwervingVector]

Your sig is insanely retarded.

Wouln't it more likely be...

[NoMercy]

Some software developers test image, possibly gloating how he's the only one in the world who can view it?

Re:Too late...

[Synli]

And I forgot. NIST had a broken link to that article which I fixed (I just guessed and it was actually correct).

Time issues in quantum theory

[rjdegraaf]

From the article:

...demonstrates that it is possible to measure the quantum properties of two interconnected artificial atoms at virtually the same time.

and the uncertainty in the energy of the quanta increases, due to the uncertainty relation!

Also,

...virtually the same time.

Time is relative to the observer, and quantum theory treats time linear but Einstein says otherwise. Take a look at an EPR situation in space-time (talk by Roger Penrose).

Here's another question

[Ryvar]

If we can read the state of two entangled atoms, is communication at greater-than-light speed now possible? Wouldn't this violate causality?

Just curious.

--Ryv

Re:Here's another question

[marcosdumay]

No, because one can not chose what he will read from the atom.
This have already been discussed here (several times), there is a good explanation here.

Re:Here's another question

[CTachyon]

No. This is one of the consequences of the No Cloning Theorem, which states that it's impossible to copy qubits. The gist is that, for Alice to send information to Bob, Bob would need to make more than one measurement of the same qubit without collapsing it. One measurement just tells him "clockwise" or "counterclockwise"; the only information he now knows is that Alice's qubit is the opposite of his, but he can't tell whether or not Alice had measured hers before he measured his (or otherwise detect anything else Alice had done to her qubit).

If Bob could clone qubits, he could measure his cloned qubits instead; if they all gave the same answer, then Alice had measured her qubit before Bob measured his. If they agree on a pre-determined time for Bob to clone and measure his qubit, they can create a system for transmitting 1s and 0s.

42

[Megamote]

"Apparently scientists have been able to create circuitry that mimics the behavior of atom pairs by using superconductors" -- And found the answer to the life, the universe and everything is 42.

"I checked it very thoroughly," said the computer, "and that quite definitely is the answer. I think the problem, to be quite honest with you, is that you've never actually known what the question is."

Are you sure?

[rbarreira]

Are you sure of what you're saying? I've never seen any statement that a QC will be able to solve NP complete problems in polynomial time. Do you have any references?

BTW, Shor's algorithm is a factoring algorithm, not a TSP one. I know you haven't affirmed this directly, but someone might infer it from your post...

Re:Are you sure?

[aprilsound]

NP stands for Nondeterministic Polynomial Time so, yes, in theory, a quantum computer should be able to solve any NP problem in polynomial time, since any NP Complete problem (Im not sure if factoring ala Shor's algorithh is one) will reduce to any other NP problem in P time. As far as P = NP, a quantum computer would not resolce that, since it is still just a brute force attack on an NP problem. Resolving P v. NP is a theory problem, not a hardware problem. It might be more acuarate to call it a "non-deterministic" computer. You can currently similate a quantum computer (VERY slowly) on a serial device, and it could, eventualy, solve any NP problem. You actualy wouldn't need the simulation of the QC, but either way "eventualy," in most nontrivial cases, would mean after the sun burns out...

Because it is insightful

[aepervius]

Aside the blah-blah about gods (with a small g) created the world and yada yada, If you go beyond the religious (unprovable) statement, then the gods of each civilisation were a by product of those civilisation's history and social environement . Do you really think Anubis stood for the old egyptian in the afterworld to judge them (or was it Horus?) or did the egyptian imagine the jackal God and gave him a position as watcher of the Dead ? Do you really think Hades and Cerberus exists or was it a mythos formed by the grec society ?

This is why the coment above was modded as insightful. Naturally if you are a believer in *any* God I perfectly understand this rattle you.

Obligatory pun

[WalletBoy]

Riiiiiiiiiiiight... what's a qubit?

Where's my ansible?

[ehiris]

I don't think I'm ready to use quantum computers but if someone would build a quantum entanglement NIC or networking device, it would be something anyone could use.

Lowered network latency at long distances would make a world of difference especially with thin-client applications.

Sorry, but this is wrong

[Catullus]

There have been no algorithms devised for quantum computers so far that can solve NP-Complete problems like the Travelling Salesman Problem in polynomial time.

It *is* possible to achieve a square-root speed-up on essentially any problem in NP using Grover's algorithm, but it has also been shown that this is the best that can be achieved without exploiting the structure of these problems in some way as yet unknown.

It would be a major advance if anyone did come up with such an algorithm, and in fact (I think) most people believe it's not possible. Incidentally, resolving this question either way would not imply that P = NP or P != NP.

Unsolvable with a *classical computer*

[Goonie]

If you actually read all of your computational theory text rather than just the powerpointy lecture notes your professor gave you, you might be aware of the actual nature of the proof. The proof says that no Turing machine (or equivalently powerful system) is capable of deciding the halting problem.

Now, the Church-Turing thesis says (roughly) that any computational system can be emulated by a Turing machine - in other words, if it's computable, it's computable on a Turing machine. This is not a mathematical statement; it can't be proven. However, nobody has been able to figure out a remotely plausible way to build a machine that is more powerful than a Turing machine over the past 60 years, so the thesis is pretty much universally accepted, and so the undecidability of the halting problem has been regarded as absolute.

Kieu argues that the quantum effects discussed in his paper can be used to "compute" useful functions that are not classically computable. If true, this would invalidate the Church-Turing thesis, not the proof for the halting problem.

I'm not saying the guy is correct; I'll believe it can be done when I see it. But your objection is based on an incomplete understanding of Turing's work. You can read Turing's original paper online if you do a Google search for it.

Insightful?

[ulatekh]

Why is this modded up as "insightful"?

Well, it's a quote from a George Carlin stand-up comedy bit, and he usually rides the line between insightful and funny...

this is dead wrong

[rufusdufus]

there is no quantum algorithm to speed up np complete problems. this whole post is just not right

if this then...

[sixofonehalfdozenofa]

if quantum computing is possible, foregoing the cost, what kinds of nanotechnology might be on the way? regenerative fuel from garbage? viruses for individual gene patterns? artificial "bionic" body parts". Neurological mapping? BOO! Im not paranoid just thinking...

Cool

[bryan1945]

I can count to 4 in quantum now.

What's Inside?

[FFCobra427]

It's the year 2015 and I just got my new quantum computer. The label says "Possibly Dead Cat Inside!"