A Theoretical Quantum Computer Scientist
"We are trying to prove ourselves wrong as quickly as possible, because only in that way we can find progress"
- Richard Feynman
Nai-Hui Chia (賈乃輝)
I am a Hartree Postdoctoral Fellow in the Joint Center for Quantum Information and Computer Science (QuICS) at the University of Maryland and a Visiting Scientist in the Luddy School of Informatics, Computing, and Engineering at Indiana University Bloomington. My research interests include quantum algorithms, complexity, and quantum cryptography. I am mainly interested in exploring the limits and capabilities of quantum computation. Most of my research is focusing on dealing with the following three questions: first, what quantum resources suffice to implement quantum algorithms with critical applications? Second, which problems can have quantum speedups, and what are the limits? Finally, how do quantum computers craft the landscapes of computer science?
I was a Postdoctoral Fellow at UT Austin from 2018 to 2020, working under the supervision of Dr. Scott Aaronson. I received my Ph.D. in Computer Science and Engineering at Penn State University, where I was fortunate to have Dr. Sean Hallgren as my advisor.
News!
[09/01/2020] I join the Joint Center for Quantum Information and Computer Science (QuICS) at the University of Maryland as a Hartree Postdoctoral Fellow.
[08/14/2020] I will join the Luddy School of Informatics, Computing, and Engineering and the Quantum Science and Engineering Center (QSEc) at the Indiana University Bloomington as an Assistant Professor in Fall 2021.
Personal
Email: naichia at iu dot edu/ nchia at umd dot edu
I am from Kaohsiung, Taiwan
Publications
Classical Verification of Quantum Computations with Efficient Verifier
Nai-Hui Chia, Kai-Min Chung, Takashi Yamakawa
In Proceedings of the 18th Theory of Cryptography Conference (TCC'2020)
[arXiv] [Conference]
On the quantum complexity of closest pair and related problems
Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang, Ruizhe Zhang
Contributed talk at the 15th Conference on the Theory of Quantum Computation, Communication, and Cryptography (TQC'2020)
In Proceedings of the 35th Computational Complexity Conference (CCC'2020)
[arXiv] [Conference]
On the need for large quantum depth
Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
Nai-Hui Chia, Andras Gilyen, Tonyang Li, Han-Hsuan Lin, Ewin Tang, Chunhao Wang
Contributed talk at the 23rd Annual Conference on Quantum Information Processing (QIP'2020)
In Proceedings of the 52nd ACM Symposium on Theory of Computing (STOC'2020)
[arXiv] [Conference]
Quantum-inspired classical sublinear-time algorithm for solving low-rank semidefinite programming via sampling approaches
Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin, and Chunhao Wang
In Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS'2020)
[arXiv] [Conference]
Quantum-inspired algorithms for solving low-rank linear equation systems with logarithmic dependence on the dimension
Nai-Hui Chia, András Gilyén, Han-Hsuan Lin, Seth Lloyd, Ewin Tang, and Chunhao Wang
In Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC’2020)
Merge of arXiv:1811.04852 (by Nai-Hui Chia, Han-Hsuan Lin, and Chunhao Wang) and arXiv:1811.04909 (by András Gilyén, Seth Lloyd, and Ewin Tang)
On Basing One-way Permutations on NP-hard Problems under Quantum Reductions
Nai-Hui Chia, Sean Hallgren, and Fang Song
Contributed talk at the 8th International Conference on Quantum Cryptography (QCRYPT'2018)
In Quantum, Volume 4, Number 312 (2020)
[Journal]
How Hard Is Deciding Trivial versus Nontrivial in the Dihedral Coset Problem?
Nai-Hui Chia and Sean Hallgren
In Proceedings of the 11th Conference on the Theory of Quantum Computation, Communication, and Cryptography (TQC'2016).
[arXiv]
Quantum Blind Computation with Teleportation-based Computation
Nai-Hui Chia, Chia-Hung Chien, Wei-Ho Chung, Sy-Yen Kuo
In Proceedings of the Ninth International Conference on Information Technology: New Generations (ITNG'2012)
On bundle configuration for viral marketing in social networks
De-Nian Yang, Wang-Chien Lee, Nai-Hui Chia, Mao Ye, Hui-Ju Hung
In Proceedings of the 21st ACM international conference on Information and knowledge management (CIKM'2012)
Manuscripts
On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Rounds
Nai-Hui Chia, Kai-Min Chung, Qipeng Liu, Takashi Yamakawa
In submission
[arXiv]
Quantum Meets the Minimum Circuit Size Problem
Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, Ruizhe Zhang
In submission
Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Round
Nai-Hui Chia, Kai-Min Chung, Takashi Yamakawa
In submission
[arXiv]
Quantum-inspired sublinear classical algorithms for solving low-rank linear systems
Nai-Hui Chia, Han-Hsuan Lin, and Chunhao Wang
[arXiv]
Invited and Contributed Talks
On the Need for Large Quantum Depth
Invited talk in QuICS Stakeholder Day, March 2021 (Online)
Invited talk in NCTS Annual Theory Meeting 2021: Quantum Physics, Quantum Information, and Quantum Technologies, Feb. 2021 (Online)
Contributed talk in STOC'2020, June 2020 (Online)
Contributed talk in QIP'2020, January 2020
Quantum Meets MCSP
Invited talk in Academia Sinica, Dec. 2020 (Online)
Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Round
Invited talk in Department of Computer Science, UMD, Dec. 2020 (Online)
Classical Verification of Quantum Computations with Efficient Verifier
Contributed talk in TCC'2020, November 2020 (Online)
Quantum-Inspired Sublinear Algorithms for Solving Low-Rank Semidefinte Programming
Contributed talk in MFCS'2020, August 2020 (Online, Short)
The capabilities and limits of quantum algorithms
Invited talk in Department of Computer Science and Engineering, UCSD, March 2020 (Online)
Invited talk in Department of Computer Science, UIUC, Feb. 2020
Invited talk in Department of Computer Science, Indiana University, Jan. 2020
Invited talk in Academia Sinica, Dec. 2019
Invited talk in Department of Computer Science and Information Engineering, National Central University, Taiwan, Dec. 2019
Invited talk in Department of Physics, National Taiwan University, Dec. 2019
Invited talk in Department of Computer Science and Information Engineering, National Taiwan University, Dec. 2019
Quantum-inspired sublinear algorithms for solving low-rank linear systems
Invited talk in Department of Computer Science, Texas A&M, Jan. 2019
Invited talk in National Chiao Tung University, Taiwan, Jan. 2019
Invited talk in Academia Sinica, Dec. 2018
Basing one-way permutations on NP-hard problems under quantum reductions
Contributed talk in QCRYPT'2018, Shanghai, August 2018
Quantum worst-case to average-case reductions for QMA-complete
Invited talk in Academia Sinica, December 2016
Introduction to quantum computing
Invited talk in Yahoo Taiwan, June 2016
How hard is deciding trivial versus nontrivial in the dihedral coset problem?
Contributed talk in TQC'2016, Berlin, September 2016
Invited talk in IQC, University of Waterloo, Nov. 2015
Invited talk in Academia Sinica, December 2015
Quantum computers - a view from computer science
Invited talk in Innovation and Interdisciplinary Collaboration Community Workshop, The Pennsylvania State University, November 2013
Invited talk in Kaohsiung High School, July 2013
Quantum Blind Computation with Teleportation-based Computation
Contributed talk in ITNG'2012, Las Vegas, 2012
Teaching Experience
Guest Lecturer for CS378: Introduction to Quantum Information Science by Scott Aaronson
Department of Computer Science, the University of Texas at Austin, Fall 2018
Teaching assistant for CMPSC464: Introduction to Theory of Computation
Department of CSE, Pennsylvania State University, Fall 2016/Spring 2018
Teaching assistant for CMPEN 331: Computer Organization and Design
Department of CSE, Pennsylvania State University, Fall 2012
Education
Ph.D. (2012 - 2018): Pennsylvania State University, CSE
Advisor: Sean Hallgren
Bachelor (2006 - 2010): National Taiwan University, CSIE