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. A sufficiently powerful and error-correcting quantum computer would break currently deployed public-key cryptography which is based on the factorisation problem or the discrete logarithm problem (on elliptic curves). Since Shor‘s publication (1994) quantum algorithms with polynomial runtime have existed for solving these problems. 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.

Before error-correcting quantum computers will be established, an era of NISQ technologies is expected in which errors are not corrected (only mitigated by hardware-related methods if necessary). Hence, 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.

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 the current version of the study, a separate evaluation scheme is presented 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

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

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

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.