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

数理解析研究所講究録

Robust Quantum Algorithms for Oracle Identification (Theoretical Computer Science and its Applications)

Kazuo Iwama, Akinori Kawachi, Rudy Raymond, Shigeru Yamashita

Published Apr 1, 2005• 0 citations
OpenAlex

Abstract

The oracle identification problem (OIP) was introduced by Ambainis et.al. [4], which is given as a set $S$ of $M$ oracles and a hidden oracle $f$ .Our task is to figure out which oracle in $S$ is equal to the hidden $f$ by doing queries to $f$ .OIP includes several problems such as Grover Search as special cases.In this paper, we design robust algorithms, i.e., those which are tolerant against noisy oracles, for OIP.Our results include: (i) For any oracle set $S$ such that $|S|$ is polynomial in $N$ , $O(\sqrt{N})$ queries are enough to identify the hidden oracle, which is obviously optimal since this OIP includes Grover Search as a special case, (ii) For the case that $|S|\leq 2^{N^{d}}(d<1)$ , we design an algorithm whose query complexity is $O(\sqrt{N\log M/\log N})$ and matches the lower bound proved in [4].(Hi) We can furthermore design a robust algorithm whose complexity changes smoothly between the complexity of (ii) and the complexity of recovering all information about the hidden oracle whose complexity is $O(N)$ as showed by Buhrman et.al. in [11].Thus our new algorithms are not only robust but also their query complexities are even better than the previous noiseless case [4],

Related papers

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

An optimal quantum algorithm for the oracle identification problem

Robin Kothari

In the oracle identification problem, we are given oracle access to an unknown N-bit string x promised to belong to a known set C of size M and our task is to identify x. We present a quantum algorithm for the problem that is optimal in its dependence on N and M. Our algorithm considerably simplifies and improves the previous best algorithm due to Ambainis et al. Our algorithm also has applications in quantum learning theory, where it improves the complexity of exact learning with membership queries, resolving a conjecture of Hunziker et al. The algorithm is based on ideas from classical learning theory and a new composition theorem for solutions of the filtered $γ_2$-norm semidefinite program, which characterizes quantum query complexity. Our composition theorem is quite general and allows us to compose quantum algorithms with input-dependent query complexities without incurring a logarithmic overhead for error reduction. As an application of the composition theorem, we remove all log factors from the best known quantum algorithm for Boolean matrix multiplication.

arXiv:1311.7685•Leibniz international proceedings in informatics•Nov 29, 2013•20 citations

Efficient algorithms in quantum query complexity

Robin Kothari

In this thesis we provide new upper and lower bounds on the quantum query complexity of a diverse set of problems. Specifically, we study quantum algorithms for Hamiltonian simulation, matrix multiplication, oracle identification, and graph-property recognition. \n \nFor the Hamiltonian simulation problem, we provide a quantum algorithm with query complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Our algorithm is based on a new quantum algorithm for implementing unitary matrices that can be written as linear combinations of efficiently implementable unitary gates. This algorithm uses a new form of ``oblivious amplitude amplification'' that can be applied even though the reflection about the input state is unavailable. \n \nIn the oracle identification problem, we are given oracle access to an unknown N-bit string x promised to belong to a known set of size M, and our task is to identify x. We present the first quantum algorithm for the problem that is optimal in its dependence on N and M. Our algorithm is based on ideas from classical learning theory and a new composition theorem for solutions of the filtered gamma_2-norm semidefinite program. \n \nWe then study the quantum query complexity of matrix multiplication and related problems over rings, semirings, and the Boolean semiring in particular. Our main result is an output-sensitive algorithm for Boolean matrix multiplication that multiplies two n x n Boolean matrices with query complexity O(n sqrt{l}), where l is the sparsity of the output matrix. The algorithm is based on a reduction to the graph collision problem and a new algorithm for graph collision. \n \nFinally, we study the quantum query complexity of minor-closed graph properties and show that most minor-closed properties---those that cannot be characterized by a finite set of forbidden subgraphs---have quantum query complexity Theta(n^{3/2}) and those that do have such a characterization can be solved strictly faster, with o(n^{3/2}) queries. Our lower bound is based on a detailed analysis of the structure of minor-closed properties with respect to forbidden topological minors and forbidden subgraphs. Our algorithms are a novel application of the quantum walk search framework and give improved upper bounds for several subgraph-finding problems.

•Aug 13, 2014•20 citations

Geometric Characterization of Quantum Oracle Identification(New Trends in Theory of Computation and Algorithm)

Akinori Kawachi, Shigeru Yamashita

We geometrically characterize the query complexity of the oracle identification prob- lem in this paper.By defining an inner product between two oracles, we construct a quantum algo- rithm, which generalizes Bemstein-Vazirani and Grover algorithms, for a certain class of the oracle identification problem characterized by the inner product.We also show the optimality of this quantum algorithm.

数理解析研究所講究録•May 1, 2006•0 citations

Approximate Degree Lower Bounds for Oracle Identification Problems

Mark Bun, Nadiia Voronova

The approximate degree of a Boolean function is the minimum degree of real polynomial that approximates it pointwise. For any Boolean function, its approximate degree serves as a lower bound on its quantum query complexity, and generically lifts to a quantum communication lower bound for a related function. We introduce a framework for proving approximate degree lower bounds for certain oracle identification problems, where the goal is to recover a hidden binary string $x \in \{0, 1\}^n$ given possibly non-standard oracle access to it. Our lower bounds apply to decision versions of these problems, where the goal is to compute the parity of $x$. We apply our framework to the ordered search and hidden string problems, proving nearly tight approximate degree lower bounds of $Ω(n/\log^2 n)$ for each. These lower bounds generalize to the weakly unbounded error setting, giving a new quantum query lower bound for the hidden string problem in this regime. Our lower bounds are driven by randomized communication upper bounds for the greater-than and equality functions.

