The status of quantum computer development

The aim of this study is to assess the state of development of current technologies for the realisation of a cryptographically relevant quantum computer and cryptographically relevant quantum algorithms.

Today, the security of digital infrastructures is largely based on public-key cryptography (also known as "asymmetric cryptography"). This in turn is essentially based on the assumed difficulty of certain mathematical problems, for example the factorisation problem or the discrete logarithm problem (on elliptic curves). According to the current state of knowledge, the common public-key cryptography used today cannot be broken with classical computers. However, the situation will change fundamentally when universal quantum computers of sufficient performance are available. Already in 1994, the mathematician Peter Shor published quantum algorithms, which can efficiently solve the mathematical problems mentioned above. Other quantum algorithms such as Grover's search algorithm and Simon's algorithm will have implications for symmetric cryptography, in particular for key lengths and operating modes. In recent years, a number of additional algorithms for the cryptanalysis of (asymmetric) protocols have been presented which can also be implemented on so-called NISQ (Noisy Intermediate-Scale Quantum) computers.

The central challenge in the development of quantum computers is their susceptibility to errors. Quantum systems are very sensitive to disturbances and therefore require an elaborate error correction, which is called quantum error correction (QEC). Currently realized quantum computers, where errors are not corrected (and only mitigated by hardware-related methods if necessary) are called Noisy Intermediate Scale Quantum (NISQ) computers. These are considered an intermediate stage on the way to fault-tolerant and universally programmable quantum computers. Here, due to the error probability, only limited algorithmic depth is available. Creative possibilities stemming from the inherent degrees of freedom of the hardware and alternative programming paradigms arise when developing algorithms for NISQ computers. The resulting solutions are generally heuristic in nature and lack a mathematical proof of convergence or a resource analysis. This is in particular the case for algorithms in the context of cryptoanalysis of (asymmetric) schemes.

Evaluation schemes in the study

In the first version of the study, an evauation model was developed to categorise quantum computing technologies. It is shown in the following figure.

Figure 1: Levels of development towards a fault-tolerant quantum computer Source: Federal Office for Information Security

In version 2.0 of the study, a separate evaluation scheme is introduced which allows further consideration of the field of NISQ algorithms. We find that these algorithms often belong to the leftmost branch of Figure 2 while, in contrast, the algorithms by Shor mentioned above fit into the rightmost branch.

Figure 2: Layered evaluation scheme for quantum algorithms based on fault-tolerant quantum computing (right) and NISQ (left) Source: Federal Office for Information Security

To analyse the state of development of cyptographically relevant quantum computing requires the joint consideration of hardware and algorithms, as illustrated in the following figure.

Figure 3: Quantum computing dependency graph between algorithms and hardware Source: Federal Office for Information Security

Current state (Version 2.1)

The current technologies identified in the study are categorised as follows according to the above evaluation scheme.

Figure 4: Evaluation of the main platforms following the developed scheme Source: Federal Office for Information Security

Looking ahead, the conclusion of the study is that quantum computing is making steady progress towards cryptanalytic relevance according to the reliable mainstream (fault-tolerant (improved) Shor algorithm, executed either on a superconducting system with the surface code or an ion-based system with the color code). Major roadblocks in this scenario were resolved in 2024, bringing us a lot closer to this goal even without large disruptions. Our conservative estimate is that cryptographically relevant quantum computers are likely to be available within 16 years.

Moreover, there are now a plethora of new developments in error correction and mitigation as well as hardware with the large progress in neutral atoms. A lot more can move and surprise, and most of possible disruptive results in this context could accelerate the development to below a decade.

Regarding NISQ algorithms, the study currently concludes that the limited evidence available does not yet permit a conclusive assessment. However, it makes a cautious assumption of low relevance for cryptanalysis.