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 Creates Exponential Quantum Query Separations

Khaled Elbassioni, Rishikesh Gajjala, Saurabh Ray

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

Abstract

We prove an exponential separation between standard (XOR) quantum queries and forward-erasing queries for a Boolean property of injective functions, answering a question of Aaronson~\cite{Aaronson2021Open}. We also obtain an exponential separation for a Boolean promise problem on permutations, where forward in-place queries are unitary but inverse queries are not supplied. Our construction follows Aaronson's suggestion of appending fixed random garbage to a Simon function. Let $X=\{0,1\}^n$ and $N=2^n$. We use the injection $f_{h,r}(x)=(h(x),x,r_x)$, where $h:X\to X$ is promised to be either a permutation or a Simon function, and $r:X\to X$ is an arbitrary tag table that is reused on every query. The resulting problem is solvable with at most $n+2$ standard queries, but requires $Θ(\sqrt N)$ forward-erasing queries, matching classical collision sampling. Embedding these instances into permutations, with the copy of $x$ replaced by a single bit that keeps the embedding injective, gives a promise problem on permutations of $L=4N^2$ elements that requires $O(\log L)$ standard queries versus $Θ(L^{1/4})$ forward in-place queries. The lower bounds use the recording method. We replace each query by a nearby contraction that records cells of a purified tag table. After $T$ queries, tracing out the purified tag table yields a sum of positive-semidefinite contributions, each depending on $h$ at no more than $T$ addresses. A query-by-query hybrid bounds the trace-norm difference between the actual and auxiliary final operators by $O(T/\sqrt N)$. Random permutations and random Simon functions have the same restriction distribution on such a set unless it contains a hidden Simon pair, an event of probability $O(T^2/N)$. Consequently, the actual final states in the two cases remain close unless $T=Ω(\sqrt N)$, giving the required lower bounds.

Related papers

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•32 citations

Exponential quantum-classical query separations for cyclic Forrelation

Yuxin Zhang, Changpeng Shao

