Quantum lower bound for inverting a permutation with advice

Aran Nayebi, Scott Aaronson, Aleksandrs Belovs +1

Given a random permutation $f:[N]\to [N]$ as a black box and $y\in [N]$, we want to output $x=f^{-1}(y)$. Supplementary to our input, we are given classical advice in the form…