Any classical comparison-based algorithm for searching an ordered list of N items requires at least log_2(N) comparisons. The celebrated binary search algorithm meets this bound and its behavior can be illustrated by a binary tree. Each node of the tree is labelled by a comparison, and each leaf by one of the N items. Initially, the state of the algorithm is represented by the root of the tree, and at each step of the algorithm, a comparison determines whether we go to the left or right child. Eventually, the walk ends at a leaf that represents the result of the algorithm.

We give a quantum version of this classical binary search algorithm. The quantum algorithm initiates several independent walks at the root, each walk advancing down the tree at its own speed. Then, instead of having each walk advancing only (at most) 1 edge at each step as classically, we give a routine that allows the walks to cooperate. Two walks that are at neighboring nodes (which must be in a parent-child relation) can, by cooperating, jump simultaneously to the same child, hereby advancing 1 and 2 edges, respectively. Having a routine that allows 1 walk to advance 1 edge, while another walk advances 2 edges, gives an average advance of 1.5 edge, intuitively yielding a better-than log_2(N) quantum algorithm for ordered searching.

In this talk, I will introduce to quantum computing and give a simple log_3(N) quantum algorithm based on the above ideas. The currently best known upper bound for ordered searching on a quantum computer is roughly 0.526 * log_2(N), due to Farhi, Goldstone, Gutmann, and Sipser. I will also briefly sketch how to prove the currently best known lower bound of 1/pi * (ln(N)-1).

No familiarity with quantum computation is assumed. Students interested in writing their master thesis or dissertation in (an area related to) quantum computing are most welcome.

Joint work with Jan Neerbek, BRICS.

Host: Jacob Hjelmborg