Quantum Computing Explained! (Well, Sorta)

An anonymous reader writes "Valiant effort to 'explain' quantum computing over on silicon.com — covering the difference between classical computers and quantum machines."

Comments

Weird thing about the article

[Anonymous Coward]

You can't possibly know if the article explains quantum computing until you actually read the article.

Re:Weird thing about the article

[Pojut]

But by observing the article, you're changing it. Does that mean it will explain it to you...but not to me? :)

Re:Weird thing about the article

[fred fleenblat]

I find your argument very polarizing.

Re:Weird thing about the article

[ultranova]

But by observing the article, you're changing it. Does that mean it will explain it to you...but not to me? :)

It means that the article's explanation is fuzzy and all over the place, however once you read it you perceive it as having collapsed into either explaining or not explaining quantum computing.

Re:Weird thing about the article

[human-cyborg]

Not exactly. Before you actually read the article, it simultaneously does and does not explain quantum computing.

Re:Weird thing about the article

[dogsbreath]

Forget magic. Any technology distinguishable from divine power is insufficiently advanced.

OTOH any magic, sufficiently explained, will appear to be a technology.

chatty narrative

[NoSleepDemon]

Interesting but the chatty narrative is really annoying and is getting in the way of the actual useful information

Re:chatty narrative

[geogob]

But "chat" is cat in french, which is totally relevant to quantum mechanics...

Re:chatty narrative

[Anonymous Coward]

Agreed. The chattiness simplifies some stuff towards poor wording or misrepresentation.
For example:
"Factoring massive numbers is what internet and banking security depends on, so security, financial services and military applications for quantum computers are easy to envisage."
RSA doesn't depend on factoring massive numbers. RSA depends on the fact that factoring massive numbers is computationally difficult.

Could be better.

Re:chatty narrative

[Pojut]

That's correct.

And don't call me Shirley.

One minor mistake

[vlm]

One more thing, there is a minority of scientists who believe that building a quantum computer will turn out to be out-and-out impossible.

However, if those scientists are right, the implication of not being able to build such a machine is that quantum mechanics itself, as a description of nature, is wrong. Either way, the stakes could not be higher.

One possible failure mode is the theoretical power required could exceed the light fluxs of the visible universe, that would be a bummer. Maybe in true supercomputer style, a formerly computational problem is merely converted into an I/O problem, the interface to the classical world might be too slow/imprecise/analog/noisy/random to pull useful results out of it. Nothing wrong with quantum theory at all, just not possible to interface usefully with the greater classical world.

Or the more practical engineering/accounting failure mode where it would simply be cheaper / faster / more efficient to use mass produced classical processor, possibly for any problem.

Thank god...

[PmanAce]

...for the leap in the right direction!

Seen on a major job board today

[Anonymous Coward]

From the geniuses in H.R.

Wanted:

Quantum Computer Developer.

Qualifications:

Five years in depth Quantum computing experience. Certification in Quantum Computing highly desired.
In depth knowledge of Quantum Computing principals and a proven track record of creating Quantum Computing applications.

Principals only.

Re:Seen on a major job board today

[phrackwulf]

If you're from the future, do you need H1-B Visa sponsorship? Or as long as I had citizenship in the past I could apply?

Re:Seen on a major job board today

[leonardluen]

You forgot the additional requirement "Must have cat"

Re:Seen on a major job board today

[sjames]

No quantum computing expert can ever be hired at a place with a formal HR process.

Interviewer: I see you attended MIT

Interviewee: I might have

Actually

[killmenow]

The more precisely the article explains it to him, the less precisely it will explain it to you.

I know you're being funny but

[Tekfactory]

Do you remember the Google Quantum Powered Image Search
http://www.newscientist.com/article/dn18272-google-demonstrates-quantum-computer-image-search.html

Some folks have questions about D-Waves technology, but there are people at Google who have been writing applications for Quantium computers.

Horrible

[aaaaaaargh!]

Sorry to be so negative but in my opinion the article is horrible. It doesn't explain anything unless you think bad analogies and jovial metaphors help you understand things better. After having read it, I don't know a single qubit more about quantum computers than before.

Re:Horrible

[noidentity]

Yeah, with a 350-pixel-wide web page (yes, the entire page), and an opening like this, I can't imagine why nobody would read any further:

Time machines - oh, boy!
Steady on Sam, I love science fiction as much as the next geek but I'm not talking about Quantum Leap here. This is even more exciting than time travel. OK, so what is this quantum computing lark then? Quantum computing and quantum information processing are research efforts that seek to exploit quantum mechanical phenomena to perform tasks such as massively parallel computing. The quantum research field also encompasses quantum cryptography, which utilises quantum phenomena to guarantee secure communications.

What are these quantum phenomena you talk of?
Tsk! Clearly weren't paying attention in physics class were you? [...]

Tip to new writers: you aren't witty, you aren't funny, you aren't entertaining. Leave your antics out of the writing and cover the subject matter so well that its inherent nature will be interesting to the reader.

Re:Horrible

[Interoperable]

Let me take a run at explaining quantum computing less awkwardly than the article.

