Q-Day Predictions: Anticipating the Arrival of Cryptanalytically Relevant Quantum Computers (CRQC)

Introduction

There is a tremendous amount of hype about quantum computing recently. Governments, corporations, and academic institutions are pouring increasing resources into this field, recognizing its potential to address a wide array of critical scientific and societal challenges. While the technology has begun to affect specific areas, such as the design of efficient batteries for electric vehicles, precision drilling in the oil and gas industry, sophisticated financial analyses, medical research advancements, and improvements in weather prediction models, these applications remain quite narrow. Broader commercial uses hinges on the development of fault-tolerant quantum computing, a goal that still faces many challenges, as we’ll discuss later.

One of the most frequently discussed potential applications of quantum computing is its ability to factor large numbers exponentially faster than classical computers, which could make it possible to break the public key encryption that underpins the internet, online banking, secure messaging, cryptocurrencies, control communication to cyber-physical systems, military communications, and more. Sensitive data protected by today’s encryption methods, such as financial records, state secrets, and personal information, could suddenly become vulnerable to exposure. Adversaries could take control of critical infrastructure and mount cyber-kinetic attacks with ease. The emergence of such Cryptographically or Cryptanalytically Relevant Quantum Computers (CRQC) that will break or weaken existing “classical” cryptography will transform the cybersecurity landscape.

While technological advancements are pushing us towards what is ominously dubbed ‘Q-Day’ – the day a CRQC becomes operational – CRQCs capable of breaking current public key encryption algorithms have not yet materialized. Many experts believe that Q-Day, or Y2Q as it’s sometimes called, is just around the corner, suggesting it could occur by 2030 or even sooner; some speculate it may already exist within secret government laboratories.

For those new to the topic, the feasibility of quantum computing technology was first showed in the late 90s. Predictions about the impending cryptographic apocalypse soon followed, with various vendors and experts attempting to pinpoint Q-Day. As far as 2010, during one of my interim CISO roles, a vendor claiming to have quantum-resilient cryptographic solutions insisted they had insider information from the NSA, suggesting that the CRQC was mere months away. Since then, I’ve encountered similar predictions with regularity.

With all this noise about quantum computing, it’s difficult to distinguish between hyperbole and reality. In this article, I aim to sift through the hype, vendor marketing exaggerations, scientific research, come up with as hype-free view as possible on when to expect the Q-Day, and form my prediction.

However, an important disclaimer: whenever Q-Day really happens, start preparing for it today! In a future article, I will explore why preparing for Q-Day could take a large enterprise a decade or more and why you should have already started these efforts.

Background

One of the most significant and disruptive applications of quantum computing is in cryptography. Cryptographically or Cryptanalytically Relevant Quantum Computing (CRQC) refers to the use of quantum computers to break cryptographic algorithms that are embedded in every digital solution and digital communication everywhere. This capability centers on quantum computing’s potential to solve certain mathematical problems far more efficiently than classical computers.

The consensus that CRQC poses a genuine threat to current cryptographic standards has solidified over recent years. This is largely because of advancements in quantum computing technology and a deeper understanding of its implications for cryptography. “Q-Day” refers to the hypothetical future point when quantum computers become capable of breaking widely used cryptographic algorithms, effectively rendering much of today’s encryption obsolete overnight.

At the heart of CRQC’s threat to cryptography is Shor’s algorithm, developed by mathematician Peter Shor in 1994. This quantum algorithm can factor large integers and compute discrete logarithms exponentially faster than the best-known classical algorithms. Since many cryptographic systems, such as RSA and ECC (Elliptic Curve Cryptography), rely on the difficulty of these problems for security, Shor’s algorithm directly threatens their integrity. For instance, decrypting an RSA-2048 bit encryption key—a standard security protocol—would require a classical computer approximately 300 trillion years, or quadrillions of years by another estimate, or hundreds of thousands of years by a third estimate – in any case, a lot. A quantum computer with 4,099 stable logical qubits could accomplish this task in mere seconds to minutes. However, the primary challenge faced by quantum computing engineers is achieving and maintaining this level of qubit stability or coherence, which, as of now, persists for only microseconds.

