# Penghui Yao's homepage

## Contact

- Email: phyao1985#gmail.com
- Office: Room #502 Department of Computer Science and Technology, Xianlin Campus of Nanjing University

## Short Bio

I am an associate professor in the Theory Group of the Department of Computer Science and Technology at Nanjing University. I am a member of CS Theory group.

I obtained Bsc. from East China Normal University majored in mathematics and Ph.D. degree from Centre for Quantum Technologies, National University of Singapore fortunately supervised by Rahul Jain and Miklos Santha. Prior to joining Nanjing University, I was a postdoctoral researcher at Centrum Wiskunde Informatica(CWI), then Institute for Quantum Computing (IQC) at University of Waterloo, then Hartree postdoctoral research fellow at Joint center for Quantum Information and Computer Science (QuICS), University of Maryland. My full cv is here.

## Research interest

I am interested in all applications of information theory and Fourier analysis in quantum computing and complexity theory. More specifically,Quantum computational complexity

Communication complexity and information complexity

Fourier analysis in theoretical computer science and quantum computation

Derandomization

## Current students

Minglong Qin (Ph.D., 2019.4- )

Mingnan Zhao (Ph.D., 2020.9- )

Xudong Wu (Ph.D. coadvised with Yitong Yin, 2020.9-)

Yangjing Dong (Ph.D. 2021.9-)

Zekun Ye (Ph.D., 2021.9-)

Zongbo Bao (Msc. 2021.9- )

Haigang Zhou (Ph.D., 2023.9 -)

## Alumni

Changsheng Wang (MSc., 2020.9-2023.7) Now Microsoft (Suzhou)

## Interns

We have a few intern positions on TCS/quantum computing . Please drop me an email if you are interested.2020.9-2021.1: Tingjia Cao (Bsc. Fudan University, now Ph.D. University of Wisconsin-Madison)

2020.12-2021.7: Ziyi Guan (Bsc. CMU, now Ph.D. EPFL)

2020.12-2022.1 : Yunqi Huang (Bsc. Sun Yat-sen University, now Ph.D. University of Technology, Sydney)

2023.9- : Yizhou Yan (Bsc. Southern University of Science and Technology)

## Services

Program Committee: QIP 2019, TQC 2021, TQC 2022, QIP 2023 QIP 2024

Students Travel Awards Commitee: Program Committees: QIP 2022

## Preprints

- Quantum Pseudorandom Scramblers [arxiv]

Chuhan Lu, Minglong Qin, Fang Song, Penghui Yao, Mingnan Zhao The Generations of Classical Correlations via Quantum Schemes [arxiv]

Zhenyu Chen, Lijinzhi Lin, Xiaodie Lin, Zhaohui Wei, Penghui YaoQuantum Insertion-Deletion Channels Covers [arxiv]

Janet Leahy, Dave Touchette, Penghui YaoRaz-McKenzie simulation with the inner product gadget [ECCC]

Xiaodi Wu, Penghui Yao, Henry Yuen

## Publications

On the Fine-Grained Query Complexity of Symmetric Functions [arxiv]

Supartha Podder, Penghui Yao, Zekun Ye**ISAAC 2023**On Testing and Learning Quantum Junta Channels [arxiv]

Zongbo Bao, Penghui Yao**COLT 2023**Decidability of fully quantum nonlocal games with noisy maximally entangled states [arxiv]

Minglong Qin, Penghui Yao**QIP 2023, ICALP 2023**Quantum Complexity of Weighted Diameter and Radius in CONGEST Networks [arxiv]

Xudong Wu, Penghui Yao**PODC 2022**Polynomial-Time Approximation of Zero-Free Partition Functions [arxiv]

Penghui Yao, Yitong Yin, Xinyuan Zhang**ICALP 2022**On the Gaussian surface area of spectrahedra [arxiv]

Srinivasan Arunachalam, Oded Regev, Penghui Yao**To appear GAFA Seminar Notes**Nonlocal games with noisy maximally entangled states are decidable [arxiv], supercedes [arxiv]

