Random Garbage Separates XOR from Forward-Only Queries

Khaled Elbassioni, Rishikesh Gajjala, Saurabh Ray

We give exponential quantum query separations between the standard XOR interface and two forward-only interfaces that supply neither an adjoint nor an inverse oracle. Let $X=\F_2^n…