Logical Qubit vs Physical Qubit

This might be a suitable moment to explain the difference between a logical qubit and a physical qubit. Physical qubits are the basic units of quantum information in a quantum computer. Somewhat like “bits” in classical computing. They physically exist in the quantum computing hardware, made from systems such as superconducting circuits, trapped ions, or photons where quantum properties like superposition and entanglement are manifested. Physical qubits are notoriously sensitive to external disturbances, as I mentioned before, leading to errors and decoherence – the loss of quantum information. This presents significant challenges, requiring the development of techniques to mitigate errors and preserve the integrity of quantum information.

A logical qubit is formed by entangling many physical qubits together and employing quantum error correction codes to detect and correct errors without disturbing the quantum information. This redundancy allows logical qubits to maintain coherence for longer periods, enhancing the reliability of quantum computations. The creation and maintenance of logical qubits require sophisticated error correction algorithms and additional physical qubits, but they are essential for realizing fault-tolerant quantum computing, where operations can proceed accurately despite the inherent imperfections of physical qubits. To achieve a sufficiently low error rate for practical quantum computing, estimates often suggest needing around 100 to 1000 physical qubits per logical qubit. For more information, see my post “Fidelity in Quantum Computing.”

In this article, and commonly within the industry, discussions about the number of qubits needed to execute a specific algorithm, such as the 4,099 qubits required for Shor’s algorithm, refer to logical, stable, error-free qubits. However, when vendors announce their latest, more advanced quantum computers, they usually talk about physical, noisy qubits. This distinction is crucial for our discussion, as the anticipated 1,000-physical-qubit chips to be announced sometime this year are still far from the 4,099-logical-qubit computers necessary to run Shor’s algorithm. If we assume that building one logical, reliable qubit requires combining 1,000 physical qubits with error correction, as is commonly believed in the industry, it implies that we are now at the developmental stage where we will soon have the first of the 4,099 logical qubits needed for Shor’s algorithm.

Quantum Supremacy

Quantum supremacy, also known as quantum advantage, is a critical milestone in quantum computing. Quantum supremacy occurs when a quantum computer surpasses the capabilities of the best classical computers by solving a problem or performing a task significantly faster or more efficiently using current algorithms. It highlights the practical benefits of quantum technologies, demonstrating their potential to handle specific computational problems that are infeasible for classical systems. For this discussion, achieving quantum advantage or quantum supremacy not only validates the power of quantum computing but also signifies the start of its practical application across various industries. Following quantum advantage, broad application of quantum computers on various problems where the commercial benefits of quantum computing will become obvious will mark the immediate milestone preceding CRQC.

Impact on Cryptography

The impact of CRQC varies across different types of cryptographic systems:

• Asymmetric Key Encryption: This form of encryption, also known as public-key cryptography, is most at risk from CRQC. Systems like RSA and ECC, which secure everything from internet transactions to confidential communications, rely on the computational difficulty of factoring large numbers and computing discrete logarithms—exactly the problems that quantum computing can solve efficiently.
• Symmetric Key Encryption: Symmetric cryptography, which uses the same key for both encryption and decryption, is less vulnerable to quantum attacks. The most notable quantum algorithm that affects symmetric encryption is Grover’s algorithm, which can theoretically reduce the security of symmetric keys by half. This means a 256-bit symmetric key (considered secure against classical attacks) would have the security equivalent of a 128-bit key against a quantum attack. While this reduction is significant, doubling the key length can mitigate the threat.
• Hash Functions: Hash functions, used for verifying data integrity and in various cryptographic protocols, are generally not directly threatened by quantum computing. While quantum algorithms can speed up hash function attacks, the impact is similar to that on symmetric key encryption: the threat can be mitigated by increasing the output size of the hash function.

Therefore, the race is on to develop quantum-resistant cryptographic algorithms—often termed “post-quantum cryptography (PQC)”—to secure digital communications against the future capabilities of quantum computing. As the field of quantum computing advances, understanding and preparing for its impact on cryptography is crucial for safeguarding the digital landscape. Despite various expert predictions about the Q-Day, there’s no unified agreement on the timeline for achieving the 4,099 stable logical qubits mentioned above required by Shor’s algorithm to crack these encryption systems.

