A new hope of quantum computers for factorizations of RSA with a thousand-fold excess

There are two types of quantum computers: universal quantum computers and dedicated ones, the state-of-the-art one of which is the commercial quantum computer developed by D-Wave Quantum Computing Company in Canada.

It has been considered that the Shor’s algorithm could be viewed as the unique and powerful quantum algorithm for cryptanalysis of RSA (widely used in e-government and e-commerce) while various media and researchers have pointed out that RSA would been as soon collapsed as the emergence of universal quantum computers. However, Nature[1] and Science reported[2, 3] universal quantum computer wont’s be working successfully before a long period. Both Prof. John Martinis[2] (UC Santa Barbara, joining Google since 2014) and Prof. Matthias Troyer[1] (now as the principal researcher of Microsoft’s quantum computing program) also agreed that it would be years before the quantum computers are able to achieve some practical applications, including the code-cracking.

Under the project of the Key Program of National Natural Science Foundation of China, Chao Wang’s team of Shanghai University has devoted itself to the factoring problems by using D-Wave quantum computer, in developing a new way based on deciphering RSA by quantum computing, although the D-Wave machine has nothing to do with the cryptography at the beginning, which is initially used only for image processing (Google), software verification (Lockheed Martin) and some more areas.

Wang’s team showed optimistic potentials of quantum annealing algorithm and D-Wave quantum computer for deciphering the RSA cryptosystem. Furthermore, the team has also shown that the D-Wave machine may have some more powerful attack of cracking practical RSA codes than by using Shor’s algorithm in a universal quantum computer. Even if, recently the latest IBM Q System One™ (Jan 8. 2019) has declared that it can effectively implement Shor’s algorithm, it could factor up to 10-bit integers in theory, whereas D-Wave can factor even 20-bit integers (with a thousand-fold excess). In fact, current quantum-circuit-based quantum chips, including the Google’s 72 qubit quantum computer “Bristlecone”, are limited by many factors such as error correction that they haven’t provided the evidence of being able to realize the factorization yet.

The research results will be published on SCIENCE CHINA Physics, Mechanics & Astronomy (vol. 62, 6. Corresponding author: Chao Wang), highlighted [4] by Xin-Mei Wang, the honorary director of CACR (Chinese Association for Cryptologic Research).

1 How the quantum tunneling can help D-Wave machine establish superiority over others?

The D-Wave One machine was emerged in 2011, which works near absolute zero (15 mK) with very low power consumption (25kW for the moment), far less than the power of high-performance computers, the development of which is limited by Moore’s Law and Dennard scaling.

As shown in the Fig. 2, D-Wave quantum annealing algorithm, working near absolute zero, can activate the quantum tunneling effects, allowing for jumping from the local sub-optimum to approximate, or even achieving, the global optimum in the exponential-scale searching space, which is the unique advantage of D-Wave machine compared to the other classical ones.

Quantum tunneling effect means that the quantum fluctuations enable the quantum directly penetrate through the barrier with higher energy than itself. The quantum states can change their self-rotations directions by two different ways: as the result of quantum fluctuations and/or thermal fluctuations. The thermal annealing will break the quantum states so that the quantum system requires the tunneling procedure only affected by quantum fluctuations. Actually, the thermal dynamics of qubits and quantum tunneling effect have their own freeze-out time respectively. The quantum annealing depends on the energy difference between the ground state and the second first excited state. Cooling down the system until both the quantum tunneling and thermal fluctuations eventually cease, then the system can obtain the final quantum state. By repeating the cooling procedure under different temperatures, the system can effectively realize quantum computing by quantum annealing.

2 Why the potentials of D-Wave for code-cracking have been ignored?

Lockheed Martin Corporation, a global munitioner, first entered into an agreement to purchase D-Wave One for most challenging computation problems, like finding error codes from an F-16 aircraft (F-35[5] in future). Then, researchers from Google, NASA, Los Alamos National Laboratory, Harvard University, and Tohoku University applied the D-Wave annealer to more than 100 applications spanning image processing, protein folding, traffic flow optimization, air traffic control, tsunami evacuation etc. Thus, this is why the applications of D-Wave quantum computer on cryptography design and analysis have been ignored.

In accordance with the analysis of Google, people within our circles considered that the dedicated quantum computers with quantum annealing technology are extreme importance to the information technology. This is because the quantum computers can find approximate answers to a kind of important problems in computer science, which can only be truly solved by exhaustively trying every possible solution. Therefore, it has laid down a solid foundation for the cryptographic applications by quantum annealing.

Prof. Xin-Mei Wang pointed out in the highlight [4] that it is important to explore the potential of D-Wave quantum computer for attacking other cryptosystems. It is well-known that there are three kinds of practical difficulties for constructing highly secure cryptography. Other than the difficulty of factoring problems, the discrete logarithm problem and elliptical discrete logarithm problem (like ECC, the basis for the second-generation identity card in China) provide a stronger way to resist the attacks from the quantum computers than others. Thus, the feasibility of D-Wave quantum computer for solving the latter two problems should be further considered.

3 What else can D-Wave machine do?

In late 2017, Professor Wang’s group first realized the cryptographic components designing experiments via D-Wave 2000Q System by transforming the cryptographic functions design problem with multiple criteria to multi-object optimization problems so that the mathematical problem can be mapped to an optimization problem by searching in the exponential-scale solutions space.

Although D-Wave machine is designed for special purpose, different from the universal quantum computer, we think it can be widely used in various areas, which is completely different from the early version of classical computers in the early stage of the development of electronic computers. Currently, D-Wave has received multi-round investments since 2013, including In-Q-Tel (supporting Central Intelligence Agency), and aims at practically commercialized applications.

D-Wave is designed ingeniously to realize the quantum annealing with quantum tunneling effects that enables some NP problems to be able to potentially solve in polynomial time. Nature reported it can be widely used in many areas, including cryptography, image processing, pattern recognition & machine learning, financial analysis, bioinformatics, emotion analysis, and so on.

Google is further exploring the combination of D-Wave quantum computer and self-driving cars towards an intelligent way more similar to the human brain for obstacle recognition and better navigation. On the other hand, Volkswagen and Chao Wang’s group are also devoted themselves to the quantum applications of smart transportation.

We firmly believe that physicists will collaborate with information scientists to develop more applications on smart city and urban refined management over next decade.

###

This research was funded by the National Natural Science Foundation of China (No. 61332019, 61572304, and 61272096).

Reference

[1] Elizabeth Gibney. Physics: quantum computer quest. Nature News Feature 516: 25-26. Dec. 3 2014.

[2] Adrian Cho. DOE pushes for useful quantum computing. Science 359, 6372: 141-142. Jan. 12 2018.

[3] Jeffrey Brainard. What’s coming up in 2018. Science 359, 6371: 10-12. Jan. 05 2018.

[4] X. M. Wang, Quest towards”factoring larger integers with commercial D-Wave quantum annealing machines”, Sci. China-Phys. Mech. Astron. 62, 060331 (2019).

[5]George Leopold. Quantum leaps needed for new computer approach. Defense System. Dec. 09 2016. https://defensesystems.com/articles/2016/12/09/quantum.aspx

See the article:
W. C. Peng, et al. Factoring larger integers with fewer qubits via quantum annealing with optimized parameters, Sci. China-Phys. Mech. Astron. 62(6), 060311 (2019) https://doi.org/10.1007/s11433-018-9307-1