Name：Zhengfeng Ji

Position：Professor

Email：jizhengfeng@tsinghua.edu.cn

Education

B. Eng., Department of Computer Science and Technology, Tsinghua University, 2002

Ph.D. Department of Computer Science and Technology, Tsinghua University, 2002

Services

ACM Transactions on Quantum Computing: Associate Editor (2022-).

Research Area

Quantum Computing, Theory of Computing

Research Highlights

1. Quantum Complexity Theory.

Quantum interactive proofs form a central area in the theory of quantum algorithm complexity, with important connections to other branches of complexity theory and cryptography. Our research provides a complete characterization of two important complexity classes in this field, QIP and MIP*. Some of the related results have had interdisciplinary impact, addressing important open problems in theoretical physics and pure mathematics.

2. Quantum Cryptography.

Quantum computing is deeply connected to cryptography. In our work on quantum cryptography, we introduce the concept of pseudo-randomness to quantum state space, define the notion of pseudorandom quantum states, and establish their fundamental properties and applications. These results have not only influenced the field of quantum cryptography but have also recently been applied in research on quantum gravity and black holes. We construct quantum zero-knowledge proofs for languages in QMA, the quantum counterpart of NP, and investigate the quantum aspects of zero-knowledge proofs. Additionally, we propose a post-quantum cryptographic assumption based on tensor equivalence and design post-quantum secure digital signature protocols based on this assumption.

3. Quantum Information.

Quantum information theory and quantum entanglement theory form the foundational language of quantum computing. In collaboration with colleagues, we have solved several fundamental problems in quantum information theory and quantum entanglement theory. This includes introducing programmability to quantum channel parameter estimation problems, addressing the sample complexity of quantum state tomography, and answering the LU-LC problem for stabilizer states in the negative.

4. Quantum Software.

Quantum software is a core technology that is equally important as the development of quantum hardware. In collaboration with colleagues, we have proposed and developed the theory of bi-simulation for quantum communication concurrent systems (CCS), the theory of weakest preconditions for quantum programs, and the symbolic representation method for quantum circuits.

Publications

1. Michael J. Bremner, Zhengfeng Ji, Ryan L. Mann, Luke Mathieson, Mauro E. S. Morales, Alexis T. E. Shaw. Quantum Parameterized Complexity. arXiv:2203.08002, 2022.

2. Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. Quantum soundness of testing tensor codes. In Proceedings of the 62nd IEEE Symposium on Foundations of Computer Science (FOCS), pages 586-597, Denver, CO, USA, 2022.

3. Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. MIP*=RE. arXiv:2001.04383 [quant-ph], September 2020.

4. Joseph Fitzsimons, Zhengfeng Ji, Thomas Vidick, and Henry Yuen. Quantum proof systems for iterated exponential time, and beyond. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 473-480, New York, NY, USA, June 2019.

5. Anne Broadbent, Zhengfeng Ji, Fang Song, and John Watrous. Zero Knowledge Proof Systems for QMA. SIAM Journal on Computing, 49(2):245-283, January 2020.

6. Mingsheng Ying, Zhengfeng Ji. Symbolic Verification of Quantum Circuits. arXiv:2010.03032, 2020.

7. Zhengfeng Ji, Yi-Kai Liu, and Fang Song. Pseudorandom Quantum States. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology - CRYPTO 2018, Lecture Notes in Computer Science, pages 126-152, 2018.

8. Zhengfeng Ji. Compression of quantum multi-prover interactive proofs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 289-302, New York, NY, USA, June 2017.

9. Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. Sample-optimal tomography of quantum states. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, STOC '16, pages 913-925, New York, NY, USA, June 2016.

10. Zhengfeng Ji, Youming Qiao, Fang Song, and Aaram Yun. General Linear Group Action on Tensors: A Candidate for Post-quantum Cryptography. In Dennis Hofheinz and Alon Rosen, editors, Theory of Cryptography, Lecture Notes in Computer Science, pages 251-281, 2019.

11. Zhengfeng Ji. Classical verification of quantum proofs. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, STOC '16, pages 885-898, New York, NY, USA, June 2016.

12. Lin Chen, Eric Chitambar, Runyao Duan, Zhengfeng Ji, and Andreas Winter. Tensor Rank and Stochastic Entanglement Catalysis for Multipartite Pure States. Physical Review Letters, 105(20):200501, November 2010.

13. Zhengfeng Ji, Zhihan Jin, and Pinyan Lu. Approximating Permanent of Random Matrices with Vanishing Mean: Made Better and Simpler. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), Proceedings, pages 959-975.

14. Zhengfeng Ji, Guoming Wang, Runyao Duan, Yuan Feng, and Mingsheng Ying. Parameter Estimation of Quantum Channels. IEEE Transactions on Information Theory, 54(11):5172-5185, November 2008.

15. Zhengfeng Ji, Jianxin Chen, Zhaohui Wei, and Mingsheng Ying. The LU-LC conjecture is false. Quantum Information & Computation, 10(1):97-108, January 2010.

16. Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous. QIP = PSPACE. Journal of the ACM, 58(6):30:1-30:27, December 2011.

17. Xie Chen, Runyao Duan, Zhengfeng Ji, and Bei Zeng. Quantum State Reduction for Universal Measurement Based Computation. Physical Review Letters, 105(2):020502, July 2010.

18. Samuel A. Ocko, Xie Chen, Bei Zeng, Beni Yoshida, Zhengfeng Ji, Mary Beth Ruskai, and Isaac L. Chuang. Quantum Codes Give Counterexamples to the Unique Preimage Conjecture of the N-Representability Problem. Physical Review Letters, 106(11):110501, March 2011.

19. Mingsheng Ying, Yuan Feng, Runyao Duan, and Zhengfeng Ji. An algebra of quantum processes. ACM Transactions on Computational Logic, 10(3):19:1-19:36, April 2009.

20. Zhengfeng Ji, Yuan Feng, Runyao Duan, and Mingsheng Ying. Identification and Distance Measures of Measurement Apparatus. Physical Review Letters, 96(20):200401, May 2006.