Reasons for Calm

Several indicators suggest that Q-Day is still far off, potentially decades into the future. These indicators are summarized below.

Required Capabilities

The journey towards fully operational quantum computing, particularly in the context of cryptanalysis, is often envisioned as a sprint towards the ominous Q-Day. However, long before the arrival of CRQC significant other milestones must be achieved. The timeline for CRQC realization is dependent on breakthroughs across multiple dimensions of quantum computing development. Observing academic publications and commercial use of quantum can give us another signal about how close we are to Q-Day.

Current state – Few hundred to a thousand physical qubits: Currently, quantum computing is at what can be described as a foundational level, where the focus is on increasing the physical qubit counts and improving qubit fidelity. This era, known as the Noisy Intermediate-Scale Quantum (NISQ), indicates that quantum computers are not yet advanced enough for fault-tolerance or large enough to achieve quantum supremacy. This stage is crucial for research and development; however, the current capabilities do not directly translate to practical utility, especially in cryptanalysis. The current stage is primarily about proving the concept, demonstrating the science, building the quantum computing R&D infrastructure, and understanding the fundamental properties of quantum systems. Quantum machines at this level are not yet useful for solving real-world problems. All universal quantum computing machines today are at this level. (A subset of quantum computing using a different approach – quantum annealing, is already in use on some narrow optimization problems. See below.)

Next year or two – One logical qubit: Within the next year or two we expect to see a logical qubit achieved by combining a large number of physical qubits, and lots of smart tinkering to enable error correction at the level useful for real use. The challenge of scaling up quantum systems to achieve this level of complexity is significant, requiring not just an increase in physical qubit count but a leap in the stability and coherence of these qubits. Today, no vendor has achieved this milestone. This will be the first indicator that we are moving from the NISQ era towards the Fault-Tolerant Quantum Computing (FTQC) era of commercially feasible quantum computers. At this point we will be hearing many more claims of “quantum advantage” or “quantum supremacy” when various vendors succeed in demonstrating that a programmable quantum computer can solve a problem that no classical computer can solve in any feasible amount of time, irrespective of the usefulness of the problem.

Unknown timeline – 100 logical qubits – scientific benefits: Once we are able to scale that achievement to a 100 or more error-correcting logical qubits we will start seeing significant scientific benefits on a set of scientific problems particularly well suited for quantum computing. The commercial feasibility of quantum computers will not be questioned anymore and increased funding will start flowing into quantum.

Unknown timeline – 1000 logical qubits – broad commercial benefits: Further scaling up to 1000 or more logical qubits is the ultimate goal. This level of quantum computing, which would initiate the wide commercial use of quantum computers, necessitates not only technological breakthroughs in quantum hardware but also in quantum algorithms, error correction, and system architecture. The “Assessing requirements to scale to practical quantum advantage” paper by Beverland et al. highlights the monumental task of scaling quantum computing to a level where it can solve problems beyond the reach of classical computers. This comprehensive study outlines a framework for estimating the quantum resources required for large-scale applications, emphasizing the need for hundreds of thousands to millions of physical qubits to realize practical quantum advantage. We are nowhere close to these capabilities.

Unknown timeline – 1000s logical qubits – CRQC: Further scaling will be required to achieve CRQC and signify the true arrival of the Q-Day. As mentioned, for a successful factorization of RSA-2048, the first cryptographically relevant number, we would require 4,099 logical qubits based on the Shor’s algorithm. With some advances in algorithm optimization we can see this number going down, but it will likely still be in thousands of logical qubits.

As you can see, even once we achieve a logical qubit and start getting some benefits over classical computing, achieving CRQC capability will present a few additional challenges:

