Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.03628

Random Garbage Separates XOR from Forward-Only Queries

Khaled Elbassioni, Rishikesh Gajjala, Saurabh Ray

cs.CCquant-phSubmitted Sep 3, 2026• Announced Sep 4, 2026• 0 citations• Revised Sep 7, 2026 (v2)
v1 · Sep 3, 2026v2 · Sep 7, 2026
arXivHTMLPDF

Abstract

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)$.

Related papers

Quantum Search with In-Place Queries

Blake Holman, Ronak Ramachandran, Justin Yirka

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.03620•Leibniz international proceedings in informatics•Jan 1, 2025•0 citations

Explicit Separations for One-Query Unitary Synthesis

Fangqi Dong, Alex Lombardi, Fermi Ma

The unitary synthesis problem (Aaronson-Kuperberg, CCC 2007) asks whether every $n$-qubit unitary $U$ is computable by efficient quantum circuits relative to some classical oracle $f = f_U$ depending on $U$. Recently, Lombardi-Ma-Wright (STOC 2024) proved that Haar-random unitaries cannot be efficiently synthesized by algorithms that make 1 query (or poly$(n)$ parallel queries) to an arbitrary classical oracle. In this work, we prove several results about the hardness (and easiness!) of variants of unitary synthesis. Our results include: (1) 1-query vs. 2-query unitary synthesis: we prove 1-query lower bounds for synthesizing random permutation unitaries $P\lvert x\rangle = \lvert π(x)\rangle$, as well as random alternating-basis phase unitaries $F_2 \cdot H^{\otimes n} \cdot F_1$. This gives 1-query lower bounds for "explicit" families of unitaries that have efficient (even 2-query) synthesis algorithms. (2) Upper bound for complex phase unitaries: we also consider complex phase unitaries $\lvert x\rangle\mapsto α_x \lvert x\rangle$, which have a clean 2-query synthesis algorithm with no obvious 1-query algorithm. In this case, we prove an upper bound: there are 1-query algorithms (relative to binary phase oracles) that constant-approximate these unitaries in diamond distance. In order to prove our lower bounds, we introduce and analyze two new cryptographic games: the oracle state search game and the oracle Choi state game. Compared to prior work, our framework is mathematically simple, more flexible in what it can prove, and more accurately captures the hardness of synthesizing unitaries that are not "fully random". Finally, we also use the search game to prove a new hardness-of-approximation result for quantum programs (synthesizing unitaries relative to quantum advice) for phase unitaries, giving a sharper separation between 1-query unitary synthesis and quantum programs.

quant-pharXiv:2607.26478•Jul 30, 2026•0 citations

Towards Optimal Separations between Quantum and Randomized Query Complexities

Avishay Tal

The query model offers a concrete setting where quantum algorithms are provably superior to randomized algorithms. Beautiful results by Bernstein-Vazirani, Simon, Aaronson, and others presented partial Boolean functions that can be computed by quantum algorithms making much fewer queries compared to their randomized analogs. To date, separations of O(1) vs. √N between quantum and randomized query complexities remain the state-of-the-art (where N is the input length), leaving open the question of whether O(1) vs. N1/2+Ω(1)separations are possible? We answer this question in the affirmative. Our separating problem is a variant of the Aaronson-Ambainis k-fold Forrelation problem. We show that our variant: 1)Can be solved by a quantum algorithm making 2O(k)queries to the inputs. 2)Requires at least ~Ω(N2(k-1)/(3k-1)) queries for any randomized algorithm. For any constant , this gives a O(1) vs. N1/2-εseparation between the quantum and randomized query complexities of partial Boolean functions. Our proof is Fourier analytical and uses new bounds on the Fourier spectrum of classical decision trees, which could be of independent interest. Looking forward, we conjecture that the Fourier bounds could be further improved in a precise manner, and show that such conjectured bounds imply optimal O(1) vs. N1-εseparations between the quantum and randomized query complexities of partial Boolean functions.

arXiv:1912.12561•Annual Symposium on Foundations of Computer Science•Nov 1, 2020•25 citations

