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!

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

    • Nai-Hui Chia, Kai-Min Chung, Ching-Yi Lai

    • 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]

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 (ISAAC2020)

    • 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)

    • [conference]

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