Quantum query complexity underpins much of our understanding of quantum speedups, yet nearly all existing lower and upper bounds are derived for simple Boolean oracles. Many practical tasks-noisy database search, stochastic optimization, adaptive learning, and time-varying systems-are best modeled by richer oracle classes. This paper systematically extends quantum query complexity theory to four non-standard oracle models: (1) stochastic oracles that return random outputs drawn from a distribution; (2) multi-solution oracles encoding a solution set of size k; (3) time-dependent oracles whose internal state evolves between queries; and (4) relational oracles encoding structured constraints rather than simple membership. Using generalized adversary methods, polynomial method techniques, and hybrid arguments, we derive tight (up to polylog factors) lower bounds for each model and construct matching algorithms where possible. For instance, we show that searching for any one of k marked items in an unstructured database still admits a Grover-like quadratic speedup, but with optimal complexity Θ(N/k), and that stochastic noise in oracle outputs degrades the advantage gracefully as a function of the noise parameter. For certain time-dependent and relational models, we prove that no better-than-classical speedup is possible, clarifying the limits of quantum advantage in adaptive settings. These results provide a more realistic foundation for quantum algorithms targeting noisy search, stochastic optimization, and constraint satisfaction, and they highlight the precise structural features that enable or preclude query-based quantum speedups.
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=fU 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∣x⟩=∣π(x)⟩, as well as random alternating-basis phase unitaries
F2⋅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⟩, 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.
We propose a generalization of Zhandry's compressed oracle method to random permutations, where an algorithm can query both the permutation and its inverse. We show how to use the resulting oracle simulation to bound the success probability of an algorithm for any predicate on input-output pairs, a key feature of Zhandry's technique that had hitherto resisted attempts at generalization to random permutations. One key technical ingredient is to use strictly monotone factorizations to represent the permutation in the oracle's database. As an application of our framework, we show that the one-round sponge construction is unconditionally preimage resistant in the random permutation model. This proves a conjecture by Unruh.
We study a longstanding question of Aaronson and Kuperberg on whether there exists a classical oracle separating
QMA from
QCMA. Settling this question in either direction would yield insight into the power of quantum proofs over classical proofs. We show that such an oracle exists if a certain quantum pseudorandomness conjecture holds. Roughly speaking, the conjecture posits that quantum algorithms cannot, by making few queries, distinguish between the uniform distribution over permutations versus permutations drawn from so-called "dense" distributions. Our result can be viewed as establishing a "win-win" scenario: either there is a classical oracle separation of
QMA from
QCMA, or there is quantum advantage in distinguishing pseudorandom distributions on permutations.
We study the query complexity of quantum learning problems in which the oracles form a group G of unitary matrices. In the simplest case, one wishes to identify the oracle, and we find a description of the optimal success probability of a t -query quantum algorithm in terms of group characters. As an application, we show that Ω(n) queries are required to identify a random permutation in Sn . More generally, suppose H is a fixed subgroup of the group G of oracles, and given access to an oracle sampled uniformly from G , we want to learn which coset of H the oracle belongs to. We call this problem coset identification and it generalizes a number of well-known quantum algorithms including the Bernstein-Vazirani problem, the van Dam problem and finite field polynomial interpolation. We provide character-theoretic formulas for the optimal success probability achieved by a t -query algorithm for this problem. One application involves the Heisenberg group and provides a family of problems depending on n which require n+1 queries classically and only 1 query quantumly.
This paper investigates the impact of noise in the quantum query model, a fundamental framework for quantum algorithms. We focus on the scenario where the oracle is subject to non-unitary (or irreversible) noise, specifically under the \textit{faulty oracle} model, where the oracle fails with a constant probability and acts as identity. Regev and Schiff (ICALP'08) showed that quantum advantage is lost for the search problem under this noise model. Our main result shows that every quantum query algorithm can be made robust in this noise model with a roughly quadratic blow-up in query complexity, thereby preserving quantum speedup for all problems where the quantum advantage is super-cubic. This is the first non-trivial robustification of quantum query algorithms against an oracle that is noisy.