Nav: Home

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

April 03, 2019

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).


[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.

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)

Science China Press

Related Quantum Computing Articles:

A platform for stable quantum computing, a playground for exotic physics
Harvard University researchers have demonstrated the first material that can have both strongly correlated electron interactions and topological properties, which not only paves the way for more stable quantum computing but also an entirely new platform to explore the wild world of exotic physics.
Diversity may be key to reducing errors in quantum computing
In quantum computing, as in team building, a little diversity can help get the job done better, computer scientists have discovered.
'Valley states' in this 2D material could potentially be used for quantum computing
New research on 2-dimensional tungsten disulfide (WS2) could open the door to advances in quantum computing.
Sound of the future: A new analog to quantum computing
In a paper published in Nature Research's journal, Communications Physics, researchers in the University of Arizona Department of Materials Science and Engineering have demonstrated the possibility for acoustic waves in a classical environment to do the work of quantum information processing without the time limitations and fragility.
Imaging of exotic quantum particles as building blocks for quantum computing
Researchers have imaged an exotic quantum particle -- called a Majorana fermion -- that can be used as a building block for future qubits and eventually the realization of quantum computers.
Virginia Tech researchers lead breakthrough in quantum computing
A team of Virginia Tech chemistry and physics researchers have advanced quantum simulation by devising an algorithm that can more efficiently calculate the properties of molecules on a noisy quantum computer.
Limitation exposed in promising quantum computing material
Physicists have theorized that a new type of material, called a three-dimensional (3-D) topological insulator (TI), could be a candidate to create qubits for quantum computing due to its special properties.
New material shows high potential for quantum computing
A joint team of scientists at the University of California, Riverside, and the Massachusetts Institute of Technology is getting closer to confirming the existence of an exotic quantum particle called Majorana fermion, crucial for fault-tolerant quantum computing -- the kind of quantum computing that addresses errors during its operation.
A sound idea: a step towards quantum computing
Researchers at the University of Tsukuba and the University of Pittsburgh have developed a new method for using lasers to create tiny lattice waves inside silicon crystals that can encode quantum information.
Quantum computing boost from vapour stabilising technique
A technique to stabilise alkali metal vapour density using gold nanoparticles, so electrons can be accessed for applications including quantum computing, atom cooling and precision measurements, has been patented by scientists at the University of Bath.
More Quantum Computing News and Quantum Computing Current Events

Top Science Podcasts

We have hand picked the top science podcasts of 2019.
Now Playing: TED Radio Hour

Accessing Better Health
Essential health care is a right, not a privilege ... or is it? This hour, TED speakers explore how we can give everyone access to a healthier way of life, despite who you are or where you live. Guests include physician Raj Panjabi, former NYC health commissioner Mary Bassett, researcher Michael Hendryx, and neuroscientist Rachel Wurzman.
Now Playing: Science for the People

#543 Give a Nerd a Gift
Yup, you guessed it... it's Science for the People's annual holiday episode that helps you figure out what sciency books and gifts to get that special nerd on your list. Or maybe you're looking to build up your reading list for the holiday break and a geeky Christmas sweater to wear to an upcoming party. Returning are pop-science power-readers John Dupuis and Joanne Manaster to dish on the best science books they read this past year. And Rachelle Saunders and Bethany Brookshire squee in delight over some truly delightful science-themed non-book objects for those whose bookshelves are already full. Since...
Now Playing: Radiolab

An Announcement from Radiolab