I oraklet identifieringsproblem, vi ges oraklet tillgång till en okänd N -bit sträng x lovade att tillhöra en känd uppsättning C i storlek M och vår uppgift är att identifiera x. Vi presenterar en kvantalgoritm för problemet som är optimal i sitt beroende av N och M. Vår algoritm förenklar och förbättrar avsevärt den tidigare bästa algoritmen på grund av Ambainis et al. Vår algoritm har också tillämpningar i kvantlärande teori, där det förbättrar komplexiteten i exakt lärande med medlemskap frågor, lösa en gissning om Hunziker et al. Algoritmen bygger på idéer från klassisk inlärningsteori och en ny kompositionsteorem för lösningar av det filtrerade γ 2-norm semidefinite programmet, som kännetecknar kvantförfrågans komplexitet. Vår komposition teorem är ganska allmänt och tillåter oss att komponera kvantalgoritmer med input-beroende frågekomplex utan att ådra sig en logaritmisk overhead för felreduktion. Som en tillämpning av kompositionsteoremet, tar vi bort alla loggfaktorer från den mest kända kvantalgoritmen för Boolesk matris multiplikation.
Vår Algoritm 11 är mycket lik Kothari algoritm för oraklet identifiering problem REF, och vi hänvisar till hans analys av frågan komplexitet i vårt arbete.
An optimal quantum algorithm for the oracle identification problem
{'venue': 'Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), Leibniz International Proceedings in Informatics 25, pp. 482-493 (2014)', 'journal': None, 'mag_field_of_study': ['Physics', 'Computer Science']}