Soooo a non-technical friend of mine recently claimed that quantum computing threatens to render encryption technology obsolete (at least for nation-states) thanks to some kind of magical ability to prime factor large numbers. I won't degrade this forum with the useless link he sent, but it occurs to me that I have no technical understanding of quantum computing whatsoever. I doubt that anyone here has access to a quantum computer or direct research with one, but what do we think? Is encryption dead? Is quantum computing really threatening the state of security?

If we set up this reasoning:
- any encryption can be broken by a computer with unlimited processing power
- quantum computers provide unlimited processing power
then the answer should be: "yes, encryption becomes obsolete with quantum computers"

I believe there is even a Wiki page about quantum computers. They are able to perform an infinite number of calculations at the same time because nuclear particles can have an infinite number of simultaneous positions and momentums.

The question is just when a usable quantum computer will be available. Funny things, a user would be user and root at the same time. Or logged in and logged out at the same time. Or a semaphore would be true and false at the same time. Quite exciting.

Maybe it will be in 40 years from now. Just as nuclear fusion for energy generation has been 40 years away for the part half century.

jlinkels

When I asked Schrödinger's cat, he confusingly said "Yes, and No."

No, quantum computers do not give infinite processing power. They can't solve NP-complete problems in polynomial time either.

There is an algorithm to factor integers in polynomial time using a quantum computer: Shor's algorithm (friendlier explanation). Note that we don't have a lower bound on integer factoring, so it might be solvable in polynomial time on a classical computer too.

This would break current public key systems but there are public key systems that are based on NP-complete problems (they are not used currently because the key sizes are quite a bit bigger), so we could move to those if quantum computers turn out to be practical.

1 members found this post helpful.

OK this sounds more reasonable and less like middle school hearsay. Do you have a source for your information that we might refer to?

The "friendlier explanation" I linked to is the blog of Scott Aaronson, his thesis is about this stuff so I would consider him an expert. In his thesis summary he says:

2 members found this post helpful.