Publications (18)
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…
A sublinear time quantum algorithm for longest common substring problem between run-length encoded strings
Tzu-Ching Lee, Han-Hsuan Lin
We give a sublinear quantum algorithm for the longest common substring (LCS) problem on the run-length encoded (RLE) inputs, under the assumption that the prefix-sums of the runs a…
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…
Getting almost all the bits from a quantum random access code
Han-Hsuan Lin, Ronald de Wolf
A quantum random access code (QRAC) is a map that encodes -bit strings into -qubit quantum states , in a way that allows us to recover any one bit of…
Optimizing sparse quantum state preparation with measurement and feedforward
Yao-Cheng Lu, Han-Hsuan Lin
Quantum state preparation (QSP) is a key component in many quantum algorithms. In particular, the problem of sparse QSP (SQSP) $\unicode{x2013}$ the task of preparing the states wi…
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…
Permutation Symmetric Critical Phases in Disordered Non-Abelian Anyonic Chains
Lukasz Fidkowski, Gil Refael, Han-Hsuan Lin +1
Topological phases supporting non-abelian anyonic excitations have been proposed as candidates for topological quantum computation. In this paper, we study disordered non-abelian a…
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…
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…
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…
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…
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…
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…
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…
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…
Near-Optimal Quantum Algorithm for Finding the Longest Common Substring between Run-Length Encoded Strings
Tzu-Ching Lee, Han-Hsuan Lin
We give a near-optimal quantum algorithm for the longest common substring (LCS) problem between two run-length encoded (RLE) strings, with the assumption that the prefix-sums of th…
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…
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…