mlsanityData to 14 Oct 2026

Simplified Quantum Algorithm for the Oracle Identification Problem

arXiv 2109.03902 ↗First posted 8 Sep 2021quant-ph cs.CC cs.LGcited by 0

Not on the map. Why?

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.

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

2 of 11 references.

References · 2

  1. 2019Quantum Speedup Based on Classical Decision Treescited by 3
  2. 2013Easy and hard functions for the Boolean hidden shift problemcited by 1

Built on by

Not cited yet.