Lower Bounds for Function Inversion with Quantum Advice

Kai-Min Chung, Tai-Ning Liao, Luowen Qian

Function inversion is the problem that given a random function $f:[M]\to [N]$, we want to find pre-image of any image $f^{-1}(y)$ in time $T$. In this work, we revisit this probl…