image: (a) The Tianhe-2 supercomputer used for permanent calculation in simulating the boson sampling performance. (b) A small photonic chip could perform the same boson sampling task in the quantum computing protocol. view more
Credit: ©Science China Press
Quantum 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.
###
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.
Journal
National Science Review