1998/05/31 by Wim van Dam, W. van Dam · 1 citation
Computer Science · Physics and Astronomy · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #cs.CC #quant-ph
paper · pdf · doi:10.1109/sfcs.1998.743486
published as Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 362-367 (1998) · 11 pages LaTeX2e, 1 postscript figure; error analysis added; new section on approximate interrogation added
arxiv created 1998/09/11 · openalex publication_date 2002/11/27 · arxiv updated 2009/11/30 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/29
Consider a quantum computer in combination with a binary oracle of domain size N. It is shown how N/2+/spl radic/N calls to the oracle are sufficient to guess the whole content of the oracle (being an N bit string) with probability greater than 95%. This contrasts the power of classical computers which would require N calls to achieve the same task. From this result it follows that any function with the N bits of the oracle as input can be calculated using N/2+/spl radic/N queries if we allow a small probability of error. It is also shown that this error probability can be made arbitrary small by using N/2+O(/spl radic/N) oracle queries. In the second part of the article 'approximate interrogation' is considered. This is when only a certain fraction of the N oracle bits are requested. Also for this scenario does the quantum algorithm outperform the classical protocols. An example is given where a quantum procedure with N/10 queries returns a string of which 80% of the bits are correct. Any classical protocol would need 6N/10 queries to establish such a correctness ratio.