106 citations · 191 across the 9 of their papers we have counts for
15 papers
No Size-Preserving Amplification with Quantum Advice
Shih-Han Hung, Han-Hsuan Lin
Marriott and Watrous showed that quantum Merlin--Arthur games admit generic error reduction without increasing witness size [Computational Complexity, 2005]. In this work, we show…
Small-Bias Quantum Approximate Counting via the Multiplicative Adversary Method
Albert Lin, Han-Hsuan Lin
We study the two-weight decision version of quantum approximate counting: given oracle access to , distinguish from with success probability $1/2+ζ…
Efficient learning of -doped stabilizer states with single-copy measurements
Nai-Hui Chia, Ching-Yi Lai, Han-Hsuan Lin
One of the primary objectives in the field of quantum state learning is to develop algorithms that are time-efficient for learning states generated from quantum circuits. Earlier i…
On the Impossibility of General Parallel Fast-forwarding of Hamiltonian Simulation
Nai-Hui Chia, Kai-Min Chung, Yao-Ching Hsieh +3
Hamiltonian simulation is one of the most important problems in the field of quantum computing. There have been extended efforts on designing algorithms for faster simulation, and…
On relating one-way classical and quantum communication complexities
Naresh Goud Boddu, Rahul Jain, Han-Hsuan Lin
Communication complexity is the amount of communication needed to compute a function when the function inputs are distributed over multiple parties. In its simplest form, one-way c…
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…
Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
Nai-Hui Chia, András Gilyén, Tongyang Li +3
We present an algorithmic framework for quantum-inspired classical algorithms on close-to-low-rank matrices, generalizing the series of results started by Tang's breakthrough quant…
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…
Sample Efficient Algorithms for Learning Quantum Channels in PAC Model and the Approximate State Discrimination Problem
Kai-Min Chung, Han-Hsuan Lin
We generalize the PAC (probably approximately correct) learning model to the quantum world by generalizing the concepts from classical functions to quantum processes, defining the…
A Quantum-Proof Non-Malleable Extractor, With Application to Privacy Amplification against Active Quantum Adversaries
Divesh Aggarwal, Kai-Min Chung, Han-Hsuan Lin +1
In privacy amplification, two mutually trusted parties aim to amplify the secrecy of an initial shared secret in order to establish a shared private key by exchanging messa…
Oracles with Costs
Shelby Kimmel, Cedric Yen-Yu Lin, Han-Hsuan Lin
While powerful tools have been developed to analyze quantum query complexity, there are still many natural problems that do not fit neatly into the black box model of oracles. We c…
Upper bounds on quantum query complexity inspired by the Elitzur-Vaidman bomb tester
Cedric Yen-Yu Lin, Han-Hsuan Lin
Inspired by the Elitzur-Vaidman bomb testing problem [arXiv:hep-th/9305002], we introduce a new query complexity model, which we call bomb query complexity . We investigate i…
Different Strategies for Optimization Using the Quantum Adiabatic Algorithm
Elizabeth Crosson, Edward Farhi, Cedric Yen-Yu Lin +2
We present the results of a numerical study, with 20 qubits, of the performance of the Quantum Adiabatic Algorithm on randomly generated instances of MAX 2-SAT with a unique assign…