• Massive Scale and Error Correction: Cryptanalysis tasks, like factoring large integers (a key challenge for breaking RSA encryption), require quantum computers of a scale and with error correction capabilities far beyond what is needed for economically viable applications. This is because cryptographic relevance demands not just any computation, but highly specific and complex computations with a high degree of accuracy.
• Quantum Error Correction: To run the large, complex algorithms needed for cryptanalysis without significant errors, quantum computers must implement robust quantum error correction schemes. Developing these schemes is a monumental challenge that involves creating a quantum computer with a significantly larger number of physical qubits to encode a smaller number of logical, error-corrected qubits.
• Technological and Theoretical Hurdles: Beyond hardware, there are theoretical challenges in algorithm development and optimization for cryptanalysis that are not as pressing for other types of quantum computing applications. The algorithms must not only exist but be refined and optimized for practical use.

Canary in a Coal Mine

To expand on the previous point: although the development of a cryptographically relevant quantum computer in the foreseeable future is plausible, the assessment of various potential use cases and their quantum computing requirements indicate that economically-viable quantum computers will precede those with cryptographic significance. Many experts in the field believe that quantum computers will first be utilized for economically-impactful computations before they achieve the capability to tackle cryptographic challenges.

In essence, the moment we start seeing universal quantum computers generating commercial advantages, it’s time to worry.

Expert Opinion

The “Quantum Threat Timeline Report 2023,” authored by Dr. Michele Mosca and Dr. Marco Piani, provides a comprehensive analysis of the timeline for when quantum computing could potentially break current cryptographic systems. This report, based on a survey of 37 leading experts in quantum computing from academia and industry, aims to offer an educated perspective on the proximity of the quantum threat by examining expert opinions on various aspects of quantum computing development. Results of the expert opinion on when quantum computers will be able to break RSA-2048 are summarized in the image below:

Despite the challenges in predicting the exact timeline due to the scientific and engineering breakthroughs required, there is a general agreement that steady progress is being made towards achieving key milestones necessary for a CRQC. The report highlights that about half of the respondents optimistically believe that there is more than a 50% likelihood that quantum computing could pose a threat to cryptography within a 15-year timeframe.

Strategic Preparedness and Policy Response

In May 2022, the White House issued the “National Security Memorandum on Promoting United States Leadership in Quantum Computing While Mitigating Risks to Vulnerable Cryptographic Systems” memorandum. In it the White House outlines United States’ commitment to transitioning cryptographic systems to quantum-resistant cryptography by 2035 as much as feasibly possible. If the White House, equipped with comprehensive intelligence and expert analyses, perceives a 13-year window as an appropriate timeframe for this mitigation to the extent is feasible, it suggests a belief that Q-Day is not immediately upon us.

Similarly, the timeline established by the National Institute of Standards and Technology (NIST) for finalizing quantum-resistant algorithm standards is by 2024, followed by a projected full rollout spanning an additional five to fifteen years. If the U.S. government had perceived Q-Day as an imminent event, it stands to reason that there would be a concerted effort to expedite this timeline significantly. However, the current schedule suggests a different perspective, one that sees the quantum threat as pressing yet manageable within the framework of a deliberate and phased approach over the next 10 to 15 years.

Energy Requirements to Break a Single Key with CRQC

RAND Corporation’s researchers recently published a pioneering analysis of the energy requirements necessary to operate a CRQC, shifting the focus from a qubit count metric to more tangible resources such as electricity consumption. This gives us another angle we can use to predict Q-Day.

The researchers extrapolated data from existing superconducting-transmon quantum computers, and made a rough estimate of about six watts per qubit for a future superconducting-transmon CRQC. This estimate, combined with a plausible spacetime volume, suggests that operating a CRQC to break one public key would require approximately 125 MW of electrical power, translating to an electricity cost of about $64,000 at current prices. These significant operational costs associated with running a CRQC, suggesting that, even after overcoming the monumental challenge of building such a computer, its operation would likely remain within the domain of nation-states and large organizations for an extended period.

Inability to Keep it Secret

The RAND Corporation’s article, “When a Quantum Computer Is Able to Break Our Encryption, It Won’t Be a Secret” presents yet another argument for why Q-Day is not an immediate threat, not even in secret government labs. The article underscores the difficulty of keeping significant advancements in quantum computing a secret, suggesting that the development of a CRQC will likely not occur clandestinely for several reasons: the competitive nature of the commercial quantum computing industry, the visibility of leading experts within the quantum computing field, the potential physical conspicuousness of a CRQC, and the relative technical ease of achieving commercial quantum applications compared to executing Shor’s algorithm. These factors collectively suggest that commercial quantum computing applications will precede and thus signal the advent of decryption capabilities, providing a buffer for vulnerable systems to mitigate the risks. In summary, according to the author, the worst-case scenario—a hostile actor covertly operating a CRQC for an extended period—is highly unlikely.

