Quantum Oracle Interrogation: Getting all information for almost half the price

Preprint
Publisher Website
Google Scholar
Abstract
A quantum computer in combination with a binary oracle of domain size N is considered. It is shown how N/2+sqrt(N) calls to the oracle are sufficient to guess the whole content of the oracle (being an N bit string) with probability greater than 85%. This contrasts the power of classical computers which would require N calls to achieve the same result. From this result it follows that any binary function with the N bits of the oracle as input, can be calculated with a small 2 sided error using N/2+sqrt(N) queries.

This publication has 0 references indexed in Scilit: