Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
This question may be slightly opinion based, so I apologise if this is the incorrect place to ask.
My question is, is there any use for Shor's integer factorisation algorithm other than for breaking public key cryptography. If there isn't, then am I right in thinking that the algorithm becomes obsolete once all data is encrypted using post quantum cryptography?
A bit of an esoteric answer: there is a particular proposal for post-quantum cryptography called "CSI-FiSh", based on isogenies. Without getting too deep into the number theory, the parameters of CSI-FiSh define a particular group structure. If we know the group structure, we can make efficient digital signature schemes; if we do not know the group structure, the digital signature schemes are much less efficient.
However, the best classical algorithms to find the group structure are subexponential in the input size of the CSI-FiSh parameters, and the best quantum attacks are also subexponential. So far we only know the group structure for 512-bit primes, which many people (including me) feel are not large enough to be quantum safe. But we cannot find the group structure for bigger parameters with classical computers. Yet, Shor's algorithm could find the group structure in polynomial time!
In the end, this means we can't make this scheme efficient and secure until we have a quantum computer that can apply Shor's algorithm to it. Some have called it "post-post-quantum cryptography" for this reason. I'm not sure that this scheme would actually be used, but it's a potential constructive application for Shor's algorithm.
community wiki
It's an interesting question to pose which problems reduce to factoring (or discrete log), and whether any of those problems could be of practical value. In general I think the consensus is that most such problems are of some number-theoretical bent in the first place.
There's a 1987 paper from Heather Wolf that proves and lists some reductions known at that time:
Whether any other reductions are known, since, say, Shor '94, that are of industrial relevance, I am not sure. I've often thought about reducing factoring to finding Golomb rulers but I don't know enough number theory to make headway.
Factoring (and discrete log and related questions) are such unique problems in computer science - Aaronson often quips that if we can factor numbers easily then we can collapse the entire world economy but we wouldn't collapse the polynomial hierarchy.
Graph Isomorphism is another problem of much practical importance, but alas this is not known to be in BQP (and our classical algorithms are pretty good anyways).
I do disagree, though, that "the algorithm becomes obsolete once all data is encrypted using post quantum cryptography". The website that I'm writing this on, right now, says https - all of those private keys are ripe for the taking even after conversion to post-quantum cryptography.
