Nai-Hui Chia

55 papers A* 6A 5B 2Journal 37Unranked 5
YearRankTypeTitle / Venue / Authors
2026 A* conf
A Catalyst Framework for the Quantum Linear System Problem via the Proximal Point Algorithm.
AAAI
Junhyung Lyle Kim, Nai-Hui Chia, Anastasios Kyrillidis
2026 J jnl
A Cryptographic Perspective on the Verifiability of Quantum Advantage.
ACM Trans. Quantum Comput.
Nai-Hui Chia, Honghao Fu, Fang Song, Penghui Yao
2026 J jnl
Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions.
CoRR
Nai-Hui Chia, Atsuya Hasegawa, François Le Gall, Yu-Ching Shen
2025 J jnl
3-Local Hamiltonian Problem and Constant Relative Error Quantum Partition Function Approximation: O(2
CoRR
Nai-Hui Chia, Yu-Ching Shen
2025 A* conf
Adversarially Robust Quantum State Learning and Testing.
FOCS
Maryam Aliakbarpour, Vladimir Braverman, Nai-Hui Chia, Yuhan Liu
2025 J jnl
Adversarially robust quantum state learning and testing.
CoRR
Maryam Aliakbarpour, Vladimir Braverman, Nai-Hui Chia, Yuhan Liu
2025 J jnl
Efficient Closest Matrix Product State Learning in Logarithmic Depth.
CoRR
Chia-Ying Lin, Nai-Hui Chia, Shih-Han Hung
2025 A* conf
Quantum State and Unitary Learning Implies Circuit Lower Bounds.
COLT
Nai-Hui Chia, Daniel Liang, Fang Song
2025 J jnl
Shadow Tomography Against Adversaries.
CoRR
Maryam Aliakbarpour, Vladimir Braverman, Nai-Hui Chia, Chia-Ying Lin, Yuhan Liu, Aadil Oufkir, Yu-Ching Shen
2024 J jnl
A Catalyst Framework for the Quantum Linear System Problem via the Proximal Point Algorithm.
CoRR
Junhyung Lyle Kim, Nai-Hui Chia, Anastasios Kyrillidis
2024 J jnl
Complexity Theory for Quantum Promise Problems.
CoRR
Nai-Hui Chia, Kai-Min Chung, Tzu-Hsiang Huang, Jhih-Wei Shih
2024 J jnl
Efficient learning of t-doped stabilizer states with single-copy measurements.
Quantum
Nai-Hui Chia, Ching-Yi Lai, Han-Hsuan Lin
2024 J jnl
Oracle Separation between Noisy Quantum Polynomial Time and the Polynomial Hierarchy.
CoRR
Nai-Hui Chia, Min-Hsiu Hsieh, Shih-Han Hung, En-Jui Kuo
2024 J jnl
The Black-Box Simulation Barrier Persists in a Fully Quantum World.
CoRR
Nai-Hui Chia, Kai-Min Chung, Xiao Liang, Jiahui Liu
2024 J jnl
The Black-Box Simulation Barrier Persists in a Fully Quantum World.
IACR Cryptol. ePrint Arch.
Nai-Hui Chia, Kai-Min Chung, Xiao Liang, Jiahui Liu
2023 J jnl
A Cryptographic Perspective on the Verifiability of Quantum Advantage.
CoRR
Nai-Hui Chia, Honghao Fu, Fang Song, Penghui Yao
2023 J jnl
Non-Interactive Classical Verification of Quantum Depth: A Fine-Grained Characterization.
IACR Cryptol. ePrint Arch.
Nai-Hui Chia, Shih-Han Hung
2023 A conf
On the Impossibility of General Parallel Fast-Forwarding of Hamiltonian Simulation.
CCC
Nai-Hui Chia, Kai-Min Chung, Yao-Ching Hsieh, Han-Hsuan Lin, Yao-Ting Lin, Yu-Ching Shen
2023 J jnl
On the Impossibility of General Parallel Fast-forwarding of Hamiltonian Simulation.
CoRR
Nai-Hui Chia, Kai-Min Chung, Yao-Ching Hsieh, Han-Hsuan Lin, Yao-Ting Lin, Yu-Ching Shen
2023 J jnl
On the Need for Large Quantum Depth.
J. ACM
Nai-Hui Chia, Kai-Min Chung, Ching-Yi Lai
2022 J jnl
Classical verification of quantum depth.
CoRR
Nai-Hui Chia, Shih-Han Hung
2022 — conf
Post-quantum Simulatable Extraction with Minimal Assumptions: Black-Box and Constant-Round.
CRYPTO (3)
Nai-Hui Chia, Kai-Min Chung, Xiao Liang, Takashi Yamakawa
2022 A conf
QMLP: An Error-Tolerant Nonlinear Quantum MLP Architecture using Parameterized Two-Qubit Gates.
ISLPED
Cheng Chu, Nai-Hui Chia, Lei Jiang, Fan Chen
2022 J jnl
QMLP: An Error-Tolerant Nonlinear Quantum MLP Architecture using Parameterized Two-Qubit Gates.
CoRR
Cheng Chu, Nai-Hui Chia, Lei Jiang, Fan Chen
2022 A conf
Quantum Meets the Minimum Circuit Size Problem.
ITCS
Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, Ruizhe Zhang
2022 J jnl
Sampling-based Sublinear Low-rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning.
J. ACM
Nai-Hui Chia, András Pal Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, Chunhao Wang
2021 — conf
A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds.
CRYPTO (1)
Nai-Hui Chia, Kai-Min Chung, Takashi Yamakawa
2021 A* conf
On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Round.
FOCS
Nai-Hui Chia, Kai-Min Chung, Qipeng Liu, Takashi Yamakawa
2021 J jnl
On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Rounds.
CoRR
Nai-Hui Chia, Kai-Min Chung, Qipeng Liu, Takashi Yamakawa
2021 J jnl
On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Rounds.
IACR Cryptol. ePrint Arch.
Nai-Hui Chia, Kai-Min Chung, Qipeng Liu, Takashi Yamakawa
2021 J jnl
Post-Quantum Simulatable Extraction with Minimal Assumptions: Black-Box and Constant-Round.
CoRR
Nai-Hui Chia, Kai-Min Chung, Xiao Liang, Takashi Yamakawa
2021 J jnl
Post-Quantum Simulatable Extraction with Minimal Assumptions: Black-Box and Constant-Round.
IACR Cryptol. ePrint Arch.
Nai-Hui Chia, Kai-Min Chung, Xiao Liang, Takashi Yamakawa
2021 J jnl
Quantum Meets the Minimum Circuit Size Problem.
CoRR
Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, Ruizhe Zhang
2021 J jnl
Quantum Meets the Minimum Circuit Size Problem.
Electron. Colloquium Comput. Complex.
Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, Ruizhe Zhang
2020 J jnl
A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Round.
CoRR
Nai-Hui Chia, Kai-Min Chung, Takashi Yamakawa
2020 J jnl
A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds.
IACR Cryptol. ePrint Arch.
Nai-Hui Chia, Kai-Min Chung, Takashi Yamakawa
2020 — conf
Classical Verification of Quantum Computations with Efficient Verifier.
TCC (3)
Nai-Hui Chia, Kai-Min Chung, Takashi Yamakawa
2020 J jnl
Classical Verification of Quantum Computations with Efficient Verifier.
IACR Cryptol. ePrint Arch.
Nai-Hui Chia, Kai-Min Chung, Takashi Yamakawa
2020 J jnl
On Basing One-way Permutations on NP-hard Problems under Quantum Reductions.
Quantum
Nai-Hui Chia, Sean Hallgren, Fang Song
2020 A conf
On the Quantum Complexity of Closest Pair and Related Problems.
CCC
Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang, Ruizhe Zhang
2020 A* conf
On the need for large quantum depth.
STOC
Nai-Hui Chia, Kai-Min Chung, Ching-Yi Lai
2020 B conf
Quantum-Inspired Algorithms for Solving Low-Rank Linear Equation Systems with Logarithmic Dependence on the Dimension.
ISAAC
Nai-Hui Chia, András Gilyén, Han-Hsuan Lin, Seth Lloyd, Ewin Tang, Chunhao Wang
2020 B conf
Quantum-Inspired Sublinear Algorithm for Solving Low-Rank Semidefinite Programming.
MFCS
Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin, Chunhao Wang
2020 A* conf
Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning.
STOC
Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, Chunhao Wang
2019 J jnl
Classical Verification of Quantum Computations with Efficient Verifier.
CoRR
Nai-Hui Chia, Kai-Min Chung, Takashi Yamakawa
2019 J jnl
On the Need for Large Quantum Depth.
CoRR
Nai-Hui Chia, Kai-Min Chung, Ching-Yi Lai
2019 J jnl
On the Quantum Complexity of Closest Pair and Related Problems.
CoRR
Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang, Ruizhe Zhang
2019 J jnl
Quantum-inspired classical sublinear-time algorithm for solving low-rank semidefinite programming via sampling approaches.
CoRR
Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin, Chunhao Wang
2019 J jnl
Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning.
CoRR
Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, Chunhao Wang
2018 J jnl
On Basing One-way Permutations on NP-hard Problems under Quantum Reductions.
CoRR
Nai-Hui Chia, Sean Hallgren, Fang Song
2018 J jnl
Quantum-inspired sublinear classical algorithms for solving low-rank linear systems.
CoRR
Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang
2016 — conf
How Hard Is Deciding Trivial Versus Nontrivial in the Dihedral Coset Problem?.
TQC
Nai-Hui Chia, Sean Hallgren
2016 J jnl
How hard is deciding trivial versus nontrivial in the dihedral coset problem?
CoRR
Nai-Hui Chia, Sean Hallgren
2012 A conf
On bundle configuration for viral marketing in social networks.
CIKM
De-Nian Yang, Wang-Chien Lee, Nai-Hui Chia, Mao Ye, Hui-Ju Hung
2012 — conf
Quantum Blind Computation with Teleportation-based Computation.
ITNG
Nai-Hui Chia, Chia-Hung Chien, Wei-Ho Chung, Sy-Yen Kuo