# Simplified Quantum Algorithm for the Oracle Identification Problem

arXiv: https://arxiv.org/abs/2109.03902 · HTML: https://mlsanity.com/paper/2109.03902/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 2 of its 11 references that are in the map.
- First posted on arXiv 8 Sep 2021.

## Builds on (most cited first, 2 of 2)

- [Quantum Speedup Based on Classical Decision Trees](https://mlsanity.com/paper/1905.13095/) (2019)
- [Easy and hard functions for the Boolean hidden shift problem](https://mlsanity.com/paper/1304.4642/) (2013)

## Abstract (arXiv)

In the oracle identification problem we have oracle access to bits of an unknown string x of length n, with the promise that it belongs to a known set Csubseteq0,1n. The goal is to identify x using as few queries to the oracle as possible. We develop a quantum query algorithm for this problem with query complexity Oleft(√fracnlog M log(n/log M)+1right), where M is the size of C. This bound is already derived by Kothari in 2014, for which we provide a more elegant simpler proof.