# Tianhe-2 supercomputer works out the criterion for quantum supremacy

October 30, 2018Quantum supremacy refers to the super strong calculation capacity of a quantum computer to surpass that of any classical computer. So far, such a quantum computer has not been physically made, but as with the rapid development of quantum technologies in recent years, the voice for pursuing the superiority by quantum computing is more loudly heard and how to quantitatively define the criteria of quantum supremacy becomes a key science question. Recently, a world's first criterion for quantum supremacy was issued, in a research jointly led by Prof. Junjie Wu in National University of Defense Technology and Prof. Xianmin Jin in Shanghai Jiao Tong University. They reported the time needed to calculate boson sampling, a typical task that quantum computers would excel at, in a most powerful classical supercomputer, and the paper was published in

*National Science Review*.

Boson sampling, as introduced by one of the authors, is to sample the distribution of photons (bosons), and theoretically takes only polynomial time by quantum computers but exponential time by classical computers, showing quite evident quantum advantages as the number of photons involved in the boson sampling system increases. Besides, boson sampling, essentially an analog quantum computing protocol, maps the task directly in the photonic quantum system, and hence is much easier to implement than those based on universal quantum computing. Therefore, the task for boson sampling can be a very good candidate for defining quantum supremacy, for its preference to quantum computing over classical computing and its relative easier realization in the near future. Once a quantum computer can perform boson sampling task for a photon number larger and calculation time shorter than the best classical computer, the quantum supremacy is claimed to be achieved.

In the research led by Prof. Junjie Wu and Prof. Xianmin Jin, the boson sampling task was performed on Tianhe-2 supercomputer, which ever topped the world rank of supercomputers during 2013-2016, and still represents the tier one level of computing power that classical computers could ever achieve. The permanent calculation is a core part for theoretically performing boson sampling on a classical computer. If one just calculate the permanent directly based on its definition, it requires an algorithm with time complexity O(n!* n). The researchers used two improved algorithm, Ryser's algorithm and BB/FG's algorithm, both in the time complexity of O(n2* 2n). By performing matrix calculation on up to 312?000 CPU cores of Tianhe-2, they inferred that the boson sampling task for 50 photons requires 100 minutes using the then most efficient computer and algorithms. Put it in other words, if a physical quantum device could 50-photon boson sampling in less than 100 minutes, it achieves the quantum supremacy.

If such a quantum setup could be experimentally made, it quite likely will be very quick as photons travel in the speed of light, but many challenges still lie ahead for its experimental implementation. Prof. Xianmin Jin used to conduct pioneering research on boson sampling experiment in Oxford University. So far, the world record for the photon number in boson sampling experiment still remains no more than five. There's still a long way to go towards the ideal quantum supremacy.

An author for this Tianhe-2 project also pointed out that, as the limit for classical computing power would keep increasing with the improvement of supercomputers, and more efficient permanent calculation algorithms would emerge that require a time complexity less than O(n2* 2n), the time required for 50-photon boson sampling may be further reduced, making an even more stringent criterion for quantum supremacy. Meanwhile, a task to demonstrate quantum supremacy does not necessarily have any real applications. It is worthwhile to realize a wide range of useful applicable fields by quantum computing while carrying on the pursuit of quantum supremacy.

-end-

See the article:Junjie Wu, Yong Liu, Baida Zhang, Xianmin Jin, Yang Wang, Huiquan Wang, and Xuejun Yang

A benchmark test of boson sampling on Tianhe-2 supercomputer

*Natl Sci Rev*2018; 5: 715-720

https://doi.org/10.1093/nsr/nwy079

The

*National Science Review*is the first comprehensive scholarly journal released in English in China that is aimed at linking the country's rapidly advancing community of scientists with the global frontiers of science and technology. The journal also aims to shine a worldwide spotlight on scientific research advances across China.

Science China Press

**Related Quantum Computing Articles:**

A molecular approach to quantum computing

Molecules in quantum superposition could help in the development of quantum computers.

Molecules in quantum superposition could help in the development of quantum computers.

Cosmic rays may soon stymie quantum computing

Infinitesimally low levels of radiation, such as from incoming cosmic rays, may soon stymie progress in quantum computing.

Infinitesimally low levels of radiation, such as from incoming cosmic rays, may soon stymie progress in quantum computing.

UVA pioneers study of genetic diseases with quantum computing

Scientists are harnessing the mind-bending potential of quantum computers to help us understand genetic diseases - even before quantum computers are a thing.

Scientists are harnessing the mind-bending potential of quantum computers to help us understand genetic diseases - even before quantum computers are a thing.

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.

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.

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.

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.

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.

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.

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.

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.

## 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**

**Listen Again: IRL Online**

Original broadcast date: March 20, 2020. Our online lives are now entirely interwoven with our real lives. But the laws that govern real life don't apply online. This hour, TED speakers explore rules to navigate this vast virtual space.

**Now Playing: Science for the People**

**#574 State of the Heart**

This week we focus on heart disease, heart failure, what blood pressure is and why it's bad when it's high. Host Rachelle Saunders talks with physician, clinical researcher, and writer Haider Warraich about his book "State of the Heart: Exploring the History, Science, and Future of Cardiac Disease" and the ails of our hearts.

**Now Playing: Radiolab**

**Falling**

There are so many ways to fallin love, asleep, even flat on your face. This hour, Radiolab dives into stories of great falls. We jump into a black hole, take a trip over Niagara Falls, upend some myths about falling cats, and plunge into our favorite songs about falling. Support Radiolab by becoming a member today at Radiolab.org/donate.