2 citations · 2 across the 1 of their papers we have counts for
8 papers
Classical verification of quantum depth
Nai-Hui Chia, Shih-Han Hung
We present two protocols for classical verification of quantum depth. Our protocols allow a purely classical verifier to distinguish devices with different quantum circuit depths e…
Quantum Meets the Minimum Circuit Size Problem
Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang +1
In this work, we initiate the study of the Minimum Circuit Size Problem (MCSP) in the quantum setting. MCSP is a problem to compute the circuit complexity of Boolean functions. It…
On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Rounds
Nai-Hui Chia, Kai-Min Chung, Qipeng Liu +1
We investigate the existence of constant-round post-quantum black-box zero-knowledge protocols for . As a main result, we show that there is no constant-round post-qua…
Classical Verification of Quantum Computations with Efficient Verifier
Nai-Hui Chia, Kai-Min Chung, Takashi Yamakawa
In this paper, we extend the protocol of classical verification of quantum computations (CVQC) recently proposed by Mahadev to make the verification efficient. Our result is obtain…
On the Quantum Complexity of Closest Pair and Related Problems
Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin +2
The closest pair problem is a fundamental problem of computational geometry: given a set of points in a -dimensional space, find a pair with the smallest distance. A classic…
Quantum-inspired sublinear algorithm for solving low-rank semidefinite programming
Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin +1
Semidefinite programming (SDP) is a central topic in mathematical optimization with extensive studies on its efficient solvers. In this paper, we present a proof-of-principle subli…