Re:Great education opportunity....
on
Quantum Security
·
· Score: 2
At MIT this is possible -- I did a double major in physics and electrical engineering / computer science. There was not a whole lot of overlap, though a few of the physics classes were accepted by the eecs department and I would've done it in 4 years without killing myself, except that I stuck around an extra year to get a master's in eecs also (yay 5-year master/bachelor programs). In reality, there is a lot of overlap between these fields, it's just not as apparent at the undergrad levels, and in some schools, I wouldn't be surprised if the reasons for not helping with such combinations are largely political. Go academia yeah.
Now that I'm employed, I'm doing a pretty regular eecs job, but that's because I was kind of burned out on physics. In a year or two, I may see what is available.
But there really are a lot of overlaps, and not only in quantum computing/error correction/cryptography. Especially as frequencies get higher, linewidths get narrower, etc, understanding the physics gets more important just from a practical engineering point of view. There is a lot of research, eg, in the areas of nonlinear dynamics, where computer science and physics overlap heavily. Thinking about computation as a physical process can be useful, as can thinking about physical processes as computation.
Anyway, I would strongly recommend combining majors like this, or at least using elective classes to effectively learn what you need as the basis for graduate work or maybe even industry work in these areas. Undergrad programs tend to be heavy on the traditional fields, since a solid grounding is a good idea, but there is a lot of exciting interdisciplinary research going on. Check out the Physics and Media group at the MIT media lab for some examples and pointers to other research.
CG rendering, eg, is a problem that's in P that we burn a lot of time trying to improve computing efficiency on. A quantum computer won't help with that because there's no exponential explosion of the search space to control. CG is dominated by the constants in its polynomial-time solutions. Many other tasks are similar. Maybe there's a way to cast these problems so as to take advantage of the QC's exponential search space, but maybe not. QC won't help with the constants.
You can repeat the experiment a few times to pump up the probability that you get the right answer. As long as the number of repetitions to get the answer within an arbitrary epsilon of 100% is only polynomially related to epsilon (well, 1/epsilon), then you still win from a computational viewpoint where constants don't matter because exponents dominate.
Even in classical computers, there is a nonzero error rate. It just so happens that those errors can be bounded -- Shannon's coding theorem can be applied to a computation as a communications channel and shows that a computation with arbitrarily small errors can be achieved in the face of noise if you trade off computation bandwidth (read, MIPS) to do error correction. That's what this article is about -- finding ways of error correcting quantum states to allow sustained, error-free computation...
While Shor's factoring algorithm (which permits polynomial time rather than exponential time integer factoring, and therefore could undermine the security of RSA) may well be a "killer app" for quantum computing, it's worth pointing out that it's not yet been shown that QC can help us with general computing problems.
The big win in QC comes from the superposability of states -- it is possible for the system to be in all of its states at the same time. For n quantum bits (qubits), this is 2**n (two to the n) states. Operations on a system that is in such a superposed state are performed on every possible state at once. Great, neat, cool. But there's a catch -- the information you want can't come from a single measurement of the resulting system. The exponentially large amount of data you've computed is stored in the probability distribution (in some sense). In order to read this out, you need to repeat the experiment again and again to measure out the distribution instead of a single instance of the random variable.
Guess what, in order to get out the exponentially large amount of information from the probability distribution, you need to make an exponentially large number of measurements. So you're no better off, right?
Well, in general, maybe not. But there may be special cases. In the cases we've found so far, something funny happens in the quantum mechanical phase space that lets us actually read out the correct answer. Grover's search algorithm is a particularly clear example of what happens. In this case, the "right answer" can be read out because there is a computation that can cause a particular state to be selected with near 100% probability -- this state is the "winning" state that is being searched for (see L.K. Grover, Phys Rev Lett, 79, 325 (1997)).
Anyway, QC is only useful for those problems that can be computed in such a way that the answers can be read out of the QC in polynomial time. Right now, that's factoring (admittedly a biggie, but not likely something that'll, eg, get you 200 fps at quake, which you don't need anyway... oh wait, wrong thread), Grover's search, and a few other examples. Right now, though, QCs look like they'll be special-purpose code breakers. Hmm. Collossus?...
Quantum mechanics is the current scientific dogma because it has successfully explained a _vast_ array of experiments. Further, it has successfully _predicted_ a huge number of phenomena. These are good reasons to begin to believe that a theory will generally give you a good answer, and quantum has given enough that it's not unreasonable to believe that it may be more accurate in its predictions than we are in our experimental capabilities. In response to "failures" such as the experiments you refer to (which I must admit to not having examined closely), two things should be done. First, as you suggest, alternative theories should be proposed and tested, perhaps more widely than is done today, I don't know, but it's important to consider the possibility that the theory is flawed. Second, more careful experiments should be carried out to try to nail down exactly what happens, because it's also important to consider the possibility that the experiment is flawed.
If nothing else, quantum computing, cryptography, error correction, communications, etc, push experiments that test this regime of quantum mechanics. The scientific community won't push forever if entanglement really can't be demonstrated. You (and marshall, et al) may very well prove correct -- maybe this quantum mumbo jumbo is all hogwash and students in the year 2100 will laugh at today's physics community like we laugh at the physicists of a century ago. It will take time -- quantum has been right in enough cases that it deserves some trust.
Anyway, I know a number of folks who are working on various bits of QC research. These are not shady scientists looking to push alternative theories under the rug and secure government grants on false promises. Rather, they are passionate scientists who see the potential opportunities that may come from this speculative research. I would wager that this is true of the majority of members of the QC community.
Slashdot Mirror
Now that I'm employed, I'm doing a pretty regular eecs job, but that's because I was kind of burned out on physics. In a year or two, I may see what is available.
But there really are a lot of overlaps, and not only in quantum computing/error correction/cryptography. Especially as frequencies get higher, linewidths get narrower, etc, understanding the physics gets more important just from a practical engineering point of view. There is a lot of research, eg, in the areas of nonlinear dynamics, where computer science and physics overlap heavily. Thinking about computation as a physical process can be useful, as can thinking about physical processes as computation.
Anyway, I would strongly recommend combining majors like this, or at least using elective classes to effectively learn what you need as the basis for graduate work or maybe even industry work in these areas. Undergrad programs tend to be heavy on the traditional fields, since a solid grounding is a good idea, but there is a lot of exciting interdisciplinary research going on. Check out the Physics and Media group at the MIT media lab for some examples and pointers to other research.
CG rendering, eg, is a problem that's in P that we burn a lot of time trying to improve computing efficiency on. A quantum computer won't help with that because there's no exponential explosion of the search space to control. CG is dominated by the constants in its polynomial-time solutions. Many other tasks are similar. Maybe there's a way to cast these problems so as to take advantage of the QC's exponential search space, but maybe not. QC won't help with the constants.
You can repeat the experiment a few times to pump up the probability that you get the right answer. As long as the number of repetitions to get the answer within an arbitrary epsilon of 100% is only polynomially related to epsilon (well, 1/epsilon), then you still win from a computational viewpoint where constants don't matter because exponents dominate.
Even in classical computers, there is a nonzero error rate. It just so happens that those errors can be bounded -- Shannon's coding theorem can be applied to a computation as a communications channel and shows that a computation with arbitrarily small errors can be achieved in the face of noise if you trade off computation bandwidth (read, MIPS) to do error correction. That's what this article is about -- finding ways of error correcting quantum states to allow sustained, error-free computation...
While Shor's factoring algorithm (which permits polynomial time rather than exponential time integer factoring, and therefore could undermine the security of RSA) may well be a "killer app" for quantum computing, it's worth pointing out that it's not yet been shown that QC can help us with general computing problems.
...
The big win in QC comes from the superposability of states -- it is possible for the system to be in all of its states at the same time. For n quantum bits (qubits), this is 2**n (two to the n) states. Operations on a system that is in such a superposed state are performed on every possible state at once. Great, neat, cool. But there's a catch -- the information you want can't come from a single measurement of the resulting system. The exponentially large amount of data you've computed is stored in the probability distribution (in some sense). In order to read this out, you need to repeat the experiment again and again to measure out the distribution instead of a single instance of the random variable.
Guess what, in order to get out the exponentially large amount of information from the probability distribution, you need to make an exponentially large number of measurements. So you're no better off, right?
Well, in general, maybe not. But there may be special cases. In the cases we've found so far, something funny happens in the quantum mechanical phase space that lets us actually read out the correct answer. Grover's search algorithm is a particularly clear example of what happens. In this case, the "right answer" can be read out because there is a computation that can cause a particular state to be selected with near 100% probability -- this state is the "winning" state that is being searched for (see L.K. Grover, Phys Rev Lett, 79, 325 (1997)).
Anyway, QC is only useful for those problems that can be computed in such a way that the answers can be read out of the QC in polynomial time. Right now, that's factoring (admittedly a biggie, but not likely something that'll, eg, get you 200 fps at quake, which you don't need anyway... oh wait, wrong thread), Grover's search, and a few other examples. Right now, though, QCs look like they'll be special-purpose code breakers. Hmm. Collossus?
Quantum mechanics is the current scientific dogma because it has successfully explained a _vast_ array of experiments. Further, it has successfully _predicted_ a huge number of phenomena. These are good reasons to begin to believe that a theory will generally give you a good answer, and quantum has given enough that it's not unreasonable to believe that it may be more accurate in its predictions than we are in our experimental capabilities. In response to "failures" such as the experiments you refer to (which I must admit to not having examined closely), two things should be done. First, as you suggest, alternative theories should be proposed and tested, perhaps more widely than is done today, I don't know, but it's important to consider the possibility that the theory is flawed. Second, more careful experiments should be carried out to try to nail down exactly what happens, because it's also important to consider the possibility that the experiment is flawed.
If nothing else, quantum computing, cryptography, error correction, communications, etc, push experiments that test this regime of quantum mechanics. The scientific community won't push forever if entanglement really can't be demonstrated. You (and marshall, et al) may very well prove correct -- maybe this quantum mumbo jumbo is all hogwash and students in the year 2100 will laugh at today's physics community like we laugh at the physicists of a century ago. It will take time -- quantum has been right in enough cases that it deserves some trust.
Anyway, I know a number of folks who are working on various bits of QC research. These are not shady scientists looking to push alternative theories under the rug and secure government grants on false promises. Rather, they are passionate scientists who see the potential opportunities that may come from this speculative research. I would wager that this is true of the majority of members of the QC community.