Tight Quantum Time-Space Tradeoffs for Function Inversion

Kai-Min Chung, Siyao Guo, Qipeng Liu +1

In function inversion, we are given a function $f:[N]\mapsto [N]$, and want to prepare some advice of size $S$, such that we can efficiently invert any image in time $T$. This is…