Given a random permutation f : [ N ] [ N ] as a black box and y [ N ] , we want to output x = f − 1 ( y ) . Supplementary to our input, we are given classical advice in the form of a pre-computed data structure; this advice can depend on the permutation but \emph{not} on the input y . Classically, there is a data structure of size O ( S ) and an algorithm that with the help of the data structure, given f ( x ) , can invert f in time O ( T ) , for every choice of parameters S , T , such that S T N . We prove a quantum lower bound of T 2 S ( N ) for quantum algorithms that invert a random permutation f on an fraction of inputs, where T is the number of queries to f and S is the amount of advice. This answers an open question of De et al.

We also give a ( N m ) quantum lower bound for the simpler but related Yao's box problem, which is the problem of recovering a bit x j , given the ability to query an N -bit string x at any index except the j -th, and also given m bits of advice that depend on x but not on j .