@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.
  }
}