Minglong Qin, Penghui Yao

**SIAM Journal of Computing 2021**Complexity of Eccentricities and All-Pairs Shortest Paths in the Quantum CONGEST Model [arxiv]

Changsheng Wang, Xudong Wu, Penghui Yao

**SPIN 2021**Quantum and Classical Hybrid Generations for Classical Correlations [arxiv]

Xiaodie Lin, Zhaohui Wei, Penghui Yao

**IEEE Transactions on Information Theory, 2022**Quantum verification of NP problems with single photons and linear optics [arxiv]

(by contribution) Aonan Zhang, Hao Zhan, Junjie Liao, Kaimin Zheng, Tao Jiang, Minghao Mi, Penghui Yao, Lijian Zhang

**Light: Science & Applications 2020**Positive spectrahedrons: Geometric properties, Invariance principles and Pseudorandom generators [arxiv]

Srinivasan Arunachalam, Penghui Yao

**STOC 2022**On the Compression of messages in the Multi-Party setting [arxiv]

Anurag Anshu, Penghui Yao

**IEEE Transactions on Information Theory 2020**A doubly exponential upper bound on noisy EPR states for binary games [arxiv](it is superceded by [arxiv])

Penghui Yao

**QIP 2020**Expected communication cost of distributed quantum tasks [arxiv]

Anurag Anshu, Ankit Garg, Aram Harrow, Penghui Yao.

**IEEE Transactions on Information Theory 2018**Capacity approaching coding for low noise interactive quantum communication [arxiv]

Debbie Leung, Ashwin Nayak, Ala Shayeghi, Dave Touchette, Penghui Yao, Nengkun Yu

**IEEE Transactions on Information Theory 2021. Extended abstract appeared in STOC 2018**Exponential separation of quantum communication and classical information [arxiv]

Anurag Anshu, Dave Touchette, Penghui Yao, Nengkun Yu

**STOC 2017, plenary talk QIP 2017**Multipartite quantum correlation and communication complexities [arxiv]

Rahul Jain, Zhaohui Wei, Penghui Yao, Shengyu Zhang

**Computational Complexity 2016**New one shot quantum protocols with application to communication complexity [arxiv]

Anurag Anshu, Rahul Jain, Priyanka Mukhopadhyay, Ala Shayeghi, Penghui Yao

**IEEE Transactions on Information Theory 2016**Parity Decision Tree Complexity and 4-Party Communication Complexity of XOR-functions Are Polynomially Equivalent [arxiv]

Penghui Yao

**Chicago Journal of Theoretical Computer Science 2016**Lower bound on expected communication cost of quantum Huffman coding [arxiv]

Anurag Anshu, Ankit Garg, Aram Harrow, Penghui Yao

**TQC 2016**A parallel repetition theorem for entangled two-player one-round games under product distributions [arxiv]

Rahul Jain, Attila Pereszlényi, Penghui Yao.

**CCC 2014**A direct product theorem for two-party bounded-round public-coin commuinication complexity [arxiv]

Rahul Jain, Attila Pereszlényi, Penghui Yao

**FOCS 2012, special issue in Algorithmica**A parallel approximation algorithm for positive semidefinite programming [arxiv]

Rahul Jain, Penghui Yao

**FOCS 2011**Adversary Lower Bounds for Nonadaptive Quantum Algorithms [arxiv]

Pascal Koiran, Jürgen Landes, Natacha Portier, Penghui Yao

**WoLLIC 2008, special issue in Journal of Computer and System Sciences**

## Resources

A collection of references that I think may be useful for the students and researchers who are interested in the theory aspect of quantum information and quantum computation.The Theory of Quantum Information by John Watrous.

Lecture Notes on Quantum Algorithms by Andrew Childs.

Quantum Computing: Lecture Notes by Ronald de Wolf.

Quantum Computation and Quantum Information by Michael Nielsen and Isaac Chuang.