Would the interest in building quantum computers decrease if a classical algorithm for factoring all integers in polynomial time is discovered?

Question

Quoting Wikipedia:

No algorithm has been published that can factor all integers in polynomial time, that is, that can factor a $b$-bit number $n$ in time $O(b^k)$ for some constant $k$. Neither the existence nor non-existence of such algorithms has been proved, but it is generally suspected that they do not exist and hence that the problem is not in class P.[3][4] The problem is clearly in class NP, but it is generally suspected that it is not NP-complete, though this has not been proven.[5]

There are published algorithms that are faster than $O((1 + ε)^b)$ for all positive $ε$, that is, sub-exponential. As of 2021-03-12, the algorithm with best theoretical asymptotic running time is the general number field sieve (GNFS), first published in 1993,[6] running on a $b$-bit number $n$ in time: [...] For current computers, GNFS is the best published algorithm for large $n$ (more than about 400 bits). For a quantum computer, however, Peter Shor discovered an algorithm in 1994 that solves it in polynomial time.

However, let's imagine for a moment that someday a classical algorithm for factoring all integers in polynomial time is discovered, would the interest in building quantum computer decrease?

Obviously, integer factorization is far from being the only application for quantum computers (I am thinking about Grover's algorithm, quantum mechanics simulations, etc), but Shor's algorithm has really turbocharged the interest in developing quantum computers.

Answer 1

This depends on a few factors, excuse the pun. This is already an unlikely scenario, with several associated unlikely variants.

1. Even if Integer Factorization is in P and said algorithm is discovered rather than existentially proved, it may still not be practical to factor for cryptographic purposes if the exponent or constants are too large. In this case, Shor's Algorithm would likely remain of interest for breaking cryptography. Integer Factorization is a form of the more general Hidden Finite Abelian Subgroup problem, known to be in BQP, which also includes the Discrete Logarithm of Diffie-Hellman fame: it is possible this theoretical classical technique may be impractical for factoring but if it could be generalized it may be applicable to other cryptographically-relevant problems in a way that is more practical, at least rendering some systems insecure if not RSA.
2. It is possible a quantum algorithm may be necessary to make a replacement cryptosystem for RSA, in which case this might actually increase interest in building quantum computers. This is a more speculative scenario: there are cryptographic protocols that require solving NP-Hard problems to crack that appear promising, though average cases may be too easy to crack even if the general problem is hard.

I would suspect at the very least the stocks of companies dedicated to quantum computation would crash upon such an announcement. Quantum computation would likely remain of interest in academia, business is what is going to be hit harder. And this ignores the impact RSA being unusable would immediately have, which could have a catastrophic effect on Internet security and society in general in an imagined worst-case scenario.