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:2510.07622

Conjugate queries can help

Ewin Tang, Wright, John, Mark Zhandry

Published Oct 8, 2025• 63 citations
arXivHTMLPDF

Abstract

We give a natural problem over input quantum oracles $U$ which cannot be solved with exponentially many black-box queries to $U$ and $U^\dagger$, but which can be solved with constant many queries to $U$ and $U^*$, or $U$ and $U^{\mathrm{T}}$. We also demonstrate a quantum commitment scheme that is secure against adversaries that query only $U$ and $U^\dagger$, but is insecure if the adversary can query $U^*$. These results show that conjugate and transpose queries do give more power to quantum algorithms, lending credence to the idea put forth by Zhandry that cryptographic primitives should prove security against these forms of queries. Our key lemma is that any circuit using $q$ forward and inverse queries to a state preparation unitary for a state $σ$ can be simulated to $\varepsilon$ error with $n = \mathcal{O}(q^2/\varepsilon)$ copies of $σ$. Consequently, for decision tasks, algorithms using (forward and inverse) state preparation queries only ever perform quadratically better than sample access. We also identify a motif, which we call the "acorn trick", where generically strengthening a quantum resource can be possible if the output is allowed to be random, bypassing no-go theorems for deterministic algorithms. We demonstrate this idea for several settings, including controlization and purification.

DOI
10.48550/arxiv.2510.07622

Related papers

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

A One-Query Lower Bound for Unitary Synthesis and Breaking Quantum Cryptography

Alex Lombardi, Fermi Ma, John Wright

The Unitary Synthesis Problem (Aaronson-Kuperberg 2007) asks whether any n-qubit unitary U can be implemented by an efficient quantum algorithm A augmented with an oracle that computes an arbitrary Boolean function f. In other words, can the task of implementing any unitary be efficiently reduced to the task of implementing any Boolean function? In this work, we prove a one-query lower bound for unitary synthesis. We show that there exist unitaries U such that no quantum polynomial-time oracle algorithm Af can implement U, even approximately, if it only makes one (quantum) query to f. Our approach also has implications for quantum cryptography: we prove (relative to a random oracle) the existence of quantum cryptographic primitives that remain secure against all one-query adversaries Af. Since such one-query algorithms can decide any language, solve any classical search problem, and even prepare any quantum state, our result suggests that implementing random unitaries and breaking quantum cryptography may be harder than all of these tasks. To prove this result, we formulate unitary synthesis as an efficient challenger-adversary game, which enables proving lower bounds by analyzing the maximum success probability of an adversary Af. Our main technical insight is to identify a natural spectral relaxation of the one-query optimization problem, which we bound using tools from random matrix theory. We view our framework as a potential avenue to rule out polynomial-query unitary synthesis, and we state conjectures in this direction.

arXiv:2310.08870•ACM Symposium on Theory of Computing (STOC)•Jun 10, 2024•40 citations

State Synthesis with an NP oracle

Aniruddha Sen

In this note, I describe a quantum algorithm that prepares an arbitrary state $|ψ\rangle$ to inverse exponential precision in polynomial time by making queries to an $\mathsf{NP}$ oracle, assuming one can directly query entries of the state vector corresponding to $|ψ\rangle$. The previous best upper bound on the complexity class required by an oracle for this task was $\mathsf{PP}$. I provide evidence that $\mathsf{NP}$ is the best possible upper bound by showing that any quantum algorithm using a $\mathsf{P}$ oracle, or even a $\mathsf{P/poly}$ oracle, requires exponentially many queries. I also discuss some implications of this result for the $\mathsf{QMA}$ search-to-decision problem and unitary synthesis.

quant-pharXiv:2611.02370•Nov 3, 2026•0 citations

A Separation Between Types of Quantum Oracle Separations

Scott Aaronson, Adam Bouland, Jordan Docter +1 more

Recent works have demonstrated that quantum oracles have subtle behavior, as access to inverse, conjugate or controlled queries can exponentially change the query complexity of certain tasks. Inspired by these works, we introduce the notion of meta-complexity of quantum relativization. We ask: for any two quantum complexity classes, under which "types" of quantum oracles are they equal or separated? Different pantheons of oracles (or quantum oracle types, e.g. unitary vs state, poly- vs superpoly-dimensional, closed under inverse or not) form a partially ordered set based on their power in separating complexity classes. Moreover, two oracle pantheons A and B are separated if there exists a pair of complexity classes that are separated under an oracle from pantheon A but yet the complexity classes are equivalent under all oracles from pantheon B. We show that this meta-complexity can be nontrivial by giving a complete classification, within the family of oracle pantheons defined in this paper, of which models can separate the complexity classes $\mathsf{PostBQP}$ and $\mathsf{PreciseBQP}$, the exponentially precise variant of $\mathsf{BQP}$. Both classes equal $\mathsf{PP}$ in the unrelativized setting. Within our taxonomy, they remain equal relative to real or polynomial-dimensional unitary oracles and whenever inverse or conjugate access is supplied. In contrast, we give a separation relative to forward-only complex diagonal unitaries of superpolynomial dimension, as well as a separation relative to single-qubit state-preparation oracles. We view this as a test case for the meta-complexity of oracles which underscores the subtlety inherent to the relativization of quantum complexity classes.