We study the randomized classical query complexity of cyclic Forrelation, a cyclic analogue of $k$-Forrelation [AA15, STOC'15; BS21, STOC'21]. Given $k$ Boolean functions $f_1,\ldots,f_k:\mathbb{F}_2^n\to\{-1,1\}$, the goal is to estimate $T_k=N^{-1}\operatorname{Tr}(D_{f_1}H^{\otimes n}\cdots D_{f_k}H^{\otimes n}),$ where $D_{f_i}=\operatorname{diag}(f_i(x):x\in\mathbb{F}_2^n)$, $H$ is the Hadamard gate, and $N=2^n$. This normalized-trace problem can be solved with $k$ quantum queries in the DQC1 model. Its classical query complexity was left open in [JLS+26, FOCS'26], which conjectured a lower bound of $\widetildeΩ(N^{1-2/k})$. We establish a nearly complete characterization of the nonadaptive classical query complexity of cyclic Forrelation. For even $k\ge 4$, we prove a tight bound of $Θ_k(N^{1-2/k})$ for constant additive error. For odd $k\ge 5$, we obtain a lower bound of $Ω_k(N^{1-2/(k-1)})$ and an upper bound of $O_k(N^{1-2/k})$. Surprisingly, $k=3$ admits a polylogarithmic-query nonadaptive classical algorithm, disproving the conjecture in this case. These results suggest an unexpected parity-dependent structure: the nonadaptive complexity may be governed by the independence number of the $k$-cycle, leading to the exponent $1-1/\lfloor k/2\rfloor$, rather than the previously conjectured $1-2/k$, which was motivated by a Fourier-growth heuristic. Finally, allowing adaptivity, we prove a lower bound of $Ω(N^{1/4})$ for every $k\ge4$. Although formally close to $k$-Forrelation, the cyclic structure leads to rather different classical behavior and requires different techniques. Our lower bounds are based on hidden-shift collision constructions, and our upper bounds follow from randomized sampling together with cycle-specific conditional-moment estimates. Our results provide a systematic understanding of its query advantages over classical computation.

quant-pharXiv:2610.41694•Nov 2, 2026•0 citations

On Random Purifications of Isometries and Channels

Eli Goldin

Acorn tricks turn weak quantum resources into stronger "randomized" ones. A recent example is the random purification channel, which turns $t$ copies of a mixed state into $t$ copies of a random purification. We ask whether analogous techniques can turn queries to an isometry into queries to a random unitary completion, or queries to a quantum channel into queries to a random isometry dilation. For an isometry from dimension $N$ to dimension $M$, we give an efficient, stateful simulator for $T$ sequential, forward queries to a fixed Haar random unitary completion. It uses at most one forward isometry query per simulated call, with total trace-distance error $O(T\sqrt{N/(M-T)})$. This lifts isometry query lower bounds to arbitrary unitary completions, and copy complexity lower bounds to forward access to state preparation unitaries, with dimension-dependent loss that can be made arbitrarily small for most applications. Conversely, we construct two distributions on quantum channels distinguishable exactly with two queries to an arbitrary dilation, but requiring exponentially many channel queries for nonnegligible advantage. This rules out efficient simulation of random channel dilations. Our technique also shows that approximating the quantum switch to any constant error below $1/2$ requires exponentially many channel queries, even for identical channels, giving an exponential query advantage for indefinite causal order and improving on Bavaresco et al. (2025). Finally, we show how to "decontrol" controlled forward access to an isometry: any algorithm making controlled queries to $φV$ for a random phase $φ$ can be transformed into one using the same number of uncontrolled forward queries to $V$, generalizing the analogous result for unitaries.

quant-pharXiv:2611.04573•Nov 4, 2026•2 citations

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•3 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

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•3 citations
We prove an exponential separation between standard (XOR) quantum queries and forward-erasing queries for a Boolean property of injective functions, answering a question of Aaronson~\cite{Aaronson2021Open}. We also obtain an exponential separation for a Boolean promise problem on permutations, where forward in-place queries are unitary but inverse queries are not supplied.
Our construction follows Aaronson's suggestion of appending fixed random garbage to a Simon function. Let X={0,1}nX=\{0,1\}^nX={0,1}n and N=2nN=2^nN=2n. We use the injection 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 function, and r:X→Xr:X\to Xr:X→X is an arbitrary tag table that is reused on every query. The resulting problem is solvable with at most n+2n+2n+2 standard queries, but requires Θ(N)Θ(\sqrt N)Θ(N​) forward-erasing queries, matching classical collision sampling. Embedding these instances into permutations, with the copy of xxx replaced by a single bit that keeps the embedding injective, gives a promise problem on permutations of L=4N2L=4N^2L=4N2 elements that requires O(log⁡L)O(\log L)O(logL) standard queries versus Θ(L1/4)Θ(L^{1/4})Θ(L1/4) forward in-place queries.
The lower bounds use the recording method. We replace each query by a nearby contraction that records cells of a purified tag table. After TTT queries, tracing out the purified tag table yields a sum of positive-semidefinite contributions, each depending on hhh at no more than TTT addresses. A query-by-query hybrid bounds the trace-norm difference between the actual and auxiliary final operators by O(T/N)O(T/\sqrt N)O(T/N​). Random permutations and random Simon functions have the same restriction distribution on such a set unless it contains a hidden Simon pair, an event of probability O(T2/N)O(T^2/N)O(T2/N). Consequently, the actual final states in the two cases remain close unless T=Ω(N)T=Ω(\sqrt N)T=Ω(N​), giving the required lower bounds.
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.
We study the randomized classical query complexity of cyclic Forrelation, a cyclic analogue of kkk-Forrelation [AA15, STOC'15; BS21, STOC'21]. Given kkk Boolean functions f1,…,fk:F2n→{−1,1}f_1,\ldots,f_k:\mathbb{F}_2^n\to\{-1,1\}f1​,…,fk​:F2n​→{−1,1}, the goal is to estimate Tk=N−1Tr⁡(Df1H⊗n⋯DfkH⊗n),T_k=N^{-1}\operatorname{Tr}(D_{f_1}H^{\otimes n}\cdots D_{f_k}H^{\otimes n}),Tk​=N−1Tr(Df1​​H⊗n⋯Dfk​​H⊗n), where Dfi=diag⁡(fi(x):x∈F2n)D_{f_i}=\operatorname{diag}(f_i(x):x\in\mathbb{F}_2^n)Dfi​​=diag(fi​(x):x∈F2n​), HHH is the Hadamard gate, and N=2nN=2^nN=2n. This normalized-trace problem can be solved with kkk quantum queries in the DQC1 model. Its classical query complexity was left open in [JLS+26, FOCS'26], which conjectured a lower bound of Ω~(N1−2/k)\widetildeΩ(N^{1-2/k})Ω(N1−2/k). We establish a nearly complete characterization of the nonadaptive classical query complexity of cyclic Forrelation. For even k≥4k\ge 4k≥4, we prove a tight bound of Θk(N1−2/k)Θ_k(N^{1-2/k})Θk​(N1−2/k) for constant additive error. For odd k≥5k\ge 5k≥5, we obtain a lower bound of Ωk(N1−2/(k−1))Ω_k(N^{1-2/(k-1)})Ωk​(N1−2/(k−1)) and an upper bound of Ok(N1−2/k)O_k(N^{1-2/k})Ok​(N1−2/k). Surprisingly, k=3k=3k=3 admits a polylogarithmic-query nonadaptive classical algorithm, disproving the conjecture in this case. These results suggest an unexpected parity-dependent structure: the nonadaptive complexity may be governed by the independence number of the kkk-cycle, leading to the exponent 1−1/⌊k/2⌋1-1/\lfloor k/2\rfloor1−1/⌊k/2⌋, rather than the previously conjectured 1−2/k1-2/k1−2/k, which was motivated by a Fourier-growth heuristic. Finally, allowing adaptivity, we prove a lower bound of Ω(N1/4)Ω(N^{1/4})Ω(N1/4) for every k≥4k\ge4k≥4. Although formally close to kkk-Forrelation, the cyclic structure leads to rather different classical behavior and requires different techniques. Our lower bounds are based on hidden-shift collision constructions, and our upper bounds follow from randomized sampling together with cycle-specific conditional-moment estimates. Our results provide a systematic understanding of its query advantages over classical computation.
Acorn tricks turn weak quantum resources into stronger "randomized" ones. A recent example is the random purification channel, which turns ttt copies of a mixed state into ttt copies of a random purification. We ask whether analogous techniques can turn queries to an isometry into queries to a random unitary completion, or queries to a quantum channel into queries to a random isometry dilation. For an isometry from dimension NNN to dimension MMM, we give an efficient, stateful simulator for TTT sequential, forward queries to a fixed Haar random unitary completion. It uses at most one forward isometry query per simulated call, with total trace-distance error O(TN/(M−T))O(T\sqrt{N/(M-T)})O(TN/(M−T)​). This lifts isometry query lower bounds to arbitrary unitary completions, and copy complexity lower bounds to forward access to state preparation unitaries, with dimension-dependent loss that can be made arbitrarily small for most applications. Conversely, we construct two distributions on quantum channels distinguishable exactly with two queries to an arbitrary dilation, but requiring exponentially many channel queries for nonnegligible advantage. This rules out efficient simulation of random channel dilations. Our technique also shows that approximating the quantum switch to any constant error below 1/21/21/2 requires exponentially many channel queries, even for identical channels, giving an exponential query advantage for indefinite causal order and improving on Bavaresco et al. (2025). Finally, we show how to "decontrol" controlled forward access to an isometry: any algorithm making controlled queries to φVφVφV for a random phase φφφ can be transformed into one using the same number of uncontrolled forward queries to VVV, generalizing the analogous result for unitaries.
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 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.
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.