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:1502.02174 · Leibniz international proceedings in informatics

Oracles with Costs

Shelby Kimmel, Cedric Yen-Yu Lin, Han-Hsuan Lin

Published Jan 1, 2015• 4 citations
arXivHTMLPDF

Abstract

While powerful tools have been developed to analyze quantum query complexity, there are still many natural problems that do not fit neatly into the black box model of oracles. We create a new model that allows multiple oracles with differing costs. This model captures more of the difficulty of certain natural problems. We test this model on a simple problem, Search with Two Oracles, for which we create a quantum algorithm that we prove is asymptotically optimal. We further give some evidence, using a geometric picture of Grover's algorithm, that our algorithm is exactly optimal.

DOI
10.4230/lipics.tqc.2015.1

Related papers

Oracles with Costs

Shelby Kimmel, Cedric Yen-Yu Lin, Han-Hsuan Lin

While powerful tools have been developed to analyze quantum query complexity, there are still many natural problems that do not fit neatly into the black box model of oracles. We create a new model that allows multiple oracles with differing costs. This model captures more of the difficulty of certain natural problems. We test this model on a simple problem, Search with Two Oracles, for which we create a quantum algorithm that we prove is asymptotically optimal. We further give some evidence, using a geometric picture of Grover's algorithm, that our algorithm is exactly optimal.

Conference on Theory of Quantum Computation, Communication and Cryptography•Feb 1, 2015•0 citations

Exact quantum lower bound for Grover's problem

Catalin Dohotaru, Peter Høyer

One of the most important quantum algorithms ever discovered is Grover's algorithm for searching an unordered set. We give a new lower bound in the query model which proves that Grover's algorithm is exactly optimal. Similar to existing methods for proving lower bounds, we bound the amount of information we can gain from a single oracle query, but we bound this information in terms of angles. This allows our proof to be simple, self-contained, based on only elementary mathematics, capturing our intuition, while obtaining at the same time an exact bound.

arXiv:0810.3647•Quantum Information and Computation•May 1, 2009•16 citations

Quantum Query Complexity for Nonstandard Oracles with Tight Bounds and Tradeoffs Beyond Grover

Yalla Jnan Devi Satya Prasad

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.

•Dec 19, 2025•0 citations

Robust Quantum Algorithms for Oracle Identification

Andris Ambainis, Kazuo Iwama, Akinori Kawachi +2 more

The oracle identification problem (OIP) was introduced by Ambainis et al. \cite{AIKMRY04}. It is given as a set $S$ of $M$ oracles and a blackbox oracle $f$. Our task is to figure out which oracle in $S$ is equal to the blackbox $f$ by making queries to $f$. OIP includes several problems such as the Grover Search as special cases. In this paper, we improve the algorithms in \cite{AIKMRY04} by providing a mostly optimal upper bound of query complexity for this problem: ($i$) For any oracle set $S$ such that $|S| \le 2^{N^d}$ ($d < 1$), we design an algorithm whose query complexity is $O(\sqrt{N\log{M}/\log{N}})$, matching the lower bound proved in \cite{AIKMRY04}. ($ii$) Our algorithm also works for the range between $2^{N^d}$ and $2^{N/\log{N}}$ (where the bound becomes O(N)), but the gap between the upper and lower bounds worsens gradually. ($iii$) Our algorithm is robust, namely, it exhibits the same performance (up to a constant factor) against the noisy oracles as also shown in the literatures \cite{AC02,BNRW03,HMW03} for special cases of OIP.

arXiv:quant-ph/0411204•IPSJ SIG Notes•Nov 30, 2004•18 citations

Test-state approach to the quantum search problem

Arun Sehrawat, Le Huy Nguyen, Berthold‐Georg Englert

The search for ``a quantum needle in a quantum haystack'' is a metaphor for the problem of finding out which one of a permissible set of unitary mappings---the oracles---is implemented by a given black box. Grover's algorithm solves this problem with quadratic speedup as compared with the analogous search for ``a classical needle in a classical haystack.'' Since the outcome of Grover's algorithm is probabilistic---it gives the correct answer with high probability, not with certainty---the answer requires verification. For this purpose we introduce specific test states, one for each oracle. These test states can also be used to realize ``a classical search for the quantum needle'' which is deterministic---it always gives a definite answer after a finite number of steps---and 3.41 times as fast as the purely classical search. Since the test-state search and Grover's algorithm look for the same quantum needle, the average number of oracle queries of the test-state search is the classical benchmark for Grover's algorithm.

arXiv:1102.3628•Physical Review A•May 17, 2011•5 citations

Quantum Query Complexity for List Search

Niranka Banerjee, Akinori Kawachi

Searching in a linked list is one of the most basic problems in classical algorithms. Although the nodes of the list come with memory addresses, classically those addresses play no role in the cost of search: one simply starts at the head and follows successor pointers to search for an element. In this paper, we show that the quantum setting is different. Here, the ambient address space from which the list vertices are drawn can itself affect the query complexity. We study the following problem analogous to search in a linked list in the query complexity model: the input consists of an address universe $[N]$, a public start symbol $s$, a successor oracle $f$ whose non-$\perp$ values trace a hidden simple path $s \to a_1 \to a_2 \to \cdots \to a_\ell \to \perp$, and a marking oracle $g$ that marks at most one list vertex. The task is to decide whether the list contains a marked vertex. We prove that both the decision and search versions of this problem for all $N \ge \ell \ge 1$ have quantum query complexity $Θ\!\bigl(\min\{\ell,(N\ell)^{1/4}\}\bigr)$. Thus, quite surprisingly, when $N < \ell^3$ the optimal quantum complexity is $(N\ell)^{1/4}$, which is strictly smaller than the $Θ(\ell)$ cost of ordinary linked-list traversal. This gives a precise characterization of when the ambient address space yields a genuine quantum advantage for linked-list search. We extend our results and give the same tight asymptotic bounds for the natural double linked-list version as well.

