5 papers · 1 filter
An Improved Quantum Algorithm for 3-Tuple Lattice Sieving
Lynn Engelberts, Yanlin Chen, Amin Shiraz Gilani +3
The assumed hardness of the Shortest Vector Problem in high-dimensional lattices is one of the cornerstones of post-quantum cryptography. The fastest known heuristic attacks on SVP…
QuantumBoost: A lazy, yet fast, quantum algorithm for learning with weak hypotheses
Amira Abbas, Yanlin Chen, Tuyen Nguyen +1
The technique of combining multiple votes to enhance the quality of a decision is the core of boosting algorithms in machine learning. In particular, boosting provably increases de…
Fine-Grained Complexity via Quantum Natural Proofs
Yanlin Chen, Yilei Chen, Rajendra Kumar +2
Buhrman, Patro, and Speelman presented a framework of conjectures that together form a quantum analogue of the strong exponential-time hypothesis and its variants. They called it t…
QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more
Yanlin Chen, Yilei Chen, Rajendra Kumar +2
While seemingly undesirable, it is not a surprising fact that there are certain problems for which quantum computers offer no computational advantage over their respective classica…
A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix
Yanlin Chen, András Gilyén, Ronald de Wolf
Finding a good approximation of the top eigenvector of a given matrix is a basic and important computational problem, with many applications. We give two different…