Let’s assume general purpose quantum computers that can operate usefully at scale are coming. I think a reasonable timeframe is 15 years. There are massive engineering challenges to be overcome that might push this further out, but there is also the potential for incredible breakthroughs that may bring this forward. The National Academies has a great report on the current state of quantum computing here. When thinking about the risks that come from quantum computing it is strange (but not surprising) we fixate solely on the impact to cryptographic algorithms and the security systems they underpin. That is of course critical and NIST are actively developing quantum proof algorithms and there are already some uses of a number of the candidate algorithms in public and private sectors. For some organizations that are protecting long term secrets or require long lived signatures for which re-signing may not be practical (or legal) the work does indeed need to be done now. Everyone else can wait and take the new algorithms as they become integrated into software / toolkits. In all cases though, the long term effort of upgrading all the systems that use current crypto to the new algorithms will be immense. But let’s be careful, in a world of quantum computing, cryptographic impact may be just one of many security issues. Here are some other things to worry about (and I am just scratching the surface here):
1. Crypto-agility
After you’ve figured out whether you need to care about updating all your crypto in the coming years then you need to worry about improved upgradability (perhaps in the field) and the different performance characteristics of the algorithms selected. We need to focus on so called, crypto-agility, whereby we engineer our crypto-systems and the use of them to be better able to cope with algorithm and algorithm parameter changes more frequently - without requiring constant and significant changes to the surrounding environment.
The real problem, though, is broader than can be solved by crypto-agility as it seems to be currently conceived by many vendors. Under the new algorithms keys maybe larger, cipher text expanded and hashes / signatures may be significantly longer. Even if crypto-agile systems can insulate your applications and associated protocols from much of this, and even if we can safely assume hardware evolution will reduce the burden of speed and power to run the new algorithms, it is still going to be problematic to change applications. Specifically, applications that have in their data structures, messaging types and API formulation dependencies on prior algorithms' properties. Think of all the market specific protocols (e.g. financial messaging) that encode signatures and hashes in application layer protocols. It might not be too dramatic to suggest we are looking at something like a "crypto Y2K" project. [Although, look on the bright side, given the likely timing we can probably deal with this at the same time we’re dealing with the 2038 problem.]
2. High Performance Solutions of Hard Security Problems
The promise of quantum computing is to provide fast(er) solutions to hard computational problems - hard in the formal sense of computational complexity. There are plenty of hard (some NP-complete) problems in information/cybersecurity.
Perhaps we will formulate quantum algorithms for finding software vulnerabilities, protocol flaws, developing exploits, provably hiding logic intent in code, compromising secure multi party computation, and so on. Of course, this is a dual risk as offensive use can be turned to defensive advantage as well. A whole new arms race will begin.
3. Second Order Consequences
What are the risk consequences of the widespread use of quantum computing? Hard optimization problems will be solved and improved upon, this might mean more efficient supply chains, improvements in design and manufacturing of physical products, faster and more potent drug development, sensor improvements nullifying stealth technologies, better AI, improved robotics. The list is huge. As security can have dual (positive and negative) consequence so will all these other impacts: supply chain optimization might further reduce the slack we need for resilience, new manufacturing processes will yield new operational technology issues, pervasive autonomous transport will bring security and safety more squarely together, and so on.
Bottom line : when it arrives, quantum computing will bring societal level opportunities and risks. We can't fully predict the n-order effects of this and even though we are preparing for a crypto-agile and upgraded world we also need to pay attention to all the other security consequences.