Nai-Hui Chia

According to our database, Nai-Hui Chia authored at least 24 papers between 2012 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of four.

2024

Efficient learning of t-doped stabilizer states with single-copy measurements.

Nai-Hui Chia, Ching-Yi Lai, Han-Hsuan Lin

Quantum, February, 2024

2023

On the Need for Large Quantum Depth.

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

J. ACM, February, 2023

Non-Interactive Classical Verification of Quantum Depth: A Fine-Grained Characterization.

Nai-Hui Chia, Shih-Han Hung

IACR Cryptol. ePrint Arch., 2023

A Cryptographic Perspective on the Verifiability of Quantum Advantage.

Nai-Hui Chia, Honghao Fu, Fang Song, Penghui Yao

CoRR, 2023

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

Proceedings of the 38th Computational Complexity Conference, 2023

2022

Sampling-based Sublinear Low-rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning.

Nai-Hui Chia, András Pal Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, Chunhao Wang

J. ACM, 2022

Classical verification of quantum depth.

Nai-Hui Chia, Shih-Han Hung

CoRR, 2022

QMLP: An Error-Tolerant Nonlinear Quantum MLP Architecture using Parameterized Two-Qubit Gates.

Cheng Chu, Nai-Hui Chia, Lei Jiang, Fan Chen

Proceedings of the ISLPED '22: ACM/IEEE International Symposium on Low Power Electronics and Design, Boston, MA, USA, August 1, 2022

2021

Post-Quantum Simulatable Extraction with Minimal Assumptions: Black-Box and Constant-Round.

Nai-Hui Chia, Kai-Min Chung, Xiao Liang, Takashi Yamakawa

IACR Cryptol. ePrint Arch., 2021

On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Rounds.

Nai-Hui Chia, Kai-Min Chung, Qipeng Liu, Takashi Yamakawa

IACR Cryptol. ePrint Arch., 2021

Quantum Meets the Minimum Circuit Size Problem.

Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, Ruizhe Zhang

Electron. Colloquium Comput. Complex., 2021

On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Round.

Nai-Hui Chia, Kai-Min Chung, Qipeng Liu, Takashi Yamakawa

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

On Basing One-way Permutations on NP-hard Problems under Quantum Reductions.

Nai-Hui Chia, Sean Hallgren, Fang Song

Quantum, 2020

A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds.

Nai-Hui Chia, Kai-Min Chung, Takashi Yamakawa

IACR Cryptol. ePrint Arch., 2020

Classical Verification of Quantum Computations with Efficient Verifier.

Nai-Hui Chia, Kai-Min Chung, Takashi Yamakawa

IACR Cryptol. ePrint Arch., 2020

A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Round.

Nai-Hui Chia, Kai-Min Chung, Takashi Yamakawa

CoRR, 2020

Quantum-Inspired Sublinear Algorithm for Solving Low-Rank Semidefinite Programming.

Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin, Chunhao Wang

Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

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, Chunhao Wang

Proceedings of the 31st International Symposium on Algorithms and Computation, 2020

On the Quantum Complexity of Closest Pair and Related Problems.

Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang, Ruizhe Zhang

Proceedings of the 35th Computational Complexity Conference, 2020

2019

Quantum-inspired classical sublinear-time algorithm for solving low-rank semidefinite programming via sampling approaches.

Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin, Chunhao Wang

CoRR, 2019

2018

Quantum-inspired sublinear classical algorithms for solving low-rank linear systems.

Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang

CoRR, 2018

2016

How Hard Is Deciding Trivial Versus Nontrivial in the Dihedral Coset Problem?.

Nai-Hui Chia, Sean Hallgren

Proceedings of the 11th Conference on the Theory of Quantum Computation, 2016

2012

Quantum Blind Computation with Teleportation-based Computation.

Nai-Hui Chia, Chia-Hung Chien, Wei-Ho Chung, Sy-Yen Kuo

Proceedings of the Ninth International Conference on Information Technology: New Generations, 2012

On bundle configuration for viral marketing in social networks.

De-Nian Yang, Wang-Chien Lee, Nai-Hui Chia, Mao Ye, Hui-Ju Hung

Proceedings of the 21st ACM International Conference on Information and Knowledge Management, 2012