Quantum Security of XOR of Permutations via Fourier Analysis

Wonseok Choi, Minki Hhan, Junyoung Jang

The XOR of two or more independent random permutations (XoP) is the prototypical pseudorandom function built from permutations achieving security beyond the birthday bound. The classical security of the XoP construction is well established, but its security against quantum attacks that query XoP in superposition has remained widely open. We prove that the XOR of $r\ge 2$ random permutations over $\{0,1\}^n$ is indistinguishable from a random function by any $q$-query quantum algorithm with advantage \[O\left(\min\left\{\frac{q^3}{2^{rn}},\frac{q^{1.5}}{2^{(r-0.5)n}},\frac{1}{2^{(r-1.5)n}}\right\}\right)\] for all $q\ll 2^n$. In particular, XoP remains secure throughout the entire query range, far beyond the $2^{n/3}$ bound due to quantum collision finding attacks. This is the first construction from permutations that achieves the quantum version of the beyond birthday bound security. We also present several heuristic attacks suggesting the tightness of our bounds in ranges $q\le 2^{n/2}$ and $\approx 2^n$. We use a Fourier-analytic variant of the polynomial method: the advantage of any $q$-query quantum algorithm is controlled by the Fourier components of degree at most $2q$, or by $2q$ input-output data of the construction. The norms of most components are bounded well, proving the bound $2^{-(r-3/2)n}$. The norm of low-degree components turn out to be too large for the bounds $q^3/2^{rn}$ and $q^{1.5}/2^{(r-0.5)n}$. We reinterpret these low-degree components as (sums of) advantages of the other problems. For example, the degree-2 and degree-4 terms are interpreted as the advantages against random functions with and without \emph{planted collisions}, which in turn are bounded using Zhandry's small-range distributions. Along the way, we prove a new bound for the small-range indistinguishability for (ironically) large ranges, which is of independent interest.

quant-pharXiv:2609.34413•Sep 29, 2026•0 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.

arXiv:2306.13729•IACR Communications in Cryptology•Apr 9, 2024•6 citations

IQP circuits for 2-Forrelation

Quentin Buzet, André Chailloux

The $2$-Forrelation problem provides an optimal separation between classical and quantum query complexity and is also the problem used for separating $\mathsf{BQP}$ and $\mathsf{PH}$ relative to an oracle. A natural question is therefore to ask what are the minimal quantum resources needed to solve this problem. We show that $2$-Forrelation can be solved using Instantaneous Quantum Polynomial-time ($\mathsf{IQP}$) circuits, a restricted model of quantum computation in which all gates commute. Concretely, signed $2$-Forrelation can be solved by a classical random choice between two one-query $\mathsf{IQP}$ circuits, while the absolute-value variant uses two independent executions of this randomized procedure. This answers a recent open question of Girish (STOC 2026) on the power of commuting quantum computations. For the Raz-Tal distribution, this randomization is unnecessary. We use this to show that there is an oracle $O$ such that $\mathsf{IQP}^O \not\subseteq \mathsf{PH}^O$, strengthening the result of Raz and Tal (STOC 2019). It also yields an oracle separation between $\mathsf{IQP}$ and $\mathsf{DQC}_1$. We prove Fourier growth bounds for multi-query $\mathsf{IQP}$ circuits, including bounds in terms of the size of their accepting set. Our results suggest a possible route toward decision-based quantum advantage within the restricted $\mathsf{IQP}$ model. The key ingredient is an algebraic identity of the quadratic function $Q(x) = \sum_{i < j} x_ix_j$ that allows extracting inner-product phases within an $\mathsf{IQP}$ circuit.

