Modified Grover's search algorithm in $O(M+\log N)$ steps
The present letter proposes a modification in the well known Grover's search algorithm, which searches a database of $N$ unsorted items in $O(\sqrt{N/M})$ steps, where $M$ represents the number of solutions to the search problem. Concurrency control techniques and extra registers for marking and storing the solutions are used in the modified algorithm. This requires additional space but it is shown that the use of extra register and marking techniques can reduce the time complexity to $O(M+\log N)$.
quant-ph0506093.tex
%% LyX 1.3 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[english]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
%% Bold symbol macro for standard LaTeX users
\newcommand{\boldsymbol}[1]{\mbox{\boldmath $#1$}}


\usepackage{babel}
\makeatother
\begin{document}

\title{Modified Grover's search algorithm in $O(M+\log N)$ steps }

\maketitle
\begin{center}Abhishek S Gupta%
\footnote{acmabhi@rediffmail.com%
}, Anirban Pathak%
\footnote{anirban.pathak@jiit.ac.in%
}\end{center}

\begin{center}Jaypee Institute of Information Technology, A-10, Sector
62, Noida-201307, India \end{center}

\begin{abstract}
The present letter proposes a modification in the well known Grover's
search algorithm, which searches a database of $N$ unsorted items
in $O(\sqrt{N/M})$ steps, where $M$ represents the number of solutions
to the search problem. Concurrency control techniques and extra registers
for marking and storing the solutions are used in the modified algorithm.
This requires additional space but it is shown that the use of extra
register and marking techniques can reduce the time complexity to
$O(M+\log N)$. 
\end{abstract}

\section{Introduction }

Searching databases is one of the most important problem in computer
science and real life. This fact has motivated people to develop a
large number of algorithms {[}\ref{the:search algos}{]} to search
different kind of databases. We are interested about a database of
$N$ unsorted items, having $M$ solutions (where $M\ll N)$. Any
classical algorithm takes $O(N)$ steps to search such a database.
In recent past Grover {[}\ref{the:L.-K.-Grover,}{]} has proposed
a quantum algorithm for the same purpose but with a time complexity
$O(\sqrt{N/M})$ {[}\ref{the:L.-K.-Grover,}-\ref{the:M.A.-Nielsen-and}{]}.
Till now, the time complexity of the Grover's algorithm is minimum
among all the algorithms that are designed for the same purpose. Tight
bound on Grover searching has been studied by many people {[}\ref{the:tight bound}{]}
but it does not establish any tight bound on quantum search in general.
This fact has motivated us to explore the possibility of improvement.
For this purpose we have used a technique which is well known as marking
technique in classical computation.

Marking is a technique which either put a level on the target elements
or on the indices associated with the target element. This technique
is used widely in classical computation for various purposes. Quantum
analogue of the marking technique is also used by many people {[}\ref{Durr}-\ref{chen-diao}{]}.
For example we can note, that Durr {[}\ref{dur2}{]} and Chen {[}\ref{chen-diao}{]}
have used this technique for finding out minima and searching. In
this letter we have used this technique to mark the solution states
to a register of size $N$ and we have also used two additional registers
to store these marked states and the number of solutions to the search
query respectively. Essentially, this registers increases the resource
requirement but it considerably reduces the time complexity. The time
complexity of the proposed modified Grover's algorithm is only $O(M+\log N)$.
This is a considerable reduction, specially when $M$ is small and
$N$ is large.

In section 2 we briefly discuss Grover's algorithm. The modified algorithm,
its complexity and issues related to concurrency control are discussed
in section 3. Finally section 4 is devoted for conclusion.


\section{Grover's algorithm}

As we have already stated, we are interested to search a database
of $N$ unsorted items out of which $M$ are the solutions. In Grover's
search algorithm we assign an index to each element and search on
those indices. Now for our convenience if we assume that $N=2^{n}$
then we can store all the indices in $n$ qubits since the indices
varies from $0$ to $N-1$. A particular instance of the search problem
can conveniently be represented by a function $f$, which takes an
integer $x$, in the range $0$ to $N-1$. By definition, $f(x)=1$
if $x$ is a solution to the search problem and $f(x)=0$ if $x$
is not a solution to the search problem. 

Grovers algorithm uses an unitary operator as a quantum oracle which
flips the oracle qubit if $f(x)=1$. Essentially, the Oracle marks
the solutions to the search problem by shifting the phase of the solution.
The search oracle is applied only $O(\sqrt{N/M})$ times in order
to obtain a solution on a quantum computer. This is done in following
steps {[}\ref{the:M.A.-Nielsen-and}{]}:

\begin{enumerate}
\item The algorithm begins with a quantum register in the state $\left|0\right\rangle ^{\otimes n}$.
\item The Hadamard transform is used to put the register in a equal superposition
of $N=2^{n}$ states. This is how we used to prepare the input state
$|x>$ for the oracle.
\item A quantum subroutine, known as the Grover iteration is repeatedly
applied. The Grover iteration may be broken in following four steps:\\
a) Apply the oracle \\
b) Apply the Hadamard transformation on $n$ qubits \\
c) Perform a conditional phase shift on the computer, with every computational
basis state except $|0\rangle$ receiving a phase shift of $-1$\\
d) Apply the Hadamard transformation on $n$ qubits. 
\end{enumerate}

