## Significant Advance in Quantum Computing 180

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.
## Phew (Score:5, Funny)

## Re:Phew (Score:3, Funny)

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 (Score:2)

## Re:Phew (Score:2)

neitherbrokennorworking? 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 (Score:5, Interesting)

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 (Score:5, Informative)

"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 [technologyreview.com]

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 (Score:5, Interesting)

"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 (Score:4, Informative)

## Re:I'm not a quantum engineer (Score:1)

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 m

## Re:I'm not a quantum engineer (Score:5, Insightful)

... 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 (Score:2, Informative)

## Re:I'm not a quantum engineer (Score:3, Interesting)

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 (Score:3, Informative)

## Re:I'm not a quantum engineer (Score:5, Informative)

## Re:I'm not a quantum engineer (Score:2)

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 proba

## Re:I'm not a quantum engineer (Score:2)

=Smidge=

## Re:I'm not a quantum engineer (Score:3, Informative)

## Re:I'm not a quantum engineer (Score:4, Informative)

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.

## sounds like rainman autistic computer.... (Score:2)

## Re:sounds like rainman autistic computer.... (Score:4, Interesting)

## Re:sounds like rainman autistic computer.... (Score:2)

I read an article about 5 years ago that said that the human brain

doestake 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.... (Score:2)

## Re:I'm not a quantum engineer (Score:2)

## Re:I'm not a quantum engineer (Score:2)

## Re:I'm not a quantum engineer (Score:2)

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

NPproblem 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.## this is dead wrong (Score:3, Insightful)

## Re:Are you sure? (Score:2, Informative)

## Sorry, but this is wrong (Score:3, Insightful)

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 thin

## Re:I'm not a quantum engineer (Score:2)

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 (Score:2)

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 (Score:3, Funny)

## This isnt right either.. (Score:4, Insightful)

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.

## Re:I'm not a quantum engineer (Score:5, Informative)

## Re:I'm not a quantum engineer (Score:5, Informative)

## Re:I'm not a quantum engineer (Score:2)

## We already know what they will look like (Score:5, Informative)

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 (Score:2, Informative)

## Re:I'm not a quantum engineer (Score:3, Informative)

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 b

## Re:I'm not a quantum engineer (Score:2, Informative)

## Re:I'm not a quantum engineer (Score:2, Informative)

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

## And the winner is... (Score:5, Funny)

No fair! You changed the outcome by measuring it!

## Re:And the winner is... (Score:2)

## Re:And the winner is... (Score:1)

## I'm guessing... (Score:3, Interesting)

## applicable quote (Score:5, Funny)

## Related Quantum News: The Slashdot Effect (Score:5, Funny)

Von Neuman's Catastrophe, namelyThe Slashdot Effect. This effect makes it impossible to bothlinkto the story from Slashdot andreadthe 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 problemCommander Taco's Catastrophe...## Not so soon, may be never (Score:5, Informative)

Quantum computing: a view from the enemy campQuantum 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

## Religious implications (Score:1)

## Re:Religious implications (Score:4, Insightful)

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

## Re:Religious implications (Score:1)

## Because it is insightful (Score:2)

the gods of each civilisation were a by product of those civilisation's history and social environement## And a Beowulf Cluster wiped out my credit card (Score:1)

## What's the point? (Score:3, Funny)

"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? (Score:1, Insightful)

accurate video game physics down to the quantum level

## Re:What's the point? (Score:2)

"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 th

## Re:What's the point? (Score:4, Insightful)

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? (Score:2)

(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 "a## Re:What's the point? (Score:2)

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 s

## Re:What's the point? (Score:3, Interesting)

"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 rea

## Re:What's the point? (Score:2)

## Re:What's the point? (Score:2)

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 break## Re:What's the point? (Score:2)

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 m

## Wishful thinking. (Score:1)

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

## Re:Wishful thinking. (Score:2)

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. (Score:1)

## cray icon (Score:2, Informative)

## Serious question. (Score:2)

## Re:Serious question. (Score:3, Insightful)

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.

## Booor-ing... (Score:5, Interesting)

Instead, Tien Kieu [arxiv.org] from my university wants to solve arbitrary Diophantine equations [wolfram.com] 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:

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... (Score:5, Informative)

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.

## More to it than that... (Score:4, Interesting)

You've got it in one. According to Kieu, his system is a non-computable process; you

can'tsimulate what it does on a Turing machine. Hence your objection doesn't apply to his claims.However, there

areapparently lots of other objections.## Re:More to it than that... (Score:2)

## Re:Booor-ing... (Score:3, Interesting)

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. Tha

## Re:Booor-ing... (Score:2)

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 tim

## Re:Booor-ing... (Score:2, Informative)

## Re:Booor-ing... (Score:2)

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

## Re:Booor-ing... (Score:2)

## Unsolvable with a *classical computer* (Score:2)

Now, the Church-Turing thesis says (roughly) that

anycomputational 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 mathemati## Re:Booor-ing... (Score:2)

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

## Is it just me (Score:2)

## At last! (Score:2)

NowI can sleep.## Wouln't it more likely be... (Score:2)

## Time issues in quantum theory (Score:2, Interesting)

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

Also,

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 [psu.edu] (talk by Roger Penrose [psu.edu]).

## Here's another question (Score:3, Interesting)

Just curious.

--Ryv

## Re:Here's another question (Score:2)

No. This is one of the consequences of the No Cloning Theorem [wikipedia.org], 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 any

## Where's my ansible? (Score:2)

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

## Re:Advances? (Score:1, Funny)

## Re:Advances? (Score:5, Insightful)

## Re:Advances? (Score:2)

## Re:Advances? (Score:2)

## Re:Advances? (Score:1, Insightful)

## Re:Advances? (Score:4, Insightful)

## Re:Advances? (Score:1)

## Re:first post for quantum computing (Score:1, Redundant)

## Re:Nice cray icon (Score:1)

## Re:Quantum Logic (Score:1)

## I had a French Arabic math prof... (Score:2, Funny)

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:Quantum computing isn't the holy grail (Score:2, Funny)

"Well if quantum computing can exist maybe that other stuff is true too . . ." R

## Re:Quantum computing isn't the holy grail (Score:5, Informative)

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 processclassical 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

ama quantum physicist (although I don't work on quantum computing).## Re:Quantum computing isn't the holy grail (Score:2)

Also under the first links is http://www.qubit.org/library/intros/comp/comp.html [qubit.org], 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 [york.ac.uk] looks good.

And if you can't wait to program a QC, then you might be interested in QCL [tp],