2 papers
quant-ph2023
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…
quant-ph2023
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…