Baby Steps Toward Quantum Computers 308
Mz6 writes "In a step toward making ultra-powerful computers, scientists have transferred physical characteristics between atoms by using a phenomenon called entanglement, which Einstein derided as 'spooky action at a distance' before experiments showed it was real. Such 'quantum teleportation' of characteristics had been demonstrated before between beams of light. Teleportation between atoms could someday lie at the heart of powerful quantum computers, which are probably at least a decade away from development. Researchers using lab techniques can create a weird relationship between pairs of tiny particles. After that, the fate of one particle instantly affects the other; if one particle is made to take on a certain set of properties, the other immediately takes on identical or opposite properties, no matter how far away it is and without any apparent physical connection to the first particle." Reader starannihilator adds: "Physics Web provides a good graphic summary of the phenomenon, as well as a good technical article."
Re:Umm...this is old news. (Score:5, Informative)
Re:Analogue vs Digital (Score:5, Informative)
Regards,
Steve
Re:Analogue vs Digital (Score:3, Informative)
With n quantum qubits, they can be any normalized (overall phase doesn't matter) complex vector in 2^n dimensions.
However, when you measure them, the wave-function will collapse (unless you believe in the many world's multiverse), and you'll get n classical bits.
Classical information is simply a subset of quantum information.
Re:How to choose? (Score:3, Informative)
Re:can someone qualified answer this question (Score:4, Informative)
However, there still exist quantum error correcting codes that can correct an arbitrary error. Classically, one only gets bit flip errors. In quantum computation, you have to worry about phase flip errors, for instance instead of a|0>+b|1> you have a|0>-b|1>.
The smallest quantum code that can correct an arbitrary non located (located errors are easier) error on 1 qubit requires 5 qubits. There's a 7 qubit "CSS" code that is important for fault tolerance.
For fault tolerance, you concatenate a code with itself many times, and if your errors are independent of each other, then by doing all sorts of complicated fault tolerant techniques, you can get fault tolerance. What happens is you get a fault tolerance threshold. If your rate of errors are less than that, you can do arbitrary quantum computation with O(M) qubits in O(N polylog N) time, where O(M) is the qubits required on an error free quantum computer, and O(N) is the time required on an error free quantum computer.
Re:Umm...this is old news. (Score:2, Informative)
Stupid 2 minute rule.
Re:Not quantum computing, but (Score:5, Informative)
The problem is, we have no way to choose what state the particles will go into when we observe one. Its a random outcome, and you can't acheive any communication if the output is just random noise.
Furthermore, from the spaceship's viewpoint, how do you tell if your particle's state has changed due to an incoming transmission? The only way to know would be to observe it. But, we don't know if that particle had been observed by Earth yet. If it had, then we just disturbed the state that Earth had set. If it hadn't, then we just forced it (and Earth's particle) to a random state. True, the Earth's particle will now be set to the same random value, but random values are still uselss for communication.
For it to work, you'd need a second channel of information, which could transmit some kind of key to decoding the random states into data. Of course, this channel of information would have to go FTL too, so its a Catch-22...
Re:Analogue vs Digital (Score:3, Informative)
The best way I have found to think about quantum computations is that digital computers think in 1's and 0's
Quantum computers allow you to ad "decimal places" to this traditional logic (0.1, 0.2, 0.9, 1.0). As you increase the number of quantum bits, instead of just increasing the number of calculations a second you can do (like with our processors today) you are in fact adding new more "decimal places" by simply looking at the qubits in terms of accuracy. Even a simple quantum computer of 30 or 40 qubits could theoretically out power any single processor today depending on the quantum accuracy involved.
Medevo
Re:How to choose? (Score:3, Informative)
Faster Than Light Communication (EPR) (Score:2, Informative)
Re:can someone qualified answer this question (Score:5, Informative)
Quantum error correction. [qubit.org] is a sub-field of quantum computing concerned with just that, how to effectively perform a quantum computation in the presence of background radiation and other stuff which sub-atomic thingies tend to be quite sensitive to.
The likelyhood of flipping a few zeros and ones ( and other errors which can afflict quantum bits) is very high, and in reality is more a continuously decay than an instant flip.
It has been shown, however, that this continuous decay is equivalent to flip errors and phase errors (the other sort of quantum error) occuring with some probability. That probability is 1 in 10 for most of the current experiments, compared to your box in front of you which is more like 1 in 10 billion.
Fault-tolerant quantum computing is a theory field of research concerned with how good quantum computers have to be before quantum error correction can work. The best results at the moment suggest a probability of error of 1 in 1000 is good enough. The experimenters have a fair ways to go yet.
Re:Analogue vs Digital (Score:5, Informative)
Moreover, at the end of the day, you still extract bits from qubits. While one day in the distant future we may be able to interact computers entirely in a quantum environment, but it's a long way off.
The real potential in quantum computers is the problems of density, power, and heating, that have plagued development of faster CPU's seem to apply on a lesser scale to quantum circuits (not that they don't have there unique problems). At the same time, quantum computers could/would suffer a lot less problems with bandwidth/time delay (light/QE info transfer).
Traditional MOSFET based transistors, while powerful (look at today's advanced chips) have been around for a while; there is no harm in looking for something new and better.
Even if quantum computers provided a liner growth curve in processing power to qubits, we could expect a greater throughput in it (due to above stated factors).
Medevo
Re:can someone qualified answer this question (Score:2, Informative)
Re:Analogue vs Digital (Score:5, Informative)
Generally, a quantum computer consists in several quantum systems (for example captured particles, etc). The (quantum) state of these systems varies according to a well-known equation, called the Schrodringer equation. This is a very simple equation that describes the evolution of the system (the derivative of the current vector state) in respect to the current current state & time.
The nice thing about quantum computers is that they operate with multiple simultaneous states, therefore achieving some sort of parallelism. Basically a quantum system can be considered to have a superposition of states - it has two states at once if you want. Some of these states might converge to the same state depending on the hamiltonian or on the external interactions.
The hard part is that you never know when such a computer stops its calculation since the transformation state is fully reversible and goes on ad infinitum. If you want simply to test if the computer reached the end of the calculation, you will affect the current state. Anywyay, this challenge plus many others (for example the precision of the measurement, etc) makes quantum computing very challenging.
Still, there is a theoretical possibility that you can get a high degree of parallelism in certain configuration. A classical result from Shor (you can search on Google) shows that one of the classic problems in arithmetic - integer factorization - can be done in a polynomial time on a quantum computer. This simply means that RSA encryption can be potentially broken, irrespective to the length of the key. But we are still safe - so far nobody built a working quantum computer that would carry on simple calculations like factorizing the number 15.
On the other side, entanglement is an interesting quantum fenomenon which works like this:
1) First, you have to have a way to build pairs of entangled particles. There are several ways to do this, for example by having any quantum process that generates a pair of photons.
2) Second, if you modify the vector state of one particle, the vector state of the other one will be equally affected, regardless of the distance between these two particles!
What's interesting is that entanglement guarantees instantaneous quantum state change therefore contradicting somehow the theory of special relativity. This theory says that events cannot be 100% simultaneous if they occur in different points in space - there is a timing separation based on the particular reference chosen. Practically, no standard matter interaction can be faster than the speed of light.
But there is an exception here - "collapsing the vector state". If you measure the state of a particle, its state will collapse along one of the measured dimensions (according to certain probabilities). The corresponding entangled particle will suffer a similar change, so if you measure now the state of the this second particle you will see that its vector state has already changed - and you can even perform a partial correlation between the results of the two measurements.
In conclusion, enanglement guarantees instantaneous "interaction" regardless of the distance between these paired particles (this is why Einstein called it "spooky action at a distance" - because technically it is propagated with infinite speed). Anyway, it has be proven a while back that this does NOT contradict the special theory of relativity since this is not a standard matter interaction, like gravity, etc.
Going back to computers, entanglement is an interesting approach which might enable new algorithms or new ways to build such computers. But keep in mind that we are in the stone age of quantum computing right now...
Re:A method to break Quantum Encryption? (Score:2, Informative)
This follows from 2 facts
1. Quantum measurements can be replaced by quantum gates
2. Quantum gates preserve the inner product of two states.
Re:Analogue vs Digital (Score:4, Informative)
You're right, though, that it's about as secure a communication channel as you can get. It's actually the basis for quantum cryptography -- two people share a set of entangled photons, and they can guarantee that the measurements they make on them will be identical, giving them a shared secret key that no one can intercept. They still have to communicate over regular channels to actually send any real information, though.
Argh!!! NOT teleport, NOT affects. (Score:5, Informative)
4 times in the post it was said that the particles teleport or communicate, they don't.
Its more like the particles are using the same day planner to decide what to do next.
Think of it like to processes running the same code. if they have the same inputs, they will have the same outputs. It doesn't mean they communicate or teleport.
The reason it bugs me so much when people talk as if the particles interact after they have been entangled is it leads someone sooner or later to start asking why we can't use that to beat the speed of light for communication, or a dozen other things that have nothing to do with entanglement.
Re:can someone qualified answer this question (Score:5, Informative)
Would you really think even a e-machine is that error prone?
Think about it...
2.5 Ghz * 32 bits/cycle = 80,000,000,000 - that's 80 BILLION bits per second...
Of course, that's theoretical, there's buffering delays, cache, noops, etc. But, given the theory, there'd be 8 random errors every single second.
Something doesn't sound quite right, here, especially when you figure the vast majority of computer are sold with no error correction at all on the system memory ?
I think that 1 in 10 billion is probably quite a few orders of magnitude off....
Re:Communication! (Score:3, Informative)
Re:How do you measure spin? (Score:2, Informative)
Re:Answers anyone?? (Score:3, Informative)
When two particles are in an entangled state, it means that an observation of one counts as an observation of the other as well. That can be interpreted as information traveling instantaneously from one particle to the other. Lots of people have gotten wacky ideas because of this. However, the information that "travels" between the particles is random, and cannot be used to send information. Bear in mind that it's not the change of spin that is communicated between the two. It's the measurement of the spin, and it only works once, and only if you've managed to maintain the entangled state while you separate the particles.
The unfortunate fact of the matter is that no known phenomenon can be used to transfer information from one place to another faster than light can travel between them. It's not a matter of technical hurdles that must be overcome. It's a matter of fundamental limitations in the way the universe works.
TTFN
Re:This... (Score:3, Informative)
[*] for 2-state particles (simplest case), the measurement of the unknown+transmitter system has 4 possible outcomes, so the receiver can be in one of 4 states in a 2d space => non orthogonal, there's no measurement that will preserve all of them simultaneously, hence there's no knowing whether you destroyed the state or not by only measuring the receiver.
Re:Yes, fast (Score:5, Informative)
The main property that classical computers lack is that of superposition of states. One can understand this as calculating some result starting with all possible numbers at once, instead of testing each starting value as its own. (In reality it's more complicated than this, of course.)
Some applications, eg. codebreaking, number crunching and database applications could get a vast boost out of quantum computing. Other applications may not. The most probable places for quantum computers (at first) will probably be number crunching, networking applications (quantum cryptography etc) and database applications.
For a comparison, searching an unsorted database is classically an O(N) operation, but a quantum computer can do this [wikipedia.org] in time O(sqrt(N)). The best known classical algorithm for factoring a number is exponential, while Shor's algorithm [wikipedia.org] does it in time O((log N)^3) (allowing polynomial-time breaking of RSA).
Re:Not quantum computing, but (Score:3, Informative)
Re:Faster Than Light Communication (EPR) (Score:3, Informative)
Not quite.
You're correct that quantum teleportation will transfer a quantum wavefunction from one point to another. But it cannot 'copy' the wavefunction. In order to send the wavefunction, the original wavefunction must be destroyed during the process.
Sorry, fanout is strictly prohibited in quantum computing.
Re:Analogue vs Digital (Score:5, Informative)
This has two consequences:
1) First, it is practically possible to use entanglement to build networks that are 100% guranteed to transmit either correct information or error.
2) Second, since measuring any particle will necessarily change it state gives an interesting conclusion: it is impossible to tamper the communication channel that transmits entangled photons. As soon as you attempted to measure what's on the channel, the verification mentioned above (i.e. the correlation between the final measurement of the two entangled particles at the two ends) will fail!
Therefore you have a bullet proof method that will prevent active/passive attacks on the entangled channel. The technique was actually employed in practice - see this link [itworld.com] for example.
NB - this technique still doesn't prevent attacks that fully substitute one of the ends with a completely identical device so the other end still thinks it is talking to the right person. But in combination with standard cryptography techniques for the insecure channel, this techniue is almost impossible to break. A nice overview is presented here [paperin.org]
a classical information channel must be involved (Score:1, Informative)
http://en.wikipedia.org/wiki/Quantum_e
Re:This... (Score:3, Informative)
A lot of people misunderstand the nature of entangled pairs as a result of the fact that many reporters do not understand how they work. An entangled pair is just a pair of qubits set up in a quantum state so that there is a 50% chance they will both be 0 and a 50% chance they will both be 1 (this is an oversimplification, but it's still better than how they are usually explained). If you measure one half of the pair, you automatically know what will happen when you measure the other one.
Re:can someone qualified answer this question (Score:1, Informative)
For trapped ions, the dominant causes of poor fidelity are heating of the ions in the trap by surface potentials and spontaneous emission induced by the laser beams used to produce the Raman transitions between different internal states.
There's a long way to go to 100% fidelity!
Re:Analogue vs Digital (Score:3, Informative)
There is no equvvalent macro phnenomenon for quantum teleportation. But let me try this example.
Quantum teleportation is something like this..
If you have a metal box that can be broken into two metal boxes. Initially there are two colored balls in the metal box. You cannot see the balls. When you break the box into two, each ball stays in one box. You can now seperate the box by a large distance. This pair of boxes is similar to entangled pair. By obeserving the first box, you can determine the color of ball in the second box.
At the quantum level, without knowing the color of the ball, it is assumed to be in a state of superposition. so Observing the first photon forces the state on the second photon.
Re:Help me understand this! (Score:4, Informative)
This is confusing. You talk about things "changing" and looking in the box to see the "contents" beforehand. In the entangled state, the boxes have no "contents" to speak of, only superposed wavefunctions. By observing what is inside the box you collapse both the superposition and the entanglement.
You are asking, how can you know definitively that, before you open one of the boxes, there indeed exists an entangled superposition inside the boxes. You cannot know this. If you open a box to observe the contents, you will never observe a quantum superposition (that would be an absurdity -- it would cause your brain to enter a superposition as well. What the heck would that feel like?), you instead cause the objects to collapse to a well-defined state.
It makes no sense.
Quite right :-) But in some way, it's all connected with consciousness and observation. It seems like our consciousness is always in a well-defined state, and this "rubs off" on whatever we observe, causing any superpositions to collapse. And even if our brains did enter some kind of superposition, would we know it? Would we perceive the superposition, or would we be two superposed people, each observing what he thinks is a well-defined state?
These are questions we probably won't have answers for for a long, long time.