Quantum query complexity is typically characterized in terms of XOR queries |x,y> to |x,y+f(x)> or phase queries, which ensure that even queries to non-invertible functions are unitary. When querying a permutation, another natural model is unitary: in-place queries |x> to |f(x)>. Some problems are known to require exponentially fewer in-place queries than XOR queries, but no separation has been shown in the opposite direction. A candidate for such a separation was the problem of inverting a permutation over N elements. This task, equivalent to unstructured search in the context of permutations, is solvable with $O(\sqrt{N})$ XOR queries but was conjectured to require $Ω(N)$ in-place queries. We refute this conjecture by designing a quantum algorithm for Permutation Inversion using $O(\sqrt{N})$ in-place queries. Our algorithm achieves the same speedup as Grover's algorithm despite the inability to efficiently uncompute queries or perform straightforward oracle-controlled reflections. Nonetheless, we show that there are indeed problems which require fewer XOR queries than in-place queries. We introduce a subspace-conversion problem called Function Erasure that requires 1 XOR query and $Θ(\sqrt{N})$ in-place queries. Then, we build on a recent extension of the quantum adversary method to characterize exact conditions for a decision problem to exhibit such a separation, and we propose a candidate problem.Quantum query complexity is typically characterized in terms of XOR queries |x,y> to |x,y+f(x)> or phase queries, which ensure that even queries to non-invertible functions are unitary. When querying a permutation, another natural model is unitary: in-place queries |x> to |f(x)>. Some problems are known to require exponentially fewer in-place queries than XOR queries, but no separation has been shown in the opposite direction. A candidate for such a separation was the problem of inverting a permutation over N elements. This task, equivalent to unstructured search in the context of permutations, is solvable with $O(\sqrt{N})$ XOR queries but was conjectured to require $Ω(N)$ in-place queries. We refute this conjecture by designing a quantum algorithm for Permutation Inversion using $O(\sqrt{N})$ in-place queries. Our algorithm achieves the same speedup as Grover's algorithm despite the inability to efficiently uncompute queries or perform straightforward oracle-controlled reflections. Nonetheless, we show that there are indeed problems which require fewer XOR queries than in-place queries. We introduce a subspace-conversion problem called Function Erasure that requires 1 XOR query and $Θ(\sqrt{N})$ in-place queries. Then, we build on a recent extension of the quantum adversary method to characterize exact conditions for a decision problem to exhibit such a separation, and we propose a candidate problem.

arXiv:2504.03620Leibniz international proceedings in informaticsJan 1, 20250 citations

On the Two-sided Permutation Inversion Problem

Gorjan Alagic, Chen Bai, Alexander Poremba +1 more

In the permutation inversion problem, the task is to find the preimage of some challenge value, given oracle access to the permutation. This fundamental problem in query complexity 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 three options for the inversion algorithm: whether it can get quantum advice about the permutation, whether the query algorithm can restrict the distribution with which the challenge input is sampled, 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 permutation inversion problem and establish lower bounds for them. Our results show that, perhaps surprisingly, the permutation inversion problem does not become significantly easier when the adversary is granted oracle access to the inverse—provided it cannot query the challenge itself.In the permutation inversion problem, the task is to find the preimage of some challenge value, given oracle access to the permutation. This fundamental problem in query complexity 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 three options for the inversion algorithm: whether it can get quantum advice about the permutation, whether the query algorithm can restrict the distribution with which the challenge input is sampled, 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 permutation inversion problem and establish lower bounds for them. Our results show that, perhaps surprisingly, the permutation inversion problem does not become significantly easier when the adversary is granted oracle access to the inverse—provided it cannot query the challenge itself.

arXiv:2306.13729IACR Communications in CryptologyApr 9, 20246 citations

A state-space approach to quantum permutations

J.P. McCarthy

Expositiones MathematicaeDec 30, 20213 citations

A note on the quantum query complexity of permutation symmetric functions

André Chailloux

It is known since the work of [AA14] that for any permutation symmetric function $f$ , the quantum query complexity is at most polynomially smaller than the classical randomized query complexity, more precisely that $R(f) = \widetilde{O}\left(Q^7(f)\right)$ . In this paper, we improve this result and show that $R(f) = {O}\left(Q^3(f)\right)$ for a more general class of symmetric functions. Our proof is constructive and relies largely on the quantum hardness of distinguishing a random permutation from a random function with small range from Zhandry [Zha15].It is known since the work of [AA14] that for any permutation symmetric function $f$, the quantum query complexity is at most polynomially smaller than the classical randomized query complexity, more precisely that $R(f) = \widetilde{O}\left(Q^7(f)\right)$. In this paper, we improve this result and show that $R(f) = {O}\left(Q^3(f)\right)$ for a more general class of symmetric functions. Our proof is constructive and relies largely on the quantum hardness of distinguishing a random permutation from a random function with small range from Zhandry [Zha15].

