Quantum lower bound for inverting a permutation with advice

Given a random permutation f : [N] → [N] as a black box and y ∈ [N], we want to output x = f⁻¹(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 not on the input y. Classically, there is a data structure of size Õ(S) and an algorithm that with the help of the data structure, given f(x), can invert f in time Õ(T), for every choice of parameters S, T, such that S ・ T ≥ N. We prove a quantum lower bound of T² ・ 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 Ω(Foumula Presented) 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 classical advice that depend on x but not on j.