Two Chinese Quantum Information Leaders Receive FOCS 2021 "Time Tested Award"

On December 24, 2021, the awards for the 62nd Annual IEEE Foundations of Computer Science Symposium (FOCS 2021) were announced! FOCS, funded by the IEEE Computer Society's Special Committee on Foundations of Computer Mathematics, is the top international conference in computer science and, along with the ACM Theory of Computing Conference (STOC), the two top conferences in theoretical computer science.

The FOCS 2021 awards include the Best Paper Award, the Best Student Paper Award, and the Time Test Award. Yao Qizhi, a member of the Chinese Academy of Sciences, director of Tsinghua University's Institute of Cross-Information and director of Tsinghua University's Quantum Information Center, and Shi Yao-cheng, head of Alibaba's Dharmakaya Quantum Lab, along with two other authors, won the award for their 2001 paper "Information Complexity and the Direct Sum Problem for Simultaneous Message Complexity" published in 2001, won the Time Test Award.

As the leading figures in quantum information in China, Yao and Shi lead Tsinghua University's Institute of Cross-Cutting Research and Dharma Institute's Quantum Laboratory, respectively, which are the leading quantum information research institutions in China.

We briefly review this paper.

Abstract of the paper.

Given m copies of the same problem, does solving these m problems require m times the resources? This is the direct sum problem - a fundamental problem that has been studied in many computational models. Researchers have studied this problem in the synchronous message (SM) communication model previously proposed by Yao Chi-Chi. It is well known that the n-bit string equality problem has SM complexity Θ(√n). They prove that m copies of the solution problem have complexity Ω(m√n); the best lower bound that can be proved using previously known techniques is Ω(√mn). They also proved similar lower bounds for certain Boolean combinations of multiple copies of the equation function. These results can be generalized to a broader class of functions. They introduce a new notion of information complexity related to SM complexity and with good straightforward sum properties. This notion is used as a tool to prove the above results; it seems to be quite powerful and may be of independent interest.

In addition, Mao Xiao, who is a Master of Engineering student at the Massachusetts Institute of Technology (MIT), won the FOCS 2021 Best Student Paper Award for his paper "Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance". Mao Xiao, who attended Yali High School in Changsha, is known to be a silver medalist in the 2017 International Olympiad in Informatics and received a dual degree in mathematics and computer science from MIT as an undergraduate.

About Yao Zhizhi

Born in Shanghai, China in 1946, Yao is a computer scientist who received the Turing Award in 2000, a member of the Chinese Academy of Sciences, a foreign member of the American Academy of Sciences, and the director of the Institute of Cross-Information at Tsinghua University. His research interests include the theory of computation and its applications in cryptography and quantum computing, being the first to propose the complexity of quantum communication and to propose the distributed quantum computing model, which later became the basis for distributed quantum algorithms and the security of quantum communication protocols.

In 2021, the School of Cross-Information of Tsinghua University formally established the Quantum Information Class, with Academician Yao Qizhi as the chief professor. This is the first undergraduate talent training program in quantum information at Tsinghua University, and the third program founded by Academician Yao after the experimental computer science class "Yao class" and the artificial intelligence class "Zhi class".

About Yao-Wei Shi

He received his undergraduate degree from Peking University in 1997 and later received his Ph.D. in computer science from Princeton University, where he was a student of Academician Yao Qiqi. His research interests include quantum algorithms and complexity, quantum communication complexity, classical simulation of quantum systems and quantum computing, quantum informatics, and quantum cryptography. He was a tenured professor at the University of Michigan, Ann Arbor before returning to China. he joined Alibaba in 2017 and is currently the head of the Quantum Lab at Dharmakaya.