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:

New method predicts spin dynamics of materials for quantum computing
Researchers at UC Santa Cruz have developed a theoretical foundation and new computational tools for predicting a material's spin dynamics, a key property for building solid-state quantum computing platforms and other applications of spintronics.
Speeding-up quantum computing using giant atomic ions
An international team of researchers have found a new way to speed up quantum computing that could pave the way for huge leaps forward in computer processing power.
Boson particles discovery provides insights for quantum computing
Researchers working on a U.S. Army project discovered a key insight for the development of quantum devices and quantum computers.
In leap for quantum computing, silicon quantum bits establish a long-distance relationship
In an important step forward in the quest to build a quantum computer using silicon-based hardware, researchers at Princeton have succeeded in making possible the exchange of information between two qubits located relatively far apart -- about the length of a grain of rice, which is a considerable distance on a computer chip.
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.
More Quantum Computing News and Quantum Computing Current Events

Trending Science News

Current Coronavirus (COVID-19) News

Top Science Podcasts

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

Making Amends
What makes a true apology? What does it mean to make amends for past mistakes? This hour, TED speakers explore how repairing the wrongs of the past is the first step toward healing for the future. Guests include historian and preservationist Brent Leggs, law professor Martha Minow, librarian Dawn Wacek, and playwright V (formerly Eve Ensler).
Now Playing: Science for the People

#565 The Great Wide Indoors
We're all spending a bit more time indoors this summer than we probably figured. But did you ever stop to think about why the places we live and work as designed the way they are? And how they could be designed better? We're talking with Emily Anthes about her new book "The Great Indoors: The Surprising Science of how Buildings Shape our Behavior, Health and Happiness".
Now Playing: Radiolab

The Third. A TED Talk.
Jad gives a TED talk about his life as a journalist and how Radiolab has evolved over the years. Here's how TED described it:How do you end a story? Host of Radiolab Jad Abumrad tells how his search for an answer led him home to the mountains of Tennessee, where he met an unexpected teacher: Dolly Parton.Jad Nicholas Abumrad is a Lebanese-American radio host, composer and producer. He is the founder of the syndicated public radio program Radiolab, which is broadcast on over 600 radio stations nationwide and is downloaded more than 120 million times a year as a podcast. He also created More Perfect, a podcast that tells the stories behind the Supreme Court's most famous decisions. And most recently, Dolly Parton's America, a nine-episode podcast exploring the life and times of the iconic country music star. Abumrad has received three Peabody Awards and was named a MacArthur Fellow in 2011.