Quantum guessing via Deutsch-Jozsa
Michael H. Nathanson · Quantum Information and Computation · 2010
We examine the "Guessing Secrets" problem arising in internet routing, in which the goal is to discover the identity of two objects from a known finite set $\Omega$ by asking yes/no questions. The best known classical algorithm requires $O(\log N)$ questions and $O(\log^2 N)$ steps to process the answers, where $N = \vert \Omega \vert$. We apply the Deutsch-Jozsa algorithm and show that the number of necessary calls to the oracle is independent of the size of the domain and that the output from each run of the algorithm has immediate meaning. In doing so, we extend the types of questions that the quantum algorithms can be used to solve.