Tight Quantum Time-Space Tradeoffs for Permutation Inversion

Akshima, Tyler Besselman, Kai-Min Chung +2

In permutation inversion, we are given a permutation $\ddot{I}€:[N]\to [N]$, and want to prepare some advice of size $S$, such that we can efficiently invert any image in time $…