5
$\begingroup$

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}(000\cdots1)$ is even and $0$ if $\sigma^{-1}(000\cdots1)$ is odd. It can be proven that this problem requires an exponential number of queries, given access to just $\sigma$ and $000\cdots1$ (but, crucially, not $\sigma^{-1}$ or any oracle that calculates the parity of $\sigma^{-1}$). 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?

$\endgroup$
5
  • $\begingroup$ Initially I was confused by the question title, as it does not appear to me that your use of "hard" means what I initially thought it meant. You are not claiming that determining the parity of the inverse of a permutation is $\mathsf{BQP}$-hard, in the sense of meaning that every problem in $\mathsf{BQP}$ can be reduced (in polynomial time) to the parity of an inverse permutation; you are asking for a hybrid style argument that the BBBV-bound would apply to an oracle for determining such a parity. Correct? $\endgroup$ – Mark S Sep 25 '20 at 0:50
  • $\begingroup$ Yes, that is correct. $\endgroup$ – BlackHat18 Sep 25 '20 at 3:37
  • 1
    $\begingroup$ Picky point: if $\sigma$ is a permutation on $n$-bit strings, then $\sigma^{-1}(1)$ is only defined if $n = 1$. What do you mean instead --- possibly, to output $1$ if $\sigma^{-1}(00\cdots01)$ is a bit-string that ends in $0$ (so that it denotes an even integer in big-endian notation), and to output $0$ otherwise? $\endgroup$ – Niel de Beaudrap Sep 25 '20 at 12:03
  • $\begingroup$ Also, I am by absolutely no means knowledgeable enough to evaluate how famous the "parity inversion problem" is, in the context of computer science*/*mathematics; however Google searches seem to point to some interesting physics papers about the ground state of beryllium. This would not have come to mind when someone asks of the parity of a permutation, which I take to mean the even-ness or odd-ness of the number of transpositions in the permutation; nor do I see an immediate relation to the question as restated by @NieldeBeaudrap. Can you perhaps edit the question for more clarity? $\endgroup$ – Mark S Sep 25 '20 at 14:02
  • $\begingroup$ Edited the question. $\endgroup$ – BlackHat18 Sep 25 '20 at 18:41
1
$\begingroup$

The link to the paper in the question is by Bennett, Bernstein, Brassard, and Vazirani (BBBV).

The standard BBBV oracular problem to which the OP refers may be recast as, given the value $y$ of a permutation $y=f(x)$ acting on $n$ inputs, find a full preimage $x=x_1x_2\cdots x_n$ of the permutation which evaluates to $y$. BBBV provided a lower bound, noting that it may take at least $\mathcal{O}(\sqrt{2^n})$ calls to the oracle. Somewhat famously, the same upper bound was found, almost simultaneously with BBBV, by Grover.

However, as the OP suggests, such a proof initially presented in the BBBV paper may be challenging to understand (I think they called it the "polynomial method"); there have been a number of improvements such as the as-mentioned "hybrid method" and culminating in the "adversarial method" of Ambainis. I like O'Donnell's lecture on ways to prove the BBBV bound.

The question of the OP seems not ask for a lower bound not for the full preimage $x_1 x_2\cdots x_n$, but only for the least significant bit (LSB) $x_n$ of the preimage. But if one has a quick oracle to know the LSB $x_n$, I think one can rinse and repeat to find the full preimage $x_1x_2\cdots x_n$ quickly as well, with only $n$ calls to the parity oracle. For example, one could define a series of $n$ permutations as in:

  • $f=f_n(x_1x_2\cdots x_n)=y_1y_2\cdots y_n$; given $f$ and $y=00\cdots 01$, the parity oracle would determine $x_n$;

  • $f_{n-1}(x_1x_2\cdots x_{n-1})=y_1y_2\cdots y_{n-1}$;

  • $\ldots$

  • $f_2(x_1x_2)=y_1y_2$;

  • $f_1(x_1)=y_1$

and use the oracle for each of the $f$ functions so-defined.

Thus, if one were to use the hybrid method to prove a lower bound on a parity oracle for the preimage of $f_n$, then the proof would carry through to each of the subsequent $f$, by simply using the results of this parity oracle to redefine new functions $f_i$.

Because the BBBV theorem, no matter how it's proved, tells us that we can't have a quick way to determine the full preimage in $\mathcal{O}(\mathrm{poly\:} n)$ time, we must not have an oracle to determine the individual parity of the preimage, because if we did, we could leverage the parity oracle with only an $\mathcal{O}(n)$-overhead.

ADDED IN AN ATTEMPT TO CLARIFY

If you can prove the BBBV theorem to show that you need an exponential number of calls to a generic oracle to fully invert a permutation, using whichever method you like (such as the hybrid method), then it also follows that there is an exponential lower bound on the number of queries to solve the problem of determining only the parity of the inverse of a function; if not, then you can still use your oracle to fully invert a function/permutation in polynomial time, which contradicts exactly what the BBBV theorem proved.

For example, assume that you can use a polynomial number of calls, say $n^3$ calls, to an oracle so that you can determine the parity $x_n$ of the preimage $x$ of a permutation function $\sigma=f$ which evaluates to a particular value $y=00\cdots01$. You can then repeat such a test to determine each of the bits of $x$, but you are doing this in polynomial time, say $n^4$ time. But this is exactly what BBBV proved you cannot do.

Thus we have a way to use the hybrid method, which proved the BBBV theorem for all bits of $x$, to show that we require an exponential number of calls to an oracle to determine the parity of only one of the bits of $x$ (e.g. $x_n$).

(This is just an answer to show that determining the parity of a preimage is just as difficult as determining the preimage itself. I'm not sure if the OP's interest is about the details of the hybrid method itself, which I am not knowledgeable to speak to.)

$\endgroup$
8
  • $\begingroup$ I couldn't follow how the proof "carries over". Finding the parity reduces to finding the full pre-image; but can't it be an easier job? $\endgroup$ – BlackHat18 Sep 25 '20 at 15:21
  • $\begingroup$ In the approach described you would need $n$ calls to your parity oracle, so it's at best $n$-times easier. But $n$ is presumably very small. $\endgroup$ – Mark S Sep 25 '20 at 15:26
  • $\begingroup$ I'm still a bit unsure. Are you saying that given access to $f$ and $y$, one can cosntruct the permutations $f_{n-1}$ to $f_{1}$? $\endgroup$ – BlackHat18 Sep 25 '20 at 17:05
  • $\begingroup$ Given access to $f$ and $y$, and access to a parity oracle that provides the LSB $x_n$ of the preimage of $y=f(x)$, one can construct each of the bits of $x$ by defining new functions $f_{n-1}$ to $f_1$ based on the output of the preceding parity oracle. If you had a preimage parity oracle for one bit (the LSB), then you can repeat the oracle for each of the other bits, with only a small amount of overhead. But the BBBV theorem, proven with the hybrid method, shows that it is impossible to have a quick way to find the preimage of all of the bits. So you can't have such a parity oracle. $\endgroup$ – Mark S Sep 25 '20 at 17:20
  • $\begingroup$ Well, you can find the preimage of all the bits easily (in just one query) if you are given access to the inverse of $f$. The parity oracle seems to be doing just that: giving you access to a restricted version of the inverse of the permutation, one bit at a time. I don't think the BBBV procedure rules this out. $\endgroup$ – BlackHat18 Sep 25 '20 at 18:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.