@techreport{TR-IC-10-03,
number = {IC-10-03},
author = {Nilton Volpato and Arnaldo Moura},
title = {A fast quantum algorithm for the closest bichromatic pair
problem},
month = {January},
year = {2010},
institution = {Institute of Computing, University of Campinas},
note = {In English, 9 pages.
\par\selectlanguage{english}\textbf{Abstract}
We present an algorithm for solving the two-color
\textit{bichromatic closest pair} problem using $O(N^{1/2}
M^{1/4} \log M \log N)$ queries if $N \leq M \leq N^2$, or
$O(M^{1/2} \log^2 N)$ if $M > N^2$. This result contrasts with
the classical probabilistic time complexity of $O((N M \log N
\log M)^{2/3} + M \log^2 N + N \log^2 M)$. We also show how to
solve the \textit{closest pair} problem---that is a special
case of the \textit{bichromatic closest pair} problem---using
$O(N^{3/4} \log^2 N)$ queries. And, we also show a quantum
lower bound of $\Omega(N^{2/3})$ queries for this problem, and
discuss some open issues.
}
}