  In the permutation inversion problem, the task is to find the preimage of
some challenge value, given oracle access to the permutation. This is a
fundamental problem in query complexity, and appears in many contexts,
particularly cryptography. In this work, we examine the setting in which the
oracle allows for quantum queries to both the forward and the inverse direction
of the permutation -- except that the challenge value cannot be submitted to
the latter. Within that setting, we consider two options for the inversion
algorithm: whether it can get quantum advice about the permutation, and whether
it must produce the entire preimage (search) or only the first bit (decision).
We prove several theorems connecting the hardness of the resulting variations
of the inversion problem, and establish a number of lower bounds. Our results
indicate that, perhaps surprisingly, the inversion problem does not become
significantly easier when the adversary is granted oracle access to the
inverse, provided it cannot query the challenge itself.
