1 citations · 1 across the 5 of their papers we have counts for
4 papers · 1 filter
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…
LWE with Quantum Amplitudes: Algorithm, Hardness, and Oblivious Sampling
Yilei Chen, Zihan Hu, Qipeng Liu +2
In this paper, we show new algorithms, hardness results and applications for and with real Gaussian, Gaussian with linear or quadratic phase…
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…
Quantum Algorithms for Variants of Average-Case Lattice Problems via Filtering
Yilei Chen, Qipeng Liu, Mark Zhandry
We show polynomial-time quantum algorithms for the following problems: (*) Short integer solution (SIS) problem under the infinity norm, where the public matrix is very wide, the m…