Reasons for Concern

On the other hand, many researchers argue that Q-Day may arrive sooner than many quantum scientists predict, urging immediate action to protect vulnerable data and networks. Recent advancements in quantum science suggest that the ability to decrypt using quantum technology could be realized much sooner than previously thought, maybe even within four to five years. This would shift the strategic calculus significantly, emphasizing the importance of preparing for quantum threats sooner rather than later.

Advances in Algorithms

As we’ve discussed, constructing increasingly powerful quantum computers is a significant challenge. New breakthroughs are announced weekly, and quantum computers continue to improve. Yet, we remain far away from achieving widespread commercial use, let alone reaching the capabilities of a CRQC. This year, we anticipate the announcement of a quantum chip equipped with 1000 physical qubits. However, it’s important to remember that for Shor’s algorithm, we need 4,099 stable logical qubits, which translates into millions of physical qubits.

However, there is another side of the scientific progress happening in parallel with building more powerful quantum computers. Mathematicians and scientists are continuously developing more efficient algorithms to achieve equivalent outcomes. To illustrate, let’s look at the evolution of Shor’s algorithm.

• In 2012, Fowler et al. introduced a new method for implementing Shor’s algorithm. To factor a 2,048-bit RSA integer with a gate error rate of 0.1%, they required approximately 1 billion qubits.
• By 2017, O’Gorman et al. had optimized the algorithm further, devising a strategy that needed only 230 million qubits to factor a 2,048-bit RSA integer.
• In 2019, Gheorghiu further reduced this requirement to 170 million qubits.
• Significantly, Gidney and Ekerå in 2019 achieved a breakthrough, estimating that only 20 million qubits were needed to factor a 2,048-bit RSA integer.

The heavy optimization of algorithms has dramatically reduced the qubit requirement for Shor’s algorithm from 1 billion to “only” 20 million within seven years.

This is a cause for attention. Normal science progresses through the steady accumulation of knowledge within a consistent framework. However, the field of quantum computing, especially on the algorithm optimization front, appears poised for a radical discovery that could overturn all our strategic assumptions.

It’s worth mentioning that in 2022, a group of Chinese scientists published a paper titled “Factoring integers with sublinear resources on a superconducting quantum processor.” In it, they presented a new algorithm suggesting that a quantum circuit with 372 physical qubits could potentially challenge the RSA-2048 encryption algorithm. If proven true, this would imply that our current quantum computing capabilities, with around 1,000 physical noisy qubits, could already be sufficient to compromise most existing cryptographic systems. This article was quickly discredited. Nevertheless, it represents precisely the kind of scenario that warrants concern—a sudden scientific breakthrough capable of dramatically altering the security landscape.

Adiabatic Quantum Computing (AQC)

The whole discussion above was referring to Universal Quantum Computing, also known as Gate-Based Quantum Computing. This is the more familiar model of quantum computing which uses quantum gates to perform operations on qubits, the quantum analogs of classical bits. This is known as “universal” because, in theory, it can perform any computation that a classical computer can, but potentially much faster for certain types of problems.

Adiabatic Quantum Computing or Quantum Annealing (for the purpose of this article we can consider these terms the same), is a specialized subset of quantum computing focused on solving optimization problems by finding the minimum (or maximum) of a given function over a set of possible solutions. For problems that can be presented as optimization problems, quantum annealers have shown great potential in solving them in a way that classical computers struggle with.

Researchers have been exploring ways to turn factorization, the process underlying Q-Day, into an optimization problem, bypassing the need for Shor’s algorithm. Microsoft published “Factoring as Optimization” paper already in 2002.

