3-Local Hamiltonian Problem and Constant Relative Error Quantum Partition Function Approximation: O(2^{n/2})-time Algorithm Is Nearly Optimal under QSETH
Nai-Hui Chia, Yu-Ching Shen
[arXiv]
In submission
Efficient Closest Matrix Product State Learning in Logarithmic Depth
Chia-Ying Lin, Nai-Hui Chia, Shih-Han Hung
[arXiv]
In submission
Complexity Theory for Quantum Promise Problems
Nai-Hui Chia, Kai-Min Chung, Tzu-Hsiang Huang, Jhih-Wei Shih
[arXiv]
In submission
The Black-Box Simulation Barrier Persists in a Fully Quantum World
Nai-Hui Chia, Kai-Min Chung, Xiao Liang, Jiahui Liu
[arXiv]
In submission
A Catalyst Framework for the Quantum Linear System Problem via the Proximal Point Algorithm
Junhyung Lyle Kim, Nai-Hui Chia, Anastasios Kyrillidis
[arXiv]
In submission
Oracle Separation between Noisy Quantum Polynomial Time and the Polynomial Hierarchy
Nai-Hui Chia, Min-Hsiu Hsieh, Shih-Han Hung, En-Jui Kuo
[arXiv]
In submission
Non-Interactive Classical Verification of Quantum Depth: A Fine-Grained Characterization
Nai-Hui Chia and Shih-Han Hung
In submission
Quantum-inspired sublinear classical algorithms for solving low-rank linear systems
Nai-Hui Chia, Han-Hsuan Lin, and Chunhao Wang
[arXiv]
A Cryptographic Perspective on the Verifiability of Quantum Advantage
Nai-Hui Chia, Honghao Fu, Fang Song, Penghui Yao
[arXiv]
Contributed talk at AQIS2024
To appear in ACM Transaction on Quantum Computing (ACM TQC)
Efficient learning of t-doped stabilizer states with single-copy measurements
Nai-Hui Chia, Ching-Yi Lai, Han-Hsuan Lin
Quantum, Volume 8, Page 1250 (2024)
[Link]
On the need for large quantum depth
Nai-Hui Chia, Kai-Min Chung, Ching-Yi Lai
Journal of ACM (JACM), Volume 70, Issue 1, February 2023, Article No.: 6, pp 1–38
[Link]
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
Journal of ACM (JACM), Volume 69, Issue 5, October 2022 Article No.: 33, pp 1–72
[Link]
On Basing One-way Permutations on NP-hard Problems under Quantum Reductions
Nai-Hui Chia, Sean Hallgren, and Fang Song
Quantum, Volume 4, Number 312 (2020)
Contributed talk at the 8th International Conference on Quantum Cryptography (QCRYPT 2018)
[Link]
Adversarially Robust Quantum State Learning
Maryam Aliakbarpour, Vladimir Braverman, Nai-Hui Chia, Yuhan Liu
In FOCS 2025
Quantum State Learning Implies Circuit Lower Bounds
On the Impossibility of General Parallel Fast-forwarding of Hamiltonian Simulation
Nai-Hui Chia, Kai-Min Chung, Yao-Ching Hsieh, Han-Hsuan Lin, Yao-Ting Lin, Yu-Ching Shen
In Proceedings of the 38th Computational Complexity Conference (CCC 2023)
[arXiv]
Post-Quantum Simulatable Extraction with Minimal Assumptions: Black-Box and Constant-Round
Nai-Hui Chia, Kai-Min Chung, Xiao Liang, Takashi Yamakawa
In Proceedings of the 42nd Annual International Cryptology Conference (Crypto 2022)
[arXiv]
Classical Verification of Quantum Depth
Nai-Hui Chia and Shih-Han Hung
Contributed talk at the 17th Conference on the Theory of Quantum Computation, Communication, and Cryptography (TQC 2022)
Contributed talk at the 12th International Conference on Quantum Cryptography (QCrypt 2022)
In submission
[arXiv]
Quantum Meets the Minimum Circuit Size Problem
Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, Ruizhe Zhang
In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
[arXiv]
On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Rounds
Nai-Hui Chia, Kai-Min Chung, Qipeng Liu, Takashi Yamakawa
In Proceedings of the 62nd Annual Symposium on Foundations of Computer Science (FOCS 2021)
Contributed talk at the 25th Annual Conference on Quantum Information Processing (QIP 2022)
Merged with Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Round
Contributed talk at the 11th International Conference on Quantum Cryptography (QCrypt 2021)
Merged with Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Round
[arXiv]
Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Round
Nai-Hui Chia, Kai-Min Chung, Takashi Yamakawa
In Proceedings of the 41st Annual International Cryptology Conference (Crypto 2021)
Contributed talk at the 25th Annual Conference on Quantum Information Processing (QIP 2022)
Merged with On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Rounds
Contributed talk at the 11th International Conference on Quantum Cryptography (QCrypt 2021)
Merged with On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Rounds
[arXiv]
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
In Proceedings of the 35th Computational Complexity Conference (CCC 2020)
Contributed talk at the 15th Conference on the Theory of Quantum Computation, Communication, and Cryptography (TQC 2020)
[arXiv] [Conference]
On the need for large quantum depth
Nai-Hui Chia, Kai-Min Chung, Ching-Yi Lai
In Proceedings of the 52nd ACM Symposium on Theory of Computing (STOC 2020)
Contributed talk at the 23rd Annual Conference on Quantum Information Processing (QIP 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
In Proceedings of the 52nd ACM Symposium on Theory of Computing (STOC 2020)
Contributed talk at the 23rd Annual Conference on Quantum Information Processing (QIP 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 and arXiv:1811.04909
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)
Organizer of quantum computing sessions in IOS 2024
On the Panel of NSF and DOE
Program committee of 19th Theory of Quantum Computation, Communication and Cryptography (TQC 2024)
Organizer of QuantIPS 2023
Program committee of ACM/IEEE Workshop on Quantum Computing (Quantum 22)
Program committee of the 25th Annual Conference on Quantum Information Processing (QIP 2022)
Co-organizer of online quantum computing seminar