## 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**