Yes, the decoherence time may be awful if you are using exitonic states or if you are trying to use the orbital states of the electrons, but it may (hedge) not be true for the spin degree of freedom for the electrons.
TeX (and it's idiot bastard progeny, LaTeX) are a prime example of all that is kludgy, evil and stupid about the Unix world.
Tell that to xxx.lanl.gov: have you seen how much research is posted to the e-print archives!? Almost all of it was written with LaTeX.
Like you say at the end, LaTeX is good for mathematicians (physicists, etc.). I'm of the humble opinion that, FOR SCIENTISTS, LaTeX rocks. What's funny is now, when you send email to some collaborator talking about such and such an equation, everyone uses LaTeX commands.
The Turing Machine is an abstraction, a "thought experiment." What it did was prove mathematically that, once you pass a certain very low level, ANY computer is equivalent to ANY OTHER computer
Except that nowdays we realize that information is physical and thus the lowest level machine that can simulate all algorithmic tasks isn't a classical Turing Machine, but is really a quantum mechanical Turing Machine!
What you've stated is known as the Church-Turing thesis: a universal Turing machine completely captures what it means to perform a task by algorithmic means. And, really, in no way has anyone ever been able to "prove" the Church-Turing thesis: it was more like an emperical fact until quantum computing realized otherwise.
While classical Turing machines can simulate quantum mechanical Turing machines, it appears that they cannot due this efficiently. This means that we shouldn't base our idea of an algorithm on what a classical Turing machine can do, but instead on what a quantum Turing machine can do.
viva la Quantum computation
(sorry, just watched the South Park movie last night)
dabacon
I wonder how many people learned to program by chasing the inevitable bugs in transfering programs from Computes!s Gazette to computer? Thats how I learned to program.
Anyone ever get sick of this guys "arguement by Einstein". Because, of course, Einstein was always right (do the words "static universe" mean anything to you?) Not that I think that Einstein wasn't a man of amazing genius (I mean both special AND general relativity, come on, you've got to be kidding!), but I'm not such a great worshiper of the "older" Einstein.
Yes, the world could be made of cheese. But I prefer to think that the many generations of millions of scientists have got closer to the truth when they told me the world isn't made of cheese. (Feynmann probability 99.99999%)
1. Quantum computers can do things more efficiently that the classical computer you have in front of you. One word: economic considerations!
2. Quantum cryptography is a secure way to distribute random keys.
3. We don't really understand why quantum information possesses different computational properties. Researchers have some decent intuition about quantum algorithms, but it is such a new field that no one really knows where boundaries between the power of quantum and classical information lies. Of course the goal of science is to understand such questions as "what makes a quantum computer more powerful" and who knows what interesting insights about (1) computation, (2) physics will arise from quantum computation?
As to your second question: there is a ton of money being spent on building an actual quantum computer and there are more than half a dozen different proposals for such machines. Some examples of these models are using traped ions, neutral atoms in optical lattices, single electron spins on quantum dots, and much more.
And when you think the press to impact on society ratio is too high just remember good old Lord Kelvin:
"Heavier-than-air flying machines are impossible." --Lord Kelvin, president, Royal Society, 1895.
You must realize that the decoherence mechanisms which occur at the event horizon probably does not have a symmetry that can be exploited. I mean the only people who write if you're so smart are the people who already know the answer, right? lmao
OK, being as I am a reasearcher who has done work on decoherence-free subspaces (DFSs...they are also known as quantum error avoiding codes or noiseless subspaces...damn nomenclaturese) I thought I'd give all you netadmins a real simple explanation of what a DFS is. Of course, being a simple explanation, it will fuzz over a bit. But I thought I'd at least try!
Suppose you are trying to send some bits down a noisy communication channel (sending an email from Timbucktoo to Weed, CA). Now the noise will cause the bits that you send on one end of the line to sometimes come out different on the other end of the line. Many of you know how we get around this in real world situations: we use error correction. The basic idea of error correction is to use redundancy to transmit information. Thus, for example, instead of sending the bit 0 you might send ten 0's and instead of sending the bit 1 you might send ten 1's. If the channel isn't too noisy then the reciever can figure out what bit you ment to send by looking at the ten bits he recieves and deducing if of those ten more are 0's or 1's. Basically you can reduce the noise rate of information transmission at the cost of increasing the number of bits you need to send in order to transmit one bit of information. (Sorry for those of you who know this shit like the back of your hand).
Decoherence-free subspaces work on a similar "encode the information" (i.e. 0->ten 0's, 1->ten 1's), but they "use symmetry" to protect the information.
Suppose that after extensive testing of the phone line you are using you notice that if you send two bits down the line in rapid sucession the line either does nothing to these two bits or flips both of them. Thus for example, if you send 00, the reciever always gets either 00 (no error) or 11 (error!) and if you send 01, the reciever always gets either 01 (no error) or 10 (error!). Your phone line has a symmetry! How do exploit this symmetry?
Well, what you do is simply encode the information you want to send into the parity of the two bits. This simply means that if you want to send 0 down the line, you send 00 (or 11) and if you want to send 1 down the line, you send 01 or (10). Now the noise can flip 00 to 11 (or vice versa) but it cannot change 00 to 01. Thus the you can perfectly recover the information you sent down the line regardless of an error occuring. What is neat about this is that it doesn't depend on the strength of the noise (the probability that an error occurs, for example). By using the symmetry of the noise you can avoid the noise completely! Symmetry=>protection.
What I've explained to you is an example of a decoherence-free subsystem (a generalization of decoherence-free subspaces, but the same basic idea) in the real "classical" world. To build a quantum computer we need to deal with similar problems but in the "quantum" world.
When Peter Shor (quantum computing god) invented a quantum computing algorithm for factoring (the one that breaks RSA), one of the main problems in actually implementing such a computer was quickly understood to be noise. Noise in quantum system is called decoherence (at least by me) and is much more nasty than the classical noise you get when (say) you are talking on your cell phone. The problem with quantum systems is that if they interact with external systems they completely lose their quantum nature. And making this problem even harder, whenever you observe a quantum system it also loses its quantum nature.
But following his work in discovering the factoring algorithm, Peter Shor noticed that he could do error correction on quantum systems to avoid this decoherence problem (hence Peter Shor=quantum computing god). A huge host of people then developed the theory of quantum error correction which showed that the decoherence problem could be overcome. This is probably one of the most amazing new ideas of the past decade: that quantum information can be in principle be sheilded from its environement by suitable error correction.
Anyway, decoherence-free subspaces are like quantum error correction in that you encode quantum information, but they, like the example above, use the fact that often noise has some sort of symmetry. Think about it this way: decoherence of a quantum system is like you looking at the system (you are interacting with the system!). But say you have two atoms which are so close together to each other that you cannot distinguish atom A from atom B. Then there is a symmetry in the way in which observe the system: you cannot distiguish that atom A is on the left or if it is on the right. Such a symmetry can then be shown the produce encodings of information which are protected from your observation!
Ah well, I had to try. Thanks to anyone who made it this far without "man I want to kill this dork" thoughts.
Wait: you mean you don't buy the logic behind "arguement by anecdote"?
Judging by the amount of such logic I find in the majority of newsprint I'm beginning to wonder if journalists are actually taught this type of reasoning in journalism school.
Dave "I don't even believe anything I write" Bacon
God I hate articles like this. I would be even more blunt (and yes IAAQCR I am a quantum computing researcher): using a single electron to encode information is EXPONENTIALLY COSTLY and hence PRACTICALLY USELESS.
Storing k bits of information in the wavefunction of an electron will require resources (energy expendature for example) which grows like some constant to the power of k.
Of course one can store an infinite amount of information in a real number (say the length of your big toe), but the cost of measuring that length becomes exponentially prohibative as you acquire more digits of accuracy.
You could think of this as the "lets make storing and retreval of data an NP complete problem" solution.
dabacon
famous computer science conjecture: N does not equal 1.
Something within me just revolts at the site of this getting press at such a preliminary stage. From your post, I'm guessing that the CERN had to present their "possible Higgs" data in order to get the extra time needed to explore this lead further.
But if the data is as sketchy as you say, why in the world did the press pick this up?
This reminds me of a few years back when I heard on the radio that "room-temperature" superconductors had been discovered. I was so excited I almost drove off the road, only to find out later that it was just a bad case of the press picking up an early result which later proved incorrect. Doh!
Not quite right. Quantum computers don't "explore every possible key immediately".
What quantum computers can really do efficiently is to factor numbers efficiently. This is DIFFERENT from exploring all of the keys simultaneously. If this was how a quantum computer worked, then quantum computing would have an even greater impact on the world...it would easily imply that quantum computers can solve NP complete problems efficiently. As of today, to my knowledge, no one has shown how to solve an NP complete problem efficiently on a quantum computer.
Careful, the fact that quantum computers can efficiently factor (or compute the discrete logarithm) is seperate from so-called quantum key distribution. i.e.
1. If you build a computer based on quantum information, it can factor numbers efficiently and hence compromises crypto schemes like RSA.
2. If you build a communication line which uses quantum information to distribute a key for cryptographic purposes you can guarantee security of the key distribution (i.e. if someone is spying you WILL know this).
I'm sure everyone who has an ounce of intuition can postulate that these two are related, but to my knowledge, no one has every shown a connection between the two.
I recently saw a paper in which the author demonstrated an extension of the quantum computing factoring algorithm to "other hard number theory questions". How odd that nature has provided us with a way to become superb numerical geniuses!
Is it really true that it would render ALL crypto schemes unbreakable? I don't think so.
For instance, there are crypto systems based on the difficulty of solving an NP-complete problem. So far, no one has been able to show (and many researchers do not beleive) that quantum computers can efficiently solve NP-complete problems. As I understand it, crypto systems based on NP-complete problems are rather inefficient (as opposed to say RSA) and this is the main reason why they are not in widespread use.
That withstanding, I wouldn't hold your breath for Intel coming out with its first quantum computer soon: building a quantum computer looks to be one of the grand technological challenges of the 21st century.
Oh yeah, quantum computing people really hate it when they are mentioned in the same breath as DNA computing and optical computers....the speedup due to quantum computers should be thought of as more of a software speedup (i.e. faster algorithms) not as a hardware speedup (i.e. basic circuitry more efficient).
Slashdot Mirror
Yes, the decoherence time may be awful if you are using exitonic states or if you are trying to use the orbital states of the electrons, but it may (hedge) not be true for the spin degree of freedom for the electrons.
dabacon
TeX (and it's idiot bastard progeny, LaTeX) are a prime example of all that is kludgy, evil and stupid about the Unix world.
Tell that to xxx.lanl.gov: have you seen how much research is posted to the e-print archives!? Almost all of it was written with LaTeX.
Like you say at the end, LaTeX is good for mathematicians (physicists, etc.). I'm of the humble opinion that, FOR SCIENTISTS, LaTeX rocks. What's funny is now, when you send email to some collaborator talking about such and such an equation, everyone uses LaTeX commands.
dabacon
The Turing Machine is an abstraction, a "thought experiment." What it did was prove mathematically that, once you pass a certain very low level, ANY computer is equivalent to ANY OTHER computer
Except that nowdays we realize that information is physical and thus the lowest level machine that can simulate all algorithmic tasks isn't a classical Turing Machine, but is really a quantum mechanical Turing Machine!
What you've stated is known as the Church-Turing thesis: a universal Turing machine completely captures what it means to perform a task by algorithmic means. And, really, in no way has anyone ever been able to "prove" the Church-Turing thesis: it was more like an emperical fact until quantum computing realized otherwise.
While classical Turing machines can simulate quantum mechanical Turing machines, it appears that they cannot due this efficiently. This means that we shouldn't base our idea of an algorithm on what a classical Turing machine can do, but instead on what a quantum Turing machine can do.
viva la Quantum computation
(sorry, just watched the South Park movie last night)
dabacon
I wonder how many people learned to program by chasing the inevitable bugs in transfering programs from Computes!s Gazette to computer? Thats how I learned to program.
Sounds like a poll to me.
dabacon
"I ski therefore I am"
Anyone ever get sick of this guys "arguement by Einstein". Because, of course, Einstein was always right (do the words "static universe" mean anything to you?) Not that I think that Einstein wasn't a man of amazing genius (I mean both special AND general relativity, come on, you've got to be kidding!), but I'm not such a great worshiper of the "older" Einstein.
Yes, the world could be made of cheese. But I prefer to think that the many generations of millions of scientists have got closer to the truth when they told me the world isn't made of cheese. (Feynmann probability 99.99999%)
dabacon
Why the excitement?
1. Quantum computers can do things more efficiently that the classical computer you have in front of you. One word: economic considerations!
2. Quantum cryptography is a secure way to distribute random keys.
3. We don't really understand why quantum information possesses different computational properties. Researchers have some decent intuition about quantum algorithms, but it is such a new field that no one really knows where boundaries between the power of quantum and classical information lies. Of course the goal of science is to understand such questions as "what makes a quantum computer more powerful" and who knows what interesting insights about (1) computation, (2) physics will arise from quantum computation?
As to your second question: there is a ton of money being spent on building an actual quantum computer and there are more than half a dozen different proposals for such machines. Some examples of these models are using traped ions, neutral atoms in optical lattices, single electron spins on quantum dots, and much more.
And when you think the press to impact on society ratio is too high just remember good old Lord Kelvin:
"Heavier-than-air flying machines are impossible." --Lord Kelvin, president, Royal Society, 1895.
dabacon
Good to see your 100 AD dictionary getting some use! dabacon
The paper which has this experiment was just published in Science. You probably need to be connecting from somewhere that has subscribed to Science.
A good intro reference to DFSs is here.
dabacon
You must realize that the decoherence mechanisms which occur at the event horizon probably does not have a symmetry that can be exploited. I mean the only people who write if you're so smart are the people who already know the answer, right? lmao
dabacon
OK, being as I am a reasearcher who has done work on decoherence-free subspaces (DFSs...they are also known as quantum error avoiding codes or noiseless subspaces...damn nomenclaturese) I thought I'd give all you netadmins a real simple explanation of what a DFS is. Of course, being a simple explanation, it will fuzz over a bit. But I thought I'd at least try!
Suppose you are trying to send some bits down a noisy communication channel (sending an email from Timbucktoo to Weed, CA). Now the noise will cause the bits that you send on one end of the line to sometimes come out different on the other end of the line. Many of you know how we get around this in real world situations: we use error correction. The basic idea of error correction is to use redundancy to transmit information. Thus, for example, instead of sending the bit 0 you might send ten 0's and instead of sending the bit 1 you might send ten 1's. If the channel isn't too noisy then the reciever can figure out what bit you ment to send by looking at the ten bits he recieves and deducing if of those ten more are 0's or 1's. Basically you can reduce the noise rate of information transmission at the cost of increasing the number of bits you need to send in order to transmit one bit of information. (Sorry for those of you who know this shit like the back of your hand).
Decoherence-free subspaces work on a similar "encode the information" (i.e. 0->ten 0's, 1->ten 1's), but they "use symmetry" to protect the information.
Suppose that after extensive testing of the phone line you are using you notice that if you send two bits down the line in rapid sucession the line either does nothing to these two bits or flips both of them. Thus for example, if you send 00, the reciever always gets either 00 (no error) or 11 (error!) and if you send 01, the reciever always gets either 01 (no error) or 10 (error!). Your phone line has a symmetry! How do exploit this symmetry?
Well, what you do is simply encode the information you want to send into the parity of the two bits. This simply means that if you want to send 0 down the line, you send 00 (or 11) and if you want to send 1 down the line, you send 01 or (10). Now the noise can flip 00 to 11 (or vice versa) but it cannot change 00 to 01. Thus the you can perfectly recover the information you sent down the line regardless of an error occuring. What is neat about this is that it doesn't depend on the strength of the noise (the probability that an error occurs, for example). By using the symmetry of the noise you can avoid the noise completely! Symmetry=>protection.
What I've explained to you is an example of a decoherence-free subsystem (a generalization of decoherence-free subspaces, but the same basic idea) in the real "classical" world. To build a quantum computer we need to deal with similar problems but in the "quantum" world.
When Peter Shor (quantum computing god) invented a quantum computing algorithm for factoring (the one that breaks RSA), one of the main problems in actually implementing such a computer was quickly understood to be noise. Noise in quantum system is called decoherence (at least by me) and is much more nasty than the classical noise you get when (say) you are talking on your cell phone. The problem with quantum systems is that if they interact with external systems they completely lose their quantum nature. And making this problem even harder, whenever you observe a quantum system it also loses its quantum nature.
But following his work in discovering the factoring algorithm, Peter Shor noticed that he could do error correction on quantum systems to avoid this decoherence problem (hence Peter Shor=quantum computing god). A huge host of people then developed the theory of quantum error correction which showed that the decoherence problem could be overcome. This is probably one of the most amazing new ideas of the past decade: that quantum information can be in principle be sheilded from its environement by suitable error correction.
Anyway, decoherence-free subspaces are like quantum error correction in that you encode quantum information, but they, like the example above, use the fact that often noise has some sort of symmetry. Think about it this way: decoherence of a quantum system is like you looking at the system (you are interacting with the system!). But say you have two atoms which are so close together to each other that you cannot distinguish atom A from atom B. Then there is a symmetry in the way in which observe the system: you cannot distiguish that atom A is on the left or if it is on the right. Such a symmetry can then be shown the produce encodings of information which are protected from your observation!
Ah well, I had to try. Thanks to anyone who made it this far without "man I want to kill this dork" thoughts.
dave bacon
Wait: you mean you don't buy the logic behind "arguement by anecdote"?
Judging by the amount of such logic I find in the majority of newsprint I'm beginning to wonder if journalists are actually taught this type of reasoning in journalism school.
Dave "I don't even believe anything I write" Bacon
God I hate articles like this. I would be even more blunt (and yes IAAQCR I am a quantum computing researcher): using a single electron to encode information is EXPONENTIALLY COSTLY and hence PRACTICALLY USELESS.
Storing k bits of information in the wavefunction of an electron will require resources (energy expendature for example) which grows like some constant to the power of k.
Of course one can store an infinite amount of information in a real number (say the length of your big toe), but the cost of measuring that length becomes exponentially prohibative as you acquire more digits of accuracy.
You could think of this as the "lets make storing and retreval of data an NP complete problem" solution.
dabacon
famous computer science conjecture: N does not equal 1.
Something within me just revolts at the site of this getting press at such a preliminary stage. From your post, I'm guessing that the CERN had to present their "possible Higgs" data in order to get the extra time needed to explore this lead further.
But if the data is as sketchy as you say, why in the world did the press pick this up?
This reminds me of a few years back when I heard on the radio that "room-temperature" superconductors had been discovered. I was so excited I almost drove off the road, only to find out later that it was just a bad case of the press picking up an early result which later proved incorrect. Doh!
dabacon
Not quite right. Quantum computers don't "explore every possible key immediately".
What quantum computers can really do efficiently is to factor numbers efficiently. This is DIFFERENT from exploring all of the keys simultaneously. If this was how a quantum computer worked, then quantum computing would have an even greater impact on the world...it would easily imply that quantum computers can solve NP complete problems efficiently. As of today, to my knowledge, no one has shown how to solve an NP complete problem efficiently on a quantum computer.
dabacon.
Careful, the fact that quantum computers can efficiently factor (or compute the discrete logarithm) is seperate from so-called quantum key distribution. i.e.
1. If you build a computer based on quantum information, it can factor numbers efficiently and hence compromises crypto schemes like RSA.
2. If you build a communication line which uses quantum information to distribute a key for cryptographic purposes you can guarantee security of the key distribution (i.e. if someone is spying you WILL know this).
I'm sure everyone who has an ounce of intuition can postulate that these two are related, but to my knowledge, no one has every shown a connection between the two.
I recently saw a paper in which the author demonstrated an extension of the quantum computing factoring algorithm to "other hard number theory questions". How odd that nature has provided us with a way to become superb numerical geniuses!
dabacon
Is it really true that it would render ALL crypto schemes unbreakable? I don't think so.
For instance, there are crypto systems based on the difficulty of solving an NP-complete problem. So far, no one has been able to show (and many researchers do not beleive) that quantum computers can efficiently solve NP-complete problems. As I understand it, crypto systems based on NP-complete problems are rather inefficient (as opposed to say RSA) and this is the main reason why they are not in widespread use.
That withstanding, I wouldn't hold your breath for Intel coming out with its first quantum computer soon: building a quantum computer looks to be one of the grand technological challenges of the 21st century.
Oh yeah, quantum computing people really hate it when they are mentioned in the same breath as DNA computing and optical computers....the speedup due to quantum computers should be thought of as more of a software speedup (i.e. faster algorithms) not as a hardware speedup (i.e. basic circuitry more efficient).
dabacon