Comment Re:Okay, here's a question (Score 1) 137
Caveat: We are now outside my area of expertise. If anyone knows more about these matters, please feel free to correct my mistakes.
My reply would be that quantum computers are not non-deterministic. A non-deterministic machine is one that is allowed to make guesses, or choose between multiple possibilities. To say that a non-deterministic machine can solve something in polynomial time usually includes the unspoken assumption that the machine _always guesses correctly_. So, yes, secret key encryption is probably breakable by a non-deterministic machine in linear time-- the machine simply guesses each bit of the key correctly. However, I don't think anyone has actually built a non-deterministic machine.
A quantum computer, on the other hand, can be in multiple states simultaneously-- until you look at it. When you look at it, however, it collapses into one of its component states RANDOMLY. For example, suppose you have a quantum bit ("qubit"). This bit can be in either of the two classical states: |1>, or |0>. It can also be in any combination of the two, such as (a * |1> + b * |0>). (The coefficents a and b, by the way, can be complex numbers.) When you look at the bit, on the other hand, it will collapse into one of the two classical states randomly, with the probabilites given by the values of a and b.
So, as opposed to a non-deterministic machine, a quantum machine can look at all options simultaneously but will only show you one outcome. It may not be the outcome you want, and once you look at it _all the other outcomes are gone_. The trick of quantum computing is to cleverly massage the values of a and b until you can be sure that it will collapse into an outcome you want. (This is the essence of Shor's algorithm.)
If you want to know more, look at http://www.qubit.org.
My reply would be that quantum computers are not non-deterministic. A non-deterministic machine is one that is allowed to make guesses, or choose between multiple possibilities. To say that a non-deterministic machine can solve something in polynomial time usually includes the unspoken assumption that the machine _always guesses correctly_. So, yes, secret key encryption is probably breakable by a non-deterministic machine in linear time-- the machine simply guesses each bit of the key correctly. However, I don't think anyone has actually built a non-deterministic machine.
A quantum computer, on the other hand, can be in multiple states simultaneously-- until you look at it. When you look at it, however, it collapses into one of its component states RANDOMLY. For example, suppose you have a quantum bit ("qubit"). This bit can be in either of the two classical states: |1>, or |0>. It can also be in any combination of the two, such as (a * |1> + b * |0>). (The coefficents a and b, by the way, can be complex numbers.) When you look at the bit, on the other hand, it will collapse into one of the two classical states randomly, with the probabilites given by the values of a and b.
So, as opposed to a non-deterministic machine, a quantum machine can look at all options simultaneously but will only show you one outcome. It may not be the outcome you want, and once you look at it _all the other outcomes are gone_. The trick of quantum computing is to cleverly massage the values of a and b until you can be sure that it will collapse into an outcome you want. (This is the essence of Shor's algorithm.)
If you want to know more, look at http://www.qubit.org.
