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.
Junjie Wu, Yong Liu, Baida Zhang, Xianmin Jin, Yang Wang, Huiquan Wang, and Xuejun Yang are the authors of the paper titled " A benchmark test of boson sampling on Tianhe-2 supercomputer ". The paper has been published inNational Science Review2018; 5: 715-720.