4 papers
Constant-round Blind Classical Verification of Quantum Sampling
Kai-Min Chung, Yi Lee, Han-Hsuan Lin +1
In a recent breakthrough, Mahadev constructed a classical verification of quantum computation (CVQC) protocol for a classical client to delegate decision problems in BQP to an untr…
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…
Quantum-inspired sublinear classical algorithms for solving low-rank linear systems
Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang
We present classical sublinear-time algorithms for solving low-rank linear systems of equations. Our algorithms are inspired by the HHL quantum algorithm for solving linear systems…