quant-pharXiv:2609.38704•Oct 1, 2026•0 citations

Compressed Permutation Oracles

Joseph Carolan

The analysis of quantum algorithms which query random, invertible permutations has been a long-standing challenge in cryptography. Many techniques which apply to random oracles fail, or are not known to generalize to this setting. As a result, foundational cryptographic constructions involving permutations often lack quantum security proofs. With the aim of closing this gap, we develop and prove soundness of a compressed permutation oracle. Our construction shares many of the attractive features of Zhandry's original compressed function oracle: the purification is a small list of input-output pairs which meaningfully reflect an algorithm's knowledge of the oracle.

arXiv:2509.18586•ACM Symposium on Theory of Computing (STOC)•Jun 9, 2026•13 citations

On State Distinguishing Without Inverse Queries

Emma Wang, Joseph Carolan, Andrew M. Childs

In the quantum state distinguishing problem, an algorithm is given copies of a state $|ψ\rangle$ or $|φ\rangle$ separated by trace distance $\varepsilon$, and tasked with deciding which is the case. It is a standard result that $Θ(\varepsilon^{-2})$ copies are required, while having access to a unitary state preparation oracle and its inverse improves this to $Θ(\varepsilon^{-1})$ queries. We study the intermediate case with forward-only access, capturing scenarios where the oracle is a physical process that cannot be reversed. Tang and Wright recently showed that distinguishing a known state from an \emph{unknown} close state requires $Ω(\varepsilon^{-2})$ forward queries in high dimension; we strengthen this result by proving the same bound even when both states are known, as in the state distinguishing setting. Moreover, our lower bound uses a direct hybrid argument, avoiding advanced compressed oracle techniques used in the prior work. In contrast, we give a dimension-independent algorithm solving a continuous-time variant of state distinguishing with only $O(\varepsilon^{-1})$ total forward evolution time. The algorithm uses quantum Zeno dynamics to confine evolution to a known two-dimensional subspace. Thus, a quadratic advantage survives without inverse access for a natural continuous-time analogue of state distinguishing.