\section{Modified search algorithm }

The modified search algorithm requires additional space to carry out
marking and it starts with an initially unmarked additional register
T of size $N$. The marking technique and the register used here are
similar to that used in Durr's work {[}\ref{Durr}-\ref{dur2}{]}
for finding out minima. Therefore, T{[}j{]} represents a memory location
which is used for marking where $0\leq j\leq N-1$. Apart form the
register T we also need two other registers, one to store the number
of solutions to the search problem and the other to store the solution
of the search problem. Let us name these two registers as COUNT and
ANS respectively. In the modified algorithm the first two steps are
same. The modification appears only in Oracle which works as follows:\\
a) The input to the Oracle is $|x\rangle$ (obtained in Step 2)\\
b) For each x, such that $f(x)=1$ mark T {[}x{]} where $0\leq x\leq N-1.$\\
Thus, if T{[}j{]} is marked then j represents a solution to the search
problem. When T{[}j{]} is marked, it will act as a trigger and a process
to write j into ANS register will be spawn. Let this process be denoted
by P( j ). 

Now, we would like to note that the number of processes spawned is
equal to the number of solutions to the search problem i.e. $M$ and
all these $M$ processes (denoted by P (j) ) will compete with each
other to write j into the ANS register. Thus, some concurrency control
mechanism must exist to allocate resource ANS to these $M$ processes,
such that mutual exclusion exists. This is a well known problem in
classical computation and our registers are essentially classical,
so we can use existing standard concurrency control techniques {[}\ref{the:Concurrency-Control-and}{]}.
For example, we can use centralised cocurrency control technique {[}\ref{the:Concurrency-Control-and}{]}.
In this case, each process P(j), where T {[}j{]} is marked, will send
a request to Central Concurrency Controller (CCC) to write j into
the ANS register and increment COUNT register. Although CCC will initially
be flooded with M requests (since M solutions exist).

Any arbitrary process selection technique will work in our case. The
reason behind this is explained later. For example, if we want our
answers to be displayed in ascending order of index, then we have
to allocate higher priority to a process with lower index value (i.e.
j). 

As soon as a process finishes its job, it will inform the CCC that
it should select any other process that is waiting to use ANS and
COUNT registers. CCC will then select another waiting process (if
any) by using the same selection technique that it has used earlier.
Decentralised Concurreny Control techniques {[}\ref{the:William-Stallings,-Operating}{]}
can also be used for the same purpose. 

It is important to note that the presrcribed mechanism is free from
the common problems (like busy waiting, starvation, deadlock, process
failure etc.) of concurrency control schemes. Busy waiting would be
negligible in this case since the only tasks that each process P(j)
has is to write j into ANS register and give an increment in COUNT
register. In our case, irrespective of any selection technique used
in CCC, no process will starve indefinitely to use the ANS and COUNT
registers, since total no of process $M\ll N$. At most, it may happen
that due to a particular selection technique, a particular value of
index j will cause P(j) to access the registers after $M-1$ processes
which is trivial. The ANS and COUNT registers can be considered as
a single unit of shared resource since at a particular time, a particular
process is either allowed to access both of them or not allowed to
access any of them. Therefore, only one unit of shared resource exist
and a deadlock will never happen in this situation. Process failure
is a serious problem but the chance of process failure is very very
low. In the worst case, one may have to run the algorithm multiple
times to ensure correctness. 

As far as data structure is concerned we have two options regarding
the structure in which j is written on ANS: If we use a single register
the register contents will probably change too rapidly for human perception.
To correct this problem, we can allow a user input in the concurrency
control mechanism which dictates when the register contents can change.
On the other hand if we use N registers then the process P(j) writes
j at that register whose index is represented by COUNT. Thus, no user
input is required in this case and hence, it will be faster than the
single register case. 


\section{Conclusion}

