Robust Quantum Algorithms for Oracle Identification

Simple item page
dc.creatorAmbainis, Andris
dc.creatorIwama, Kazuo
dc.creatorKawachi, Akinori
dc.creatorRaymond, Rudy
dc.creatorYamashita, Shigeru
dc.date2004-11-30
dc.date2006-04-18
dc.date.accessioned2026-07-07T06:40:48Z
dc.date.available2026-07-07T06:40:48Z
dc.descriptionThe 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.
dc.descriptionPresentation is improved
dc.identifierhttps://arxiv.org/abs/quant-ph/0411204
dc.identifierhttp://arxiv.org/abs/quant-ph/0411204
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/101492
dc.subjectQuantum Physics
dc.titleRobust Quantum Algorithms for Oracle Identification
dc.typetext

Files

Collections

arXiv