#StackBounty: #lower-bounds Proof that quantum computers can't easily invert permutations

Bounty: 50

Let’s say I am given a permutation $sigma$ that maps $n$ bit strings to $n$ bit strings. I want to output $1$ if $sigma^{-1}(1)$ is even and $0$ if $sigma^{-1}(1)$ is odd. This is the famous permutation inversion problem and it can be proven that this problem requires an exponential number of queries to the permutation oracle. There are many ways to prove this lower bound, like using the hybrid argument, or the adversary method, or showing this problem is equivalent to Grover’s search. I am specifically looking for a hybrid argument.

I found one here (Theorem $3.6$), but it deals with random permutation oracles instead of a fixed oracle. I don’t think that condition should be necessary. Also, the proof seems very complicated. Can someone provide a simplified treatment?


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.