arXiv:1810.01790Oct 3, 20182 citations

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$, $N=|X|$ , and $f_{h,r}(x)=(h(x),x,r_x)$ , where $h:X\to X$ is promised to be either a permutation or a Simon two-to-one function, and $r$ is a fixed table of $n$ -bit tags, unrestricted by the promise and reused on every query. The resulting problem is solvable with at most $n+2$ standard XOR queries, but has forward-erasing query complexity $Θ(\sqrt N)$ . This answers affirmatively open question 11 in [Scott Aaronson. Open problems related to quantum query complexity. ACM Transactions on Quantum Computing, 2(4):14:1-14:9, 2021] . We also embed these instances into permutations. The detailed construction retains the copy of $x$ in each prescribed output, but for these promises that copy can be replaced by one bit that distinguishes the two inputs in every Simon pair. This gives a permutation domain of size $L=4N^2$ and a permutation problem with the same standard-query upper bound and forward-only in-place query complexity $Θ(\sqrt N)=Θ(L^{1/4})$ . Both lower bounds remain valid with a clean coherent bypass. The common lower bound uses an analysis-only recording replacement. In the replacement computation, tracing out the fixed random tag table after $T$ calls gives a sum of positive-semidefinite operator contributions, each depending on $h$ at no more than $T$ addresses. On such a set, the restrictions induced by random permutations and random Simon functions differ only if the set contains a hidden Simon pair, an event of probability $O(T^2/N)$ .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$, $N=|X|$, and $f_{h,r}(x)=(h(x),x,r_x)$, where $h:X\to X$ is promised to be either a permutation or a Simon two-to-one function, and $r$ is a fixed table of $n$-bit tags, unrestricted by the promise and reused on every query. The resulting problem is solvable with at most $n+2$ standard XOR queries, but has forward-erasing query complexity $Θ(\sqrt N)$. This answers affirmatively open question 11 in [Scott Aaronson. Open problems related to quantum query complexity. ACM Transactions on Quantum Computing, 2(4):14:1-14:9, 2021] . We also embed these instances into permutations. The detailed construction retains the copy of $x$ in each prescribed output, but for these promises that copy can be replaced by one bit that distinguishes the two inputs in every Simon pair. This gives a permutation domain of size $L=4N^2$ and a permutation problem with the same standard-query upper bound and forward-only in-place query complexity $Θ(\sqrt N)=Θ(L^{1/4})$. Both lower bounds remain valid with a clean coherent bypass. The common lower bound uses an analysis-only recording replacement. In the replacement computation, tracing out the fixed random tag table after $T$ calls gives a sum of positive-semidefinite operator contributions, each depending on $h$ at no more than $T$ addresses. On such a set, the restrictions induced by random permutations and random Simon functions differ only if the set contains a hidden Simon pair, an event of probability $O(T^2/N)$.

cs.CCCross-listedarXiv:2609.03628Sep 4, 20260 citations

O(\sqrt{N})

XOR queries but was conjectured to require

Ω(N)

in-place queries. We refute this conjecture by designing a quantum algorithm for Permutation Inversion using

O(\sqrt{N})

in-place queries. Our algorithm achieves the same speedup as Grover's algorithm despite the inability to efficiently uncompute queries or perform straightforward oracle-controlled reflections. Nonetheless, we show that there are indeed problems which require fewer XOR queries than in-place queries. We introduce a subspace-conversion problem called Function Erasure that requires 1 XOR query and

Θ(\sqrt{N})

in-place queries. Then, we build on a recent extension of the quantum adversary method to characterize exact conditions for a decision problem to exhibit such a separation, and we propose a candidate problem.

It is known since the work of [AA14] that for any permutation symmetric function

f

, the quantum query complexity is at most polynomially smaller than the classical randomized query complexity, more precisely that

R(f) = \widetilde{O}\left(Q^7(f)\right)

. In this paper, we improve this result and show that

R(f) = {O}\left(Q^3(f)\right)

for a more general class of symmetric functions. Our proof is constructive and relies largely on the quantum hardness of distinguishing a random permutation from a random function with small range from Zhandry [Zha15].

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$,

N=|X|

, and

f_{h,r}(x)=(h(x),x,r_x)

, where

h:X\to X

is promised to be either a permutation or a Simon two-to-one function, and

r

is a fixed table of

n

-bit tags, unrestricted by the promise and reused on every query. The resulting problem is solvable with at most

n+2

standard XOR queries, but has forward-erasing query complexity

Θ(\sqrt N)

. This answers affirmatively open question 11 in [Scott Aaronson. Open problems related to quantum query complexity. ACM Transactions on Quantum Computing, 2(4):14:1-14:9, 2021] . We also embed these instances into permutations. The detailed construction retains the copy of

x

in each prescribed output, but for these promises that copy can be replaced by one bit that distinguishes the two inputs in every Simon pair. This gives a permutation domain of size

L=4N^2

and a permutation problem with the same standard-query upper bound and forward-only in-place query complexity

Θ(\sqrt N)=Θ(L^{1/4})

. Both lower bounds remain valid with a clean coherent bypass. The common lower bound uses an analysis-only recording replacement. In the replacement computation, tracing out the fixed random tag table after

T

calls gives a sum of positive-semidefinite operator contributions, each depending on

h

at no more than

T

addresses. On such a set, the restrictions induced by random permutations and random Simon functions differ only if the set contains a hidden Simon pair, an event of probability

O(T^2/N)