quant-pharXiv:2604.15248•Apr 17, 2026•0 citations
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=\F2nX=\F_2^nX=\F2n​, N=∣X∣N=|X|N=∣X∣, and fh,r(x)=(h(x),x,rx)f_{h,r}(x)=(h(x),x,r_x)fh,r​(x)=(h(x),x,rx​), where h:X→Xh:X\to Xh:X→X is promised to be either a permutation or a Simon two-to-one function, and rrr is a fixed table of nnn-bit tags, unrestricted by the promise and reused on every query. The resulting problem is solvable with at most n+2n+2n+2 standard XOR queries, but has forward-erasing query complexity Θ(N)Θ(\sqrt N)Θ(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 xxx 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=4N2L=4N^2L=4N2 and a permutation problem with the same standard-query upper bound and forward-only in-place query complexity Θ(N)=Θ(L1/4)Θ(\sqrt N)=Θ(L^{1/4})Θ(N​)=Θ(L1/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 TTT calls gives a sum of positive-semidefinite operator contributions, each depending on hhh at no more than TTT 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(T2/N)O(T^2/N)O(T2/N).
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(N)O(\sqrt{N})O(N​) XOR queries but was conjectured to require Ω(N)Ω(N)Ω(N) in-place queries. We refute this conjecture by designing a quantum algorithm for Permutation Inversion using O(N)O(\sqrt{N})O(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 Θ(N)Θ(\sqrt{N})Θ(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.
The unitary synthesis problem (Aaronson-Kuperberg, CCC 2007) asks whether every nnn-qubit unitary UUU is computable by efficient quantum circuits relative to some classical oracle f=fUf = f_Uf=fU​ depending on UUU. Recently, Lombardi-Ma-Wright (STOC 2024) proved that Haar-random unitaries cannot be efficiently synthesized by algorithms that make 1 query (or poly(n)(n)(n) parallel queries) to an arbitrary classical oracle. In this work, we prove several results about the hardness (and easiness!) of variants of unitary synthesis. Our results include: (1) 1-query vs. 2-query unitary synthesis: we prove 1-query lower bounds for synthesizing random permutation unitaries P∣x⟩=∣π(x)⟩P\lvert x\rangle = \lvert π(x)\rangleP∣x⟩=∣π(x)⟩, as well as random alternating-basis phase unitaries F2⋅H⊗n⋅F1F_2 \cdot H^{\otimes n} \cdot F_1F2​⋅H⊗n⋅F1​. This gives 1-query lower bounds for "explicit" families of unitaries that have efficient (even 2-query) synthesis algorithms. (2) Upper bound for complex phase unitaries: we also consider complex phase unitaries ∣x⟩↦αx∣x⟩\lvert x\rangle\mapsto α_x \lvert x\rangle∣x⟩↦αx​∣x⟩, which have a clean 2-query synthesis algorithm with no obvious 1-query algorithm. In this case, we prove an upper bound: there are 1-query algorithms (relative to binary phase oracles) that constant-approximate these unitaries in diamond distance. In order to prove our lower bounds, we introduce and analyze two new cryptographic games: the oracle state search game and the oracle Choi state game. Compared to prior work, our framework is mathematically simple, more flexible in what it can prove, and more accurately captures the hardness of synthesizing unitaries that are not "fully random". Finally, we also use the search game to prove a new hardness-of-approximation result for quantum programs (synthesizing unitaries relative to quantum advice) for phase unitaries, giving a sharper separation between 1-query unitary synthesis and quantum programs.
The query model offers a concrete setting where quantum algorithms are provably superior to randomized algorithms. Beautiful results by Bernstein-Vazirani, Simon, Aaronson, and others presented partial Boolean functions that can be computed by quantum algorithms making much fewer queries compared to their randomized analogs. To date, separations of O(1) vs. √N between quantum and randomized query complexities remain the state-of-the-art (where N is the input length), leaving open the question of whether O(1) vs. N1/2+Ω(1)separations are possible? We answer this question in the affirmative. Our separating problem is a variant of the Aaronson-Ambainis k-fold Forrelation problem. We show that our variant: 1)Can be solved by a quantum algorithm making 2O(k)queries to the inputs. 2)Requires at least ~Ω(N2(k-1)/(3k-1)) queries for any randomized algorithm. For any constant , this gives a O(1) vs. N1/2-εseparation between the quantum and randomized query complexities of partial Boolean functions. Our proof is Fourier analytical and uses new bounds on the Fourier spectrum of classical decision trees, which could be of independent interest. Looking forward, we conjecture that the Fourier bounds could be further improved in a precise manner, and show that such conjectured bounds imply optimal O(1) vs. N1-εseparations between the quantum and randomized query complexities of partial Boolean functions.
The XOR of two or more independent random permutations (XoP) is the prototypical pseudorandom function built from permutations achieving security beyond the birthday bound. The classical security of the XoP construction is well established, but its security against quantum attacks that query XoP in superposition has remained widely open. We prove that the XOR of r≥2r\ge 2r≥2 random permutations over {0,1}n\{0,1\}^n{0,1}n is indistinguishable from a random function by any qqq-query quantum algorithm with advantage O(min⁡{q32rn,q1.52(r−0.5)n,12(r−1.5)n})O\left(\min\left\{\frac{q^3}{2^{rn}},\frac{q^{1.5}}{2^{(r-0.5)n}},\frac{1}{2^{(r-1.5)n}}\right\}\right)O(min{2rnq3​,2(r−0.5)nq1.5​,2(r−1.5)n1​}) for all q≪2nq\ll 2^nq≪2n. In particular, XoP remains secure throughout the entire query range, far beyond the 2n/32^{n/3}2n/3 bound due to quantum collision finding attacks. This is the first construction from permutations that achieves the quantum version of the beyond birthday bound security. We also present several heuristic attacks suggesting the tightness of our bounds in ranges q≤2n/2q\le 2^{n/2}q≤2n/2 and ≈2n\approx 2^n≈2n. We use a Fourier-analytic variant of the polynomial method: the advantage of any qqq-query quantum algorithm is controlled by the Fourier components of degree at most 2q2q2q, or by 2q2q2q input-output data of the construction. The norms of most components are bounded well, proving the bound 2−(r−3/2)n2^{-(r-3/2)n}2−(r−3/2)n. The norm of low-degree components turn out to be too large for the bounds q3/2rnq^3/2^{rn}q3/2rn and q1.5/2(r−0.5)nq^{1.5}/2^{(r-0.5)n}q1.5/2(r−0.5)n. We reinterpret these low-degree components as (sums of) advantages of the other problems. For example, the degree-2 and degree-4 terms are interpreted as the advantages against random functions with and without \emph{planted collisions}, which in turn are bounded using Zhandry's small-range distributions. Along the way, we prove a new bound for the small-range indistinguishability for (ironically) large ranges, which is of independent interest.
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.
The 222-Forrelation problem provides an optimal separation between classical and quantum query complexity and is also the problem used for separating BQP\mathsf{BQP}BQP and PH\mathsf{PH}PH relative to an oracle. A natural question is therefore to ask what are the minimal quantum resources needed to solve this problem. We show that 222-Forrelation can be solved using Instantaneous Quantum Polynomial-time (IQP\mathsf{IQP}IQP) circuits, a restricted model of quantum computation in which all gates commute. Concretely, signed 222-Forrelation can be solved by a classical random choice between two one-query IQP\mathsf{IQP}IQP circuits, while the absolute-value variant uses two independent executions of this randomized procedure. This answers a recent open question of Girish (STOC 2026) on the power of commuting quantum computations. For the Raz-Tal distribution, this randomization is unnecessary. We use this to show that there is an oracle OOO such that IQPO⊈PHO\mathsf{IQP}^O \not\subseteq \mathsf{PH}^OIQPO⊆PHO, strengthening the result of Raz and Tal (STOC 2019). It also yields an oracle separation between IQP\mathsf{IQP}IQP and DQC1\mathsf{DQC}_1DQC1​. We prove Fourier growth bounds for multi-query IQP\mathsf{IQP}IQP circuits, including bounds in terms of the size of their accepting set. Our results suggest a possible route toward decision-based quantum advantage within the restricted IQP\mathsf{IQP}IQP model. The key ingredient is an algebraic identity of the quadratic function Q(x)=∑i<jxixjQ(x) = \sum_{i < j} x_ix_jQ(x)=∑i<j​xi​xj​ that allows extracting inner-product phases within an IQP\mathsf{IQP}IQP circuit.