Slashdot Mirror

In other words, a four-qubit computer may be nearly useless except for very specific problems; but if it was part of your desktop computer, it would give it a large boost in all sorts of power.

Not really; a four-qubit quantum computer can be simulated very fast in today's computers. It would be completely useless for any practical purpose (unless quantum computer fabrication technology improvements become ridiculously better than improvements on classical computer fabrication technology for an extended period of time).

To simulate the evolution of an n-qubit quantum computer all you have to do is (essentially) multiply a vector of size 2^n by a series of 2^n-by-2^n matrices whose entries are complex numbers; each matrix multiplication represents one step of the algorithm you're running. There are, of course, many optimizations that can be done depending on the type of algorithm you're running. (Here is a nice list of quantum simulators.)

Because the size of the vectors and matrices grows exponentially (2^n) with the number of qubits, simulating a quantum computer with a classical computer becomes impractical even for a moderate size. For very a very small number of qubits, though, it's completely reasonable.

That said, the rest of what you said seems right. Even though it would be possible to run classical algorithms in a quantum computer (i.e., quantum computers are Turing-complete), it would probably be an enormous waste of resources to use quantum computers that way. Unless, of course, quantum computer fabrication technology improvements become ridiculously better, etc.

How would one read the output of a quantum computer if they quantum state changes upon observation? Wouldn't it just spit out random numbers?

One term to google for is decoherence.

The two paragraph wikipedia answer is at:

http://en.wikipedia.org/wiki/Quantum_computer#Operation

The multi-page answer at quantiki is at:

http://www.quantiki.org/wiki/Basic_concepts_in_quantum_computation#Decoherence_and_recoherence

My crappy slashdot car analogy is the internal state of my car is almost infinitely complicated, O2 sensor levels and thermostat bypass fractions. But you could theoretically compute an algebraic equation that boils down to can I drive 400 miles on a tank of gas? The answer at the end is, is the engine running or not, just one binary bit. All the hidden internal variables and states, zillions of them, like coolant temp, O2 loop state, etc, all collapse down to one bit. Its not really important what the internal state is when the engine shuts off, or if it shut off because the O2 loop leaned out of spec, or the fuel pump control loop when haywire when it sucked air, or...

So, a 1024 qubit computer has 2^1024 internal variables all of a vaguely analog complex number value, and those 2^1024 values collapse down to a mere 1024 bits when you factor my RSA key... There's a darn near infinite number of possible values that collapse down to 1024 bits and you randomly get one of them.

You're absolutely right about the impossibility of transmitting information FTL using quantum entanglement, but I have a small nitpick about this:

It is effectively the same as writing a random number down on two bits of paper.

It's effectively the same if you're only talking about the ability to send information FTL; but not when talking about other things (like channel capacity). For example, you can use entanglement to double the capacity of a classical channel:

http://www.quantiki.org/wiki/index.php/Enhancement_of_channel_capacities_with_entanglement

(and also http://en.wikipedia.org/wiki/Superdense_coding)

This could never be done with the two bits of paper.

Your terminology is slightly off. Qubits can have an infinite number of possible states. 0 and 1 are called the basis. Also, a qubit is considered to be in a "pure state", not only when it's in a basis state, but also if it is in a superposition of the bases. A mixed state is something completely different. It occurs when we don't know exactly what pure state, so the state is represented by the sum of the possible pure states weighted by the probability of the qubit being in that state. http://www.quantiki.org/wiki/index.php/Mixed_state

What is your favorite entanglement measure?

1. Negativity
2. Entropy
3. Concurrence
4. Measure of what?

No mention is made of Schroedinger, whose "cat state" they were alluding to. Einstein never made any "theory" about producing cat states. The EPR paper didn't really have anything to do with Schroedinger's Cat and quantum superposition of macroscopic objects, but rather the paper attacked QM on the grounds that it was not a local-realistic theory. One has to break at least one of those two assumptions about the physical world in order to get the answers that QM produces (and is supported by experiment), this result was proven by John S. Bell in the 60's using his (should be) famous Bell's Inequalities.

Schroedinger wrote his famous paper describing quantum entanglement and naming it for the first time after reading the EPR paper, and saying that entanglement was the "defining feature" of quantum theory. The paper also introduced his famous cat. Wigner extended the Gedanken experiment by introducing "Wigner's Friend" who had to look inside the cat box, and thus also becoming placed into a superposition, this time simultaneously seeing both a dead and alive cat. Both Schroedinger's Cat and Wigner's Friend have very little to do with the EPR paper.

Einstein was one of the people involved in developing quantum theory, but Planck, Bohr, Heisenberg, de Broglie, von Neumann, etc who were more instrumental in its development weren't even mentioned. Einstein was very antagonistic towards QM, even after it had been extremely successful at describing physical systems and experimental results. He never really exactly thought QM wasn't right, just not complete in the local realistic sense. To the theorist, such experiments demonstrating the existence of cat states are simply to be expected, we'd be so much more surprised (and excited actually) if the experiments indicated something other than what QM would predict. To satisfy the ardent Local Realist, the Holy Grail is the Loophole Free Bell Test (close the efficiency/fair sampling, locality, random choice loopholes all simultaneously). That'd be a definitive experiment to finally nail the lid on the Einsteinian Realists, but for the majority of physicists, we'd hardly care because it's almost taken as given that the results will simply support QM and not local realism.

In the end, Nature is the final arbiter, and if QM predicts the results of experiment better than any other conceivable theory, then our bets should be on QM. There have been no compelling experiments to indicate that QM is anything other than correct, save the fact that it needs to somehow mesh with GR at some energy/length scale.

Joel Bloggs
http://www.quantiki.org/

References
http://cam.qubit.org/users/matthias/Entanglement/E ntanglement.php