In 2019 a group of Chinese scientists published a paper “Factoring larger integers with fewer qubits via quantum annealing with optimized parameters” in which they demonstrated factorization of 1,005,973, a 20 bits number, using only 89 noisy qubits. In comparison, using Shor’s algorithm to factor the same number (1,005,973) would require 41 logical qubits (many thousand noisy qubits). Authors proposed that a RSA-768 encryption could be factorized with 147,454 noisy qubits—a fraction of what was once thought necessary. They concluded their paper with the following statement: “This shows that quantum annealing machines, such as those by D-Wave, may be close to cracking practical RSA codes, while universal quantum-circuit-based computers may be many years away from attacking RSA.”

For reference, D-Wave the latest Advantage line of quantum computers currently have 5,640 qubits. However, it is also important to note that either the complexity or the problem or the number of required qubits grow exponentially as the factorization grows. In other words, being able to factor RSA-768 with 147,454 noisy qubits, doesn’t mean that around 500,000 qubits would be able to factorize RSA-2048, the first cryptographically relevant number.

Nevertheless, since gate-based, universal quantum computers require full error correction for factoring large integers, and this is still beyond our technical capabilities, it seems more likely that this challenge will be better met with rapidly developing quantum annealers and advances in algorithms.

Conclusion

The development of universal gate-based quantum computing hardware follows a discernible trajectory, allowing for predictions to be made based on extrapolation and expert opinions. From such analyses, it’s clear why many are concluding that Q-Day remains at least a decade away.

However, I am more concerned about the dynamic nature of developments in other areas of quantum computing, such as algorithm optimization, quantum annealing, as well as the substantial investments and interest from investors and nation-states in advancing this field. These domains of quantum computing could experience sudden, transformative breakthroughs due to the influx of new scientists focused on exploring them. Such breakthroughs could dramatically alter the current trajectory, potentially bringing Q-Day much closer than anticipated and rendering current strategic assumptions obsolete.

To moderate my concerns, it’s important to note that truly unexpected breakthroughs are rare and typically, experts within the field have some visibility into the roadmap that leads to these advances. None of the recent scholarly articles or expert analyses I have reviewed suggest a path to a game-changing discovery.

To deliver on the announcement made in the introduction: my prediction, which is grounded not in any specific expertise but only on the research I have summarized above, is that Q-Day will likely occur in less than 10 years but more than 5. My predictions is also informed by these few ideas:

• I believe that expert opinion methodologies used above are often influenced by experts’ own areas of focus and inherent biases. If majority of the 37 experts polled are focused on advancing the Universal Quantum Computing, they might not be aware of the latest advancements in quantum annealing.
• Similarly, I believe that some of the experts polled, focused on their own areas, might not be aware of the potential acceleration in development that could be achieved if algorithms, software, and hardware are developed in concert. At least some experts agree with me on this. EPiQC, a multidisciplinary collaboration across five universities led by the University of Chicago, aims to develop algorithms, software, and hardware in tandem. This initiative seeks to close the gap between algorithms and devices by 100-1000 times, potentially accelerating quantum computing progress by 10-20 years.
• Moreover, the likelihood of significant breakthroughs in any of these fields increases in direct proportion to the investment in the field. With the anticipated transition from the Noisy Intermediate-Scale Quantum (NISQ) era towards quantum supremacy, we can expect a substantial influx of both funding and researchers into quantum computing.
• Contrary to the assessment by the RAND Corporation that CRQC cannot be developed covertly, I believe otherwise. I believe there are regimes that have already demonstrated their ability to develop significant scientific breakthroughs covertly. This leads me to believe that on a topic as strategic for national security as this, there are potentially significant advancements happening in secret.

While the exact arrival date of Q-Day remains uncertain, the necessity for immediate and strategic preparation does not. In light of the potential for CRQC to break cybersecurity, and the strategic “Harvest Now, Decrypt Later” (HNDL) threat posed by adversaries, it is clear that the time for action is now. The Mosca inequality, which underscores the importance of considering the shelf-life of encrypted data, serves as a critical reminder that the quantum threat is not just a future concern but a present reality.

If you are responsible for managing cyber risk, complacency is not an option, regardless of the precise timeline for the advent of CRQC. Developing crypto-agility and establishing layered defenses against quantum threats are essential measures that you have to kick off right now.