For Lipschitz time-dependent Hamiltonians, the new algorithm uses O(alpha T + log(1/epsilon)/log(e + log(1/epsilon)/(alpha T))) HAM-T queries, matching the lower bound for time-independent simulation.
Elfs, transducers and quantum walks
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
Electric flow sampling (elfs) is a new tool in the quantum walk toolbox and a useful primitive for solving search, sampling and optimization problems on graphs. We refine this tool by showing that there exists a zero-error transducer for implementing elfs. More broadly, we establish a zero-error transducer for reflecting about the intersection of two subspaces, yielding an errorfree transducer version of the effective gap lemma. Building on this result, we obtain improved quantum walk algorithms for estimating effective resistances and span program witness sizes with an optimal error scaling, and for sampling from the random walk arrival distribution, via the composition of many elfs. Using this last algorithm, we obtain an up-to-quadratic quantum speedup for semi-supervised learning on expander graphs.
fields
quant-ph 1years
2026 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
Time-Dependent Hamiltonian Simulation with Optimal Query Complexity
For Lipschitz time-dependent Hamiltonians, the new algorithm uses O(alpha T + log(1/epsilon)/log(e + log(1/epsilon)/(alpha T))) HAM-T queries, matching the lower bound for time-independent simulation.