Seminário de Computação e Informação Quântica 

18/05/2007, 15:00 — 16:00 — Sala P4.35, Pavilhão de Matemática
Anthony Chefles, Hewlett-Packard Laboratories, Bristol

Unambiguous discrimination among oracle operators

Oracle operators are unitary operators which are used to coherently compute functions. We investigate the problem of unambiguous discrimination among oracle operators for two oracle models: the standard and minimal (or erasing) oracles, where the latter can only be constructed for invertible functions. It is found that the unambiguous distinguishability criterion is the same for both models, and depends only on pairwise relationships between the functions. We show that, except in certain trivial cases, it is impossible to unambiguously discriminate among all standard oracle operators corresponding to integer functions with fixed domain and range. We also find that it is possible to unambiguously discriminate among the Grover oracle operators corresponding to an arbitrarily large unsorted database, which cannot be achieved deterministically. The unambiguous distinguishability of standard oracle operators corresponding to totally indistinguishable functions is analysed in detail. For such functions, there is zero classical discrimination probability even with a memory of the independent variable and the result of the function computation. There must be at least four functions in such a set. Using a graph-theoretic framework, we prove that the standard oracle operators are not unambiguously distinguishable for any finite set of totally indistinguishable functions on a Boolean domain and with fixed range. Finite sets of such functions on a larger domain can, however, have unambiguously distinguishable standard oracle operators. We provide a complete description of sets of four functions with this property. We also examine the possibility of unambiguous oracle operator discrimination with multiple parallel calls, and provide sufficient conditions for this to be possible.