A quantum bit (qbit) may be in a 0 state, a 1 state or any linear superposition (combination) of the two, eg. 0 + i1. When measured, the outcome of the measurement can only be 0 or 1 with the probabilities of each being governed by the ratio of contributions to the qbit from the 0 and 1 components.

One qbit can usefully encode one bit of classical information (this is the point that most articles on the subject muddle up). Entangled qbits, however, also encode information into the relationship between them. More accurately, the state of the two qbits combined cannot be described by the individual states of each qbit. The number of possible states that the combined system can occupy is greater than the number of states that two unentangled qbits (or classical bits) could occupy. In other words, N entangled qbits occupy a much larger state space than 2^N, which is the state space for N classical bits.

A quantum register containing N qbits can yield an answer with, at most, 2^N bits of classical information once measured; however, the computation itself can be performed in a state space that is much larger than 2^N, hence the dramatic increase in computational power for certain algorithms. It's difficult to come up with algorithms that exploit the large quantum state space but yield a deterministic (rather than probabilistic answer). In some cases, however, even probabilistic answers may be okay if the correctness of the solution can be verified quickly with a classical algorithm and the quantum computation re-run.

Re:Horrible

[bradgoodman]

So here's the way I understand it - or rather I probably misunderstand it:

.

Quantum Computing - because it stores superpositions of bits, which can represent all values, can work work on data with not just a single value, but with all possible values, thus doing stuff effectively in parallel

Before you stop reading - it gets better...

