Penghui Yao
pyao@nju.edu.cn
Education
2008-2014 Ph.D. in Computer Science, National University of Singapore
2006-2008 Master's Degree in Computer Science, Institute of Software, Chinese Academy of Sciences
2002-2006 Bachelor's Degree in Mathematics, East Chinese Normal University
Experience
2022-Present Researcher, Hefei National Laboratory
2024-Present Professor, Nanjing University
2018-2024 Associate Professor, Nanjing University*
Overview of Academic Research
Prof. Yao’s research interest is theory of quantum computing, focusing on quantum algorithms, quantum complexity theory and quantum information theory.
His/her major achievements include:
* Proved an exponential separation between quantum communication complexity and quantum information complexity; refuting strong direct sum conjecture for quantum communication complexity.
* Initiated the study of noisy MIP* by systematically exploring theory of Pauli analysis; characterizing the computational power of noisy two-prover one-round MIP*
* Establishing the first superlinear lower bound on QAC0
Research Directions/Fields:
Distributed quantum algorithms and quantum learning algorithm
Quantum computational complexity
Quantum information theory and quantum communication complexity
Representative Publications
1.Anurag Anshu, Yangjing Dong, Fengning Ou, Penghui Yao; On the Computational Power of QAC0 with Barely Superlinear Ancillae, Proceedings of the 57th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2025)
2.Minglong Qin; Penghui Yao; Nonlocal Games with Noisy Maximally Entangled States are Decidable, SIAM Journal of Computing, 2021.
3.Srinivasan Arunachalam; Penghui Yao ; Positive spectrahedra: invariance principles and pseudorandom generators, Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022)
4.Yangjing Dong; Honghao Fu; Anand Natarajan; Minglong Qin; Haochen Xu; Penghui Yao; The Computational Advantage of MIP^∗ Vanishes in the Presence of Noise, 39th Computational Complexity Conference (CCC 2024)
5.Zongbo Bao; Penghui Yao ; On Testing and Learning Quantum Junta Channels，COLT 2023, Journal version: Transactions on Pattern Analysis and Machine Intelligence 2025