quant-pharXiv:2609.38736•Oct 1, 2026•0 citations
While powerful tools have been developed to analyze quantum query complexity, there are still many natural problems that do not fit neatly into the black box model of oracles. We create a new model that allows multiple oracles with differing costs. This model captures more of the difficulty of certain natural problems. We test this model on a simple problem, Search with Two Oracles, for which we create a quantum algorithm that we prove is asymptotically optimal. We further give some evidence, using a geometric picture of Grover's algorithm, that our algorithm is exactly optimal.
While powerful tools have been developed to analyze quantum query complexity, there are still many natural problems that do not fit neatly into the black box model of oracles. We create a new model that allows multiple oracles with differing costs. This model captures more of the difficulty of certain natural problems. We test this model on a simple problem, Search with Two Oracles, for which we create a quantum algorithm that we prove is asymptotically optimal. We further give some evidence, using a geometric picture of Grover's algorithm, that our algorithm is exactly optimal.
One of the most important quantum algorithms ever discovered is Grover's algorithm for searching an unordered set. We give a new lower bound in the query model which proves that Grover's algorithm is exactly optimal. Similar to existing methods for proving lower bounds, we bound the amount of information we can gain from a single oracle query, but we bound this information in terms of angles. This allows our proof to be simple, self-contained, based on only elementary mathematics, capturing our intuition, while obtaining at the same time an exact bound.
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 oracle identification problem (OIP) was introduced by Ambainis et al. \cite{AIKMRY04}. It is given as a set SSS of MMM oracles and a blackbox oracle fff. Our task is to figure out which oracle in SSS is equal to the blackbox fff by making queries to fff. OIP includes several problems such as the Grover Search as special cases. In this paper, we improve the algorithms in \cite{AIKMRY04} by providing a mostly optimal upper bound of query complexity for this problem: (iii) For any oracle set SSS such that ∣S∣≤2Nd|S| \le 2^{N^d}∣S∣≤2Nd (d<1d < 1d<1), we design an algorithm whose query complexity is O(Nlog⁡M/log⁡N)O(\sqrt{N\log{M}/\log{N}})O(NlogM/logN​), matching the lower bound proved in \cite{AIKMRY04}. (iiiiii) Our algorithm also works for the range between 2Nd2^{N^d}2Nd and 2N/log⁡N2^{N/\log{N}}2N/logN (where the bound becomes O(N)), but the gap between the upper and lower bounds worsens gradually. (iiiiiiiii) Our algorithm is robust, namely, it exhibits the same performance (up to a constant factor) against the noisy oracles as also shown in the literatures \cite{AC02,BNRW03,HMW03} for special cases of OIP.
The search for ``a quantum needle in a quantum haystack'' is a metaphor for the problem of finding out which one of a permissible set of unitary mappings---the oracles---is implemented by a given black box. Grover's algorithm solves this problem with quadratic speedup as compared with the analogous search for ``a classical needle in a classical haystack.'' Since the outcome of Grover's algorithm is probabilistic---it gives the correct answer with high probability, not with certainty---the answer requires verification. For this purpose we introduce specific test states, one for each oracle. These test states can also be used to realize ``a classical search for the quantum needle'' which is deterministic---it always gives a definite answer after a finite number of steps---and 3.41 times as fast as the purely classical search. Since the test-state search and Grover's algorithm look for the same quantum needle, the average number of oracle queries of the test-state search is the classical benchmark for Grover's algorithm.
Searching in a linked list is one of the most basic problems in classical algorithms. Although the nodes of the list come with memory addresses, classically those addresses play no role in the cost of search: one simply starts at the head and follows successor pointers to search for an element. In this paper, we show that the quantum setting is different. Here, the ambient address space from which the list vertices are drawn can itself affect the query complexity. We study the following problem analogous to search in a linked list in the query complexity model: the input consists of an address universe [N][N][N], a public start symbol sss, a successor oracle fff whose non-⊥\perp⊥ values trace a hidden simple path s→a1→a2→⋯→aℓ→⊥s \to a_1 \to a_2 \to \cdots \to a_\ell \to \perps→a1​→a2​→⋯→aℓ​→⊥, and a marking oracle ggg that marks at most one list vertex. The task is to decide whether the list contains a marked vertex. We prove that both the decision and search versions of this problem for all N≥ℓ≥1N \ge \ell \ge 1N≥ℓ≥1 have quantum query complexity Θ ⁣(min⁡{ℓ,(Nℓ)1/4})Θ\!\bigl(\min\{\ell,(N\ell)^{1/4}\}\bigr)Θ(min{ℓ,(Nℓ)1/4}). Thus, quite surprisingly, when N<ℓ3N < \ell^3N<ℓ3 the optimal quantum complexity is (Nℓ)1/4(N\ell)^{1/4}(Nℓ)1/4, which is strictly smaller than the Θ(ℓ)Θ(\ell)Θ(ℓ) cost of ordinary linked-list traversal. This gives a precise characterization of when the ambient address space yields a genuine quantum advantage for linked-list search. We extend our results and give the same tight asymptotic bounds for the natural double linked-list version as well.