2003/01/07 by Michael Nathanson, Nathanson, Michael
Physics and Astronomy · #FOS: Physical sciences #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/0301025
14 pages
arxiv created 2003/02/07 · arxiv updated 2009/12/01
We examine the "Guessing Secrets" problem arising in internet routing, in which the goal is to discover two or more objects from a known finite set. We propose a quantum algorithm using O(1) calls to an O(logN) oracle. This improves upon the best known classical result, which uses O(logN) questions and requires an additional O(logN3) steps to produce the answer. In showing the possibilities of this algorithm, we extend the types of questions and function oracles that the Deutsch-Jozsa algorithm can be used to solve.