This is good for solving "what-if" problems - (which I think is technically described as "NP-Hard" - but I'm not positive) - or problems which can only be solved be trying any/every/a-shitload-of permutations, rather than figuring it out through an exact formula - like the "Traveling Salesman Problem" - or cryptographic analysis.

So for a crappy example: Suppose you were trying to figure out the square-root of 11 (and didn't know how, like me, and could only do it) by using successive approximation.

You would try "3" - which yields "9" - and then "4" which yields "16". So knowing it's between the two, you'd try "3.5" which yields "12.25" - then maybe "3.4" which yeilds "11.56", etc.

So if you were testing each variable "A", instead of setting "A" to be "3" or "4" or "3.5", "A" was a superposition of a bunch of numbers, you could somehow easily deduce which "A" was valid from a formula like "A*A=11".

I obviously don't know exactly what the mechanism is - and a better example would probibly be one which used a few binary digits (solved by using qubits) - which would have a finite range of possible solutions - rather than a floating-point number like I did in my bad example.

So - if you follow my train of thought - you could see how a cryptographic analysis problem which would require a lot of "what-if" quessing could be solved if all of the potential states of all of the bits could be instantly tested in parallel

Could anyone who understands this stuff chime in?

Highly recommended book

[AdmiralXyz]

Have to agree with the comments above, that article is pretty useless.

Coincidentally, though, at a university book sale a few weeks ago, I picked up a copy of N. David Mermin's Quantum Computer Science: An Introduction, for just $5 (seems to be about $30 on Amazon) and I can't recommend it highly enough. It's an intro to quantum computing textbook, about 200 pages, written specifically for people who have CS or math (as opposed to physics) backgrounds, and while it's almost impossible to get into the nitty-gritty of why quantum computing works without a lot of quantum mechanics esoterica, this book does a great job of explaining how it works (which is plenty complicated on it's own).

It's not a light read (it's a textbook, after all), and contains some serious math, but it's nothing someone with a college education can't handle and it really helped me understand this whole mess better than any popular news article.

Re:Highly recommended book

[blueg3]

Incidentally, from Mermin's website, you can download his lecture notes at no cost. The book is directly based on the lecture notes and, as far as I recall, the notes are pretty good. I took the class while he was working on the book, so all we had to work with was the lecture notes (which have since undergone some revisions), which were essentially a beta version of the book's text.

It should be reasonably understandable to someone with a good CS and mathematical background but limited physics background. (Likewise, it should be reasonably understandable to someone with a good physics background but relatively little CS.) The course was designed to be taken by both CS and physics students. I think it was fairly challenging for the Cornell CS undergrads that were in the course, but your mileage may vary.

Re:Wrong atomic picture in TFA

[blueg3]

It's also a picture of an atom that doesn't exist. Never mind that the electrons are enormous and have circular orbits. There are 2 of one kind of nucleon and 3 of the other kind, with 4 electrons that all seem to be in the same shell.

So, the two possible atoms are Lithium-5 (-1) or Helium-5 (-2). Both Lithium-5 and Helium-5 are highly unstable. Both of them should have two electrons in one shell and two in higher-energy shell. The -2 state of helium would be challenging to produce, to say the least.

Reality less clear than even this article seems

[Comrade Ogilvy]

As someone with a couple physics degree, I find this stuff both exciting and confusing. Exciting because delving into such fundamental physics is creating some beautiful results. Confused because either something is wrong with my understanding of quantum mechanics (unlikely), or we are being snowed with pie-in-the-sky promises, in order to secure funding.

Entanglement for secure channels of communication I believe. Quantum "computing" in the sense we usually think of computing looks phony.

Sure, such a quantum computer, if built, could process, say, 10^50 quantum inputs simultaneously. But where does one get the 10^50 inputs? Each input is a delicate quantum-entangled state. Do I pull my 10^50 helium-cooled quantum state composition machines out of my closet? It is a promise which is can only be employed by leprechauns and unicorns.

The bottom line is, as stated by the article, quantum computers would useless for most everyday computations. Which things a quantum computer could actually be used for is clear as mud.

I would welcome a link to a technical article that is grounded in reality, proving me wrong.

Re:One major mistake

[Bill, Shooter of Bul]

All theories are really just models of the universe, some work better and tell us more about how the universe does work. Quantum mechanics does tell us many very important things about our universe. Most importantly, and confusingly for everyone first learning it, our universe is not deterministic. Unlike dice, where we could predict with absolute certainty what the outcome would be if we collected enough data about the throw, we cannot do that in the quantum world. There are no "hidden variables" that we could use to increase the accuracy of our probabilistic predictions.

See bells theorem for more mind bending details.

Oh no, not again!

[maxwell demon]

From the article:

"This shared state means that a change applied to one entangled object is instantly reflected by its correlated fellows"

Why, oh why, is this nonsense repeated again and again. If you change one entangled particle, you do not change the other. For example, if you have two spins entangled in a way so that if one is measured "up" the other is measured "down" and vice versa, and you turn the one spin around (without measuring it) then you'll have an entangled state where if you measure the first spin "up" the other one is also measured "up", just as you'd expect. As long as you don't measure, there's no "spooky action at a distance" but only local changes. The "spooky action at a distance" happens at measurement (which BTW destroys the entanglement), and it's all but a given that there's indeed an action at a distance (you only need it if you want a certain type of interpretation, where basically "under the hood" the system behaves completely classical, but we don't see it because there are so-called hidden variables which we cannot determine). The point is that in an entangled state the correlation is all which is defined, and the result of local measurements are completely undefined (OK, strictly speaking this is only true for maximally entangled states, for others there's less correlation and more local information; it's basically a trade-off between the two). Now when you measure the spin of one of the particles, the value of the spin gets a defined (but random) value (up or down, in the direction you measure), and also the value of the spin of the other particle gets a defined value, which is determined by the entangled state and the result you got for the first particle, i.e. if the entangled state was "both particles have opposite, but otherwise undefined spin" then after measurement, the particles will have opposite, well-defined spin. However, since the result is random, if you have the other particle, you cannot see any difference whether the first particle has been measured or not; he will get a random result either way. Only if he gets told the measurement result of the first particle, he can predict (or, if he already measured, compare) his measurement result.

Oh, and yes, I'm working in the field of entanglement, so I know what I'm speaking about.

But I absolutely like the following statement from the article:

"Hang on, what's quantum entanglement when it's at home?
I was afraid you were going to ask."

I hope the above explanation is understandable ...

Re:It is very annoying that sentences start...

[maxwell demon]

The pages are entangled.

Re:Weather Prediction?

[Comrade Ogilvy]

Won't happen. While better computers help to some degree and building better models helps even more, weather is fundamentally a chaotic system. There is a hard upper limit based on the quantity and accuracy of the data. An exponential increase in overall quality of data yields a linear increase in the quality of the prediction.

To make up some numbers to illustrate the point...So if we have 10^4 weather stations to have 48 hours of good accuracy, it might take 10^5 weather stations to achieve 60 hours of good accuracy, assuming that you have all the computing power you could possible want in the first place.

Re:One major mistake

[Anonymous Coward]

Note that not everyone rejects hidden variables. Claiming that QM implies a non-deterministic universe because of the absence of hidden variables is in fact subtly wrong. The dominant interpretation of QM (which claims the nonexistence of hidden variables) *assumes* nondeterminism, it doesn't conclude it. You can find a complete quote on the Wikipedia page for Superdeterminism, but there was an assumption in the design of the EPR experiment that assumed non-determinism as a means of preserving the free will of the experimenters. In other words they mixed philosophy into science then got freaky weird results, and now most of their followers fail to consider the possibility of a causal link between the two.

Re:Are quantum computers Turing machines?

[maxwell demon]

The set of problems you can in principle solve with a quantum computer is exactly the same as you can solve with classical computers. The best proof of this is that you can simulate a quantum computer with a classical computer (and vice versa). However, as far as we know you cannot simulate a quantum computer on a classical computer in polynomial time.

Re:Are quantum computers Turing machines?

[FrangoAssado]

Quantum computers only offer better speeds; a quantum computer can always be simulated by a classical computer. However, storage and run time of the simulation grows exponentially with the size of the quantum computer being simulated, so this is not feasible in practice.

The reverse is also true. A quantum computer (when/if built) will be able to run any classical algorithm, since it's possible to implement a classical NAND gate using quantum gates. It'd be a huge waste, however, to use quantum gates this way.

Re:One major mistake

[u17]

I find non-determinism to be stranger. In a deterministic world, you can always ask what caused anything that you observe. In a non-deterministic world, you observe something, and apparently it happened without a cause, it could have just as well been one of several other outcomes. If you accept non-determinism, it's not free will that results, it's that your will is governed by random chance and not by cause and effect.