In the modified algorithm step 1 requires $O(logN)$ time and step
3 requires $O(M)$ time, assuming that each process P(j) requires
$O(1)$ time to complete its task. Thus, the total time required would
be $O(M+logN)$. Thus we have a modified version of the existing Grover's
algorithm having a considerably reduced time complexity. There is
one more important point, Grover's iterations yield all solutions
but as soon as we do a measurement the wave function collapses to
a particular state, so we end up with only one solution. But in the
present scheme we have all the solutions in hand. If in a particular
case we decide to note only one solution then our algorithm's time
complexity will reduce to $O(logN).$ Since, there exists many applications
of Grover algorithm, the improvement acheived in the present work
opens up the possibility of improvement in all these applications.

\begin{thebibliography}{1}
\bibitem{key-14}\label{the:search algos} T. H. Cormen, C. E. Leiserson, R. L. Rivest,
C. Stein, \emph{Introduction to Algorithms}, MIT Cambridge (2001).
\bibitem{key-4}\label{the:L.-K.-Grover,}L. K. Grover, \emph{A fast quantum mechanical
algorithm for database Search}, Proceedings, 28th Annual ACM Symposium
on the Theory of Computing (STOC), 212 (1996).
\bibitem{key-2}\label{the:M.A.-Nielsen-and}M. A. Nielsen and I. L. Chuang, \emph{Quantum
Computation and Quantum Information,} Cambridge University Press (2000).
\bibitem{key-15}\label{the:tight bound} M. Boyer, G. Brassard, P. Hoyer, A. Tapp,
\emph{Tight Bounds on Quantum Searching}, Fortschr. Physics \textbf{46}
493 (1998).
\bibitem{key-9}\label{Durr} C. Durr, M. Heiligman, P. Hoyer, M. Mhalla, \emph{Quantum
query complexity of some graph problems}, quant-ph/0401091.
\bibitem{key-11}\label{dur2} C. Durr, P. Hoyer, \emph{A quantum algorithm for finding
the minimum} quant-ph/9607014.
\bibitem{key-13}\label{chen-diao} G. Chen and Z. Diao, \emph{An exact quantum search
algorithm} www.math.tamu.edu/\textasciitilde{}zdiao/efs.pdf (2004).
\bibitem{key-17}\label{the:Concurrency-Control-and} P. A. Bernstein, V. Hadzilacos,
N. Goodman, \emph{Concurrency Control and recovery in database systems},
Addison-Wesley (1987).
\bibitem{key-7}\label{the:William-Stallings,-Operating}W. Stallings, \emph{Operating
Systems-Internals and Design Principles}, Prentice-Hall (2004).\end{thebibliography}

\end{document}

quant-ph0506093.extracted_bib
\begin{thebibliography}{1}
\bibitem{key-14}\label{the:search algos} T. H. Cormen, C. E. Leiserson, R. L. Rivest,
C. Stein, \emph{Introduction to Algorithms}, MIT Cambridge (2001).
\bibitem{key-4}\label{the:L.-K.-Grover,}L. K. Grover, \emph{A fast quantum mechanical
algorithm for database Search}, Proceedings, 28th Annual ACM Symposium
on the Theory of Computing (STOC), 212 (1996).
\bibitem{key-2}\label{the:M.A.-Nielsen-and}M. A. Nielsen and I. L. Chuang, \emph{Quantum
Computation and Quantum Information,} Cambridge University Press (2000).
\bibitem{key-15}\label{the:tight bound} M. Boyer, G. Brassard, P. Hoyer, A. Tapp,
\emph{Tight Bounds on Quantum Searching}, Fortschr. Physics \textbf{46}
493 (1998).
\bibitem{key-9}\label{Durr} C. Durr, M. Heiligman, P. Hoyer, M. Mhalla, \emph{Quantum
query complexity of some graph problems}, quant-ph/0401091.
\bibitem{key-11}\label{dur2} C. Durr, P. Hoyer, \emph{A quantum algorithm for finding
the minimum} quant-ph/9607014.
\bibitem{key-13}\label{chen-diao} G. Chen and Z. Diao, \emph{An exact quantum search
algorithm} www.math.tamu.edu/\textasciitilde{}zdiao/efs.pdf (2004).
\bibitem{key-17}\label{the:Concurrency-Control-and} P. A. Bernstein, V. Hadzilacos,
N. Goodman, \emph{Concurrency Control and recovery in database systems},
Addison-Wesley (1987).
\bibitem{key-7}\label{the:William-Stallings,-Operating}W. Stallings, \emph{Operating
Systems-Internals and Design Principles}, Prentice-Hall (2004).\end{thebibliography}