quant-pharXiv:2610.05389•Oct 6, 2026•1 citation
We give a natural problem over input quantum oracles UUU which cannot be solved with exponentially many black-box queries to UUU and U†U^\daggerU†, but which can be solved with constant many queries to UUU and U∗U^*U∗, or UUU and UTU^{\mathrm{T}}UT. We also demonstrate a quantum commitment scheme that is secure against adversaries that query only UUU and U†U^\daggerU†, but is insecure if the adversary can query U∗U^*U∗. These results show that conjugate and transpose queries do give more power to quantum algorithms, lending credence to the idea put forth by Zhandry that cryptographic primitives should prove security against these forms of queries. Our key lemma is that any circuit using qqq forward and inverse queries to a state preparation unitary for a state σσσ can be simulated to ε\varepsilonε error with n=O(q2/ε)n = \mathcal{O}(q^2/\varepsilon)n=O(q2/ε) copies of σσσ. Consequently, for decision tasks, algorithms using (forward and inverse) state preparation queries only ever perform quadratically better than sample access. We also identify a motif, which we call the "acorn trick", where generically strengthening a quantum resource can be possible if the output is allowed to be random, bypassing no-go theorems for deterministic algorithms. We demonstrate this idea for several settings, including controlization and purification.
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.
The Unitary Synthesis Problem (Aaronson-Kuperberg 2007) asks whether any n-qubit unitary U can be implemented by an efficient quantum algorithm A augmented with an oracle that computes an arbitrary Boolean function f. In other words, can the task of implementing any unitary be efficiently reduced to the task of implementing any Boolean function? In this work, we prove a one-query lower bound for unitary synthesis. We show that there exist unitaries U such that no quantum polynomial-time oracle algorithm Af can implement U, even approximately, if it only makes one (quantum) query to f. Our approach also has implications for quantum cryptography: we prove (relative to a random oracle) the existence of quantum cryptographic primitives that remain secure against all one-query adversaries Af. Since such one-query algorithms can decide any language, solve any classical search problem, and even prepare any quantum state, our result suggests that implementing random unitaries and breaking quantum cryptography may be harder than all of these tasks. To prove this result, we formulate unitary synthesis as an efficient challenger-adversary game, which enables proving lower bounds by analyzing the maximum success probability of an adversary Af. Our main technical insight is to identify a natural spectral relaxation of the one-query optimization problem, which we bound using tools from random matrix theory. We view our framework as a potential avenue to rule out polynomial-query unitary synthesis, and we state conjectures in this direction.
In this note, I describe a quantum algorithm that prepares an arbitrary state ∣ψ⟩|ψ\rangle∣ψ⟩ to inverse exponential precision in polynomial time by making queries to an NP\mathsf{NP}NP oracle, assuming one can directly query entries of the state vector corresponding to ∣ψ⟩|ψ\rangle∣ψ⟩. The previous best upper bound on the complexity class required by an oracle for this task was PP\mathsf{PP}PP. I provide evidence that NP\mathsf{NP}NP is the best possible upper bound by showing that any quantum algorithm using a P\mathsf{P}P oracle, or even a P/poly\mathsf{P/poly}P/poly oracle, requires exponentially many queries. I also discuss some implications of this result for the QMA\mathsf{QMA}QMA search-to-decision problem and unitary synthesis.
Recent works have demonstrated that quantum oracles have subtle behavior, as access to inverse, conjugate or controlled queries can exponentially change the query complexity of certain tasks. Inspired by these works, we introduce the notion of meta-complexity of quantum relativization. We ask: for any two quantum complexity classes, under which "types" of quantum oracles are they equal or separated? Different pantheons of oracles (or quantum oracle types, e.g. unitary vs state, poly- vs superpoly-dimensional, closed under inverse or not) form a partially ordered set based on their power in separating complexity classes. Moreover, two oracle pantheons A and B are separated if there exists a pair of complexity classes that are separated under an oracle from pantheon A but yet the complexity classes are equivalent under all oracles from pantheon B. We show that this meta-complexity can be nontrivial by giving a complete classification, within the family of oracle pantheons defined in this paper, of which models can separate the complexity classes PostBQP\mathsf{PostBQP}PostBQP and PreciseBQP\mathsf{PreciseBQP}PreciseBQP, the exponentially precise variant of BQP\mathsf{BQP}BQP. Both classes equal PP\mathsf{PP}PP in the unrelativized setting. Within our taxonomy, they remain equal relative to real or polynomial-dimensional unitary oracles and whenever inverse or conjugate access is supplied. In contrast, we give a separation relative to forward-only complex diagonal unitaries of superpolynomial dimension, as well as a separation relative to single-qubit state-preparation oracles. We view this as a test case for the meta-complexity of oracles which underscores the subtlety inherent to the relativization of quantum complexity classes.
The analysis of quantum algorithms which query random, invertible permutations has been a long-standing challenge in cryptography. Many techniques which apply to random oracles fail, or are not known to generalize to this setting. As a result, foundational cryptographic constructions involving permutations often lack quantum security proofs. With the aim of closing this gap, we develop and prove soundness of a compressed permutation oracle. Our construction shares many of the attractive features of Zhandry's original compressed function oracle: the purification is a small list of input-output pairs which meaningfully reflect an algorithm's knowledge of the oracle.
In the quantum state distinguishing problem, an algorithm is given copies of a state ∣ψ⟩|ψ\rangle∣ψ⟩ or ∣φ⟩|φ\rangle∣φ⟩ separated by trace distance ε\varepsilonε, and tasked with deciding which is the case. It is a standard result that Θ(ε−2)Θ(\varepsilon^{-2})Θ(ε−2) copies are required, while having access to a unitary state preparation oracle and its inverse improves this to Θ(ε−1)Θ(\varepsilon^{-1})Θ(ε−1) queries. We study the intermediate case with forward-only access, capturing scenarios where the oracle is a physical process that cannot be reversed. Tang and Wright recently showed that distinguishing a known state from an \emph{unknown} close state requires Ω(ε−2)Ω(\varepsilon^{-2})Ω(ε−2) forward queries in high dimension; we strengthen this result by proving the same bound even when both states are known, as in the state distinguishing setting. Moreover, our lower bound uses a direct hybrid argument, avoiding advanced compressed oracle techniques used in the prior work. In contrast, we give a dimension-independent algorithm solving a continuous-time variant of state distinguishing with only O(ε−1)O(\varepsilon^{-1})O(ε−1) total forward evolution time. The algorithm uses quantum Zeno dynamics to confine evolution to a known two-dimensional subspace. Thus, a quadratic advantage survives without inverse access for a natural continuous-time analogue of state distinguishing.