arXiv:2303.03921•Leibniz international proceedings in informatics•Jan 1, 2023•0 citations

Quantum query complexity of symmetric oracle problems

Daniel Copeland, Jamie Pommersheim

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.

arXiv:1812.09428•Quantum•Mar 7, 2021•1 citation
The oracle identification problem (OIP) was introduced by Ambainis et.al. [4], which is given as a set SSS of MMM oracles and a hidden oracle fff .Our task is to figure out which oracle in SSS is equal to the hidden fff by doing queries to fff .OIP includes several problems such as Grover Search as special cases.In this paper, we design robust algorithms, i.e., those which are tolerant against noisy oracles, for OIP.Our results include: (i) For any oracle set SSS such that ∣S∣|S|∣S∣ is polynomial in NNN , O(N)O(\sqrt{N})O(N​) queries are enough to identify the hidden oracle, which is obviously optimal since this OIP includes Grover Search as a special case, (ii) For the case that ∣S∣≤2Nd(d<1)|S|\leq 2^{N^{d}}(d<1)∣S∣≤2Nd(d<1) , we design an algorithm whose query complexity is O(Nlog⁡M/log⁡N)O(\sqrt{N\log M/\log N})O(NlogM/logN​) and matches the lower bound proved in [4].(Hi) We can furthermore design a robust algorithm whose complexity changes smoothly between the complexity of (ii) and the complexity of recovering all information about the hidden oracle whose complexity is O(N)O(N)O(N) as showed by Buhrman et.al. in [11].Thus our new algorithms are not only robust but also their query complexities are even better than the previous noiseless case [4],
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.
In the oracle identification problem, we are given oracle access to an unknown N-bit string x promised to belong to a known set C of size M and our task is to identify x. We present a quantum algorithm for the problem that is optimal in its dependence on N and M. Our algorithm considerably simplifies and improves the previous best algorithm due to Ambainis et al. Our algorithm also has applications in quantum learning theory, where it improves the complexity of exact learning with membership queries, resolving a conjecture of Hunziker et al. The algorithm is based on ideas from classical learning theory and a new composition theorem for solutions of the filtered γ2γ_2γ2​-norm semidefinite program, which characterizes quantum query complexity. Our composition theorem is quite general and allows us to compose quantum algorithms with input-dependent query complexities without incurring a logarithmic overhead for error reduction. As an application of the composition theorem, we remove all log factors from the best known quantum algorithm for Boolean matrix multiplication.
In this thesis we provide new upper and lower bounds on the quantum query complexity of a diverse set of problems. Specifically, we study quantum algorithms for Hamiltonian simulation, matrix multiplication, oracle identification, and graph-property recognition. \n \nFor the Hamiltonian simulation problem, we provide a quantum algorithm with query complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Our algorithm is based on a new quantum algorithm for implementing unitary matrices that can be written as linear combinations of efficiently implementable unitary gates. This algorithm uses a new form of ``oblivious amplitude amplification'' that can be applied even though the reflection about the input state is unavailable. \n \nIn the oracle identification problem, we are given oracle access to an unknown N-bit string x promised to belong to a known set of size M, and our task is to identify x. We present the first quantum algorithm for the problem that is optimal in its dependence on N and M. Our algorithm is based on ideas from classical learning theory and a new composition theorem for solutions of the filtered gamma_2-norm semidefinite program. \n \nWe then study the quantum query complexity of matrix multiplication and related problems over rings, semirings, and the Boolean semiring in particular. Our main result is an output-sensitive algorithm for Boolean matrix multiplication that multiplies two n x n Boolean matrices with query complexity O(n sqrt{l}), where l is the sparsity of the output matrix. The algorithm is based on a reduction to the graph collision problem and a new algorithm for graph collision. \n \nFinally, we study the quantum query complexity of minor-closed graph properties and show that most minor-closed properties---those that cannot be characterized by a finite set of forbidden subgraphs---have quantum query complexity Theta(n^{3/2}) and those that do have such a characterization can be solved strictly faster, with o(n^{3/2}) queries. Our lower bound is based on a detailed analysis of the structure of minor-closed properties with respect to forbidden topological minors and forbidden subgraphs. Our algorithms are a novel application of the quantum walk search framework and give improved upper bounds for several subgraph-finding problems.
The approximate degree of a Boolean function is the minimum degree of real polynomial that approximates it pointwise. For any Boolean function, its approximate degree serves as a lower bound on its quantum query complexity, and generically lifts to a quantum communication lower bound for a related function. We introduce a framework for proving approximate degree lower bounds for certain oracle identification problems, where the goal is to recover a hidden binary string x∈{0,1}nx \in \{0, 1\}^nx∈{0,1}n given possibly non-standard oracle access to it. Our lower bounds apply to decision versions of these problems, where the goal is to compute the parity of xxx. We apply our framework to the ordered search and hidden string problems, proving nearly tight approximate degree lower bounds of Ω(n/log⁡2n)Ω(n/\log^2 n)Ω(n/log2n) for each. These lower bounds generalize to the weakly unbounded error setting, giving a new quantum query lower bound for the hidden string problem in this regime. Our lower bounds are driven by randomized communication upper bounds for the greater-than and equality functions.
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.