Permutation Superposition Oracles for Quantum Query Lower Bounds

Zhandry’s compressed oracle technique has been extremely successful as a proof tool for analyzing quantum algorithms with (quantum) access to a random function. It has, however, turned out to be very difficult to generalize the technique to the case of random permutations. I will begin this talk by describing the compressed oracle technique on a high level, highlighting the properties of random functions it makes crucial use of. Then I will explain the difficulties that arise when trying to construct an analogue technique for permutations. Finally, I will describe how we tackle the challenges to get a first permutation superposition oracle that has a number of the nice properties which make the function version so useful.

Joint work with Giulio Malavolta and Michael Walter.