---
abstract: 'In the recent years we have seen that Grover search algorithm [@grover-search] by using quantum parallelism has revolutionized the field of solving huge class of NP problems in comparison to classical systems. In this work we explore the idea of extending the Grover search algorithm to approximate algorithms. Here we try to analyze the applicability of Grover search to process an unstructured database with dynamic selection function as compared to the static selection function in the original work[@grover-search]. This allows us to extend the application of Grover search to the field of randomized search algorithms. We further use the Dynamic Grover search algorithm to define the goals for a recommendation system, and define the algorithm for recommendation system for binomial similarity distribution space giving us a quadratic speedup over traditional unstructured recommendation systems. Finally we see how the Dynamic Grover Search can be used to attack a wide range of optimization problems where we improve complexity over existing optimization algorithms.'
author:
- 'Indranil Chakrabarty, Shahzor Khan and Vanshdeep Singh'
title: 'Dynamic Grover Search: Applications in Recommendation systems and Optimization problems'
---

=10000

\[theorem\][Lemma]{} \[theorem\][Corollary]{} \[theorem\][Proposition]{} \[theorem\][Conjecture]{}

\[theorem\][Definition]{}

I. Introduction
===============

The promise of quantum computation is to enable new algorithm which renders physical problems using exorbitant physical resources for their solution on a classical computer. There are two broader class of algorithms. The first class is build upon *Shor’s quantum fourier transform* [@shor] and includes remarkable algorithms for solving the discrete logarithm problems, providing a striking exponential speedup over the best known classical algorithms. The second class of algorithm is based upon Grover’s algorithm for performing *quantum searching* [@grover-search]. Apart from these two broader line of divisions Deutsch algorithm based on *quantum parallelism/interference*[@Deutsch] is another example which has no classical analogue. This provide a remarkable speed up over the best possible classical algorithms. With the induction of quantum algorithms questions were raised for proving complexity superiority of Quantum Model over Classical Model [@feynman].\
Grover’s Search algorithm was one of the first algorithms that opened a class of problems solvable by Quantum Computation[@grover-framework], in a quadratic speedup over classical systems. Classical unstructured search or processing of search space, is essentially linear as we have to process each item using randomized search functions which can be at best optimized to $N/2$ states. In 1996, L.K.Grover gave the Grover Search algorithm to search through a search space in $ \mathcal{O}\sqrt{N} $ [@grover-search]. The algorithm leverages the computational power of superimposed quantum states. In its initialization step an equi-probable superposition state is prepared from the entire search space. In each iteration of the algorithm the coefficients of selected states, based on a selection function, are increased and that of the unselected states are decreased by inversion about the mean. This method increases the coefficients of selected states quadratically and in $ \mathcal{O}\sqrt{N} $ steps we get the selected states with high probability. The unstructured search approach can be used to compute any NP problem by iterating over the search space.\
From an application perspective quantum search algorithms have several applications, as it can be used to extract statistic, such as the minimal element from an unordered data set more quickly than is possible on a classical computer[@min]. It has been extended to solve various problems like finding different measures of central tendency like mean [@mean] and median [@median]. It can be used to speed up algorithms for some problem in NP specifically those problems for which a straightforward search for a solution is the best algorithm known. Finally it can be used to speedup the search for keys to the cryptographic systems such as widely used Data Encryption Standard (DES).\
In the field of e-commerce we have seen recommended system collects information on the preferences of users for a set of items. The information can be acquired explicitly (by collecting user’s ratings) or implicitly (monitoring user’s behavior)[@lee; @nun; @choi]. It make uses of different sources of information for providing user with prediction and recommended items. They try to balance various factors like accuracy, novelty, dispersity and stability in the recommended items. Collaborative filtering plays an important role in the recommendations although they are often used with other filtering techniques like content-based, knowledge-based. Another important approach in recommending process is the k-nearest neighbor hood approach in which we find the k nearest neighbors of the search item. Recently recommendation system implementations has increased and has facilitated in diverse areas [@park] like recommending various topics like music, television , book documents; in e-learning and e-commerce; application in markets and web search [@car; @serr; @zai; @huang; @castro; @costa; @Mcnally]. Mostly these recommendations are done in structured classical database .\
NP problems[@NPProblems] have been explored in general to be solved using Grover Search [@grover-framework]. In extension to that optimization problems have been used to find solution to various specific applications. The class of NP Optimization problem (NPO)[@NPO] exists which finds solution for the combinatorial optimization problems under specific conditions. In this work we replace the static selection function of the Grover search with a dynamic selection function. This allows us to extend the application of Grover search to the field of randomized search algorithms. One such application is the use in recommendation System. We also define the goals for a recommendation system. Finally we define the algorithm for recommendation system for binomial similarity distribution space giving us a quadratic speedup over traditional unstructured recommendation systems. Another application is in finding an optimal search state, for a given NPO problem. We see that Durr and Hoyer’s work [@min] also performs optimization in $O(\log (N) \sqrt{N})$, however use of dynamic Grover Search can achieve the same in $O(\sqrt{N})$.\
In section II we give a brief introduction to Grover search by using standard static selection function. In section III we introduce our model of dynamic grover search and by defining the algorithm over the binomial distribution space and then by comparing it with the traditional unstructured recommended systems. In the last section IV we provide an application of this dynamic grover search in recommendation systems and optimization algorithms.\

II. Grover Search Algorithm
===========================

In this section we briefly describe Grover search algorithm as a standard searching procedure and elaborate on the fact that how it expedites the searching process as compared to a classical search in an unstructured database[@nielsen].\
**Oracle:** Suppose we wish to search for a given element through an unstructured search space consisting of $N$ elements. For the sake of simplicity, instead of directly searching a given element we assign indices to each of these elements which are just numbers in the range of $0$ to $N-1$. Without loss of generality we assume $N=2^n$ and we also assume that there are exactly $M$ solutions ($1\leq M \leq N$) to this search problem. Further, we define a selection function $f$ which takes an input state $\ket{x}$, where the index $x$ lies in the range $0$ to $N-1$. It assigns value $1$ when the state is a solution to the search problem and the value $0$ otherwise,

$$\begin{aligned}
 f =
  \begin{cases}
   0 & \text{if $\ket{x}$ is not selected}, \\
   1 & \text{if $\ket{x}$ is selected}.
  \end{cases}\end{aligned}$$

Here we are provided with quantum oracle-black box which precisely is a unitary operator $O$ and its action on the computational basis is given by, $$\ket{x}\ket{q} \rightarrow  \ket{x} \ket{q \oplus f(x)}.$$ In the above equation we have $\ket{x}$ as the index register. The symbol $\oplus$ denotes addition modulo $2$, and the oracle qubit $\ket{q}$ gets flipped if we have $f(\ket{x})=1$. It remains unchanged otherwise. This helps us to check whether $\ket{x}$ is a solution to the search problem or not as this is equivalent of checking the oracle qubit is flipped or not.\
**Algorithm:** The algorithm starts by creating a superposition of $N$ quantum states by applying a Hadamard transformation on $\ket{0}^{\otimes n}$.

$$\ket{\psi} =\frac{1}{\sqrt{N}}\sum _{x=0}^{N-1}\ket{x}$$

The algorithm then proceeds to repeated application of a quantum subroutine known as the Grover iteration or as the Grover operator denoted by $G$. The grover subroutine consists of following steps:\
**Procedure: Grover Subroutine**

-   Apply the Oracle $O$.

-   Perform inversion about mean.

**Algorithm: Grover Search**

-   Initialize the system, such that there is same amplitude for all the N states

-   Apply Grover Iteration $O(\sqrt{N})$ times

-   Sample the resulting state, where we get the expected state with probability greater than 1/2

**Geometry:** The entire process of Grover iteration can be considered as a rotation in the two dimensional space, where 1 dimension represents the solution space, and the other represents the remaining search space. These normalized states are written as,

$$\begin{aligned}
\ket{ \alpha} = \frac{1}{\sqrt{N-M}}\sum_x^{''} \ket{ x} \nonumber\\
\ket{ \beta} = \frac{1}{\sqrt{M}}\sum_x^{'} \ket{ x} .\end{aligned}$$

The initial state $\ket{ \psi} $ can be re-expressed as

$$\ket{ \psi} =\sqrt{\frac{N-M}{N}}\ket{ \alpha} +\sqrt{\frac{M}{N}}\ket{ \beta}  .$$

Geometric visualization of Grover iteration can be described in two parts, the oracle function and inversion about mean. The oracle function can be considered as reflection of state $\ket{\psi}$ about $\ket{\alpha}$ and the inversion about mean further reflects this state about the new mean ($\approx \ket{\psi} $)

In short, $G$ can be understood as a rotation in two dimensional space spanned by $\ket{ \alpha} $ and $\ket{ \beta} $. It is rotating the state $\ket{\psi}$ with some angle $\theta$ radians per application of $G$. Applying Grover rotation operator multiple times brings the state vector very close to $\ket{ \beta} $.\

(Origin) at (0,0); (XAxisMax) at (5,0); (YAxisMax) at (0,3); (Origin) – (XAxisMax) node \[right\] [$\ket{ \alpha }$]{};(Origin) – (YAxisMax) node \[right\] [$\ket{ \beta }$]{};(Origin) – (15: 4) node \[right\] [$\ket{ \psi }$]{};(Origin) – (-15: 4) node \[right\] [$O \ket{ \psi }$]{};(Origin) – (45: 4) node \[right\] [$G \ket{ \psi }$]{};(15: 4) – (-15: 4) – (45: 4);

(0:2.1) arc (0:15:2.1) node \[ right \] [$\theta /2$]{}; (0:2.1) arc (0:-15:2.1) node \[above right\] [$-\theta /2$]{}; (15:2.1) arc (15:45:2.1) node \[below right\] [$\theta$]{};

III. Dynamic Grover’s Search
============================

In this section we introduce a dynamic selection function $f_{s}$ which selects a state $\ket{ x} $ with certain probability $P_{s}(\ket{ x} )$. We use $f_{s}$ instead of the static selection function $f$ as used in Grover’s search to introduce randomness in the search algorithm itself. This selection criterion can be based on different properties like similarity to a given state, number of satisfying clauses, etc for applications in recommendation systems, MAX-SAT optimization systems etc.\
We consider $N$ items in a search space which are represented by (computational) basis vectors in a Hilbert space. Here our goal is to select $N_{s}$ states out of these $N$ states using the dynamic selection function. We define the dynamic selection function as: $$f_{s} =
\begin{cases}
1 & \text{$\ket{x}$ is selected with $P_{s}(x)$}, \\
0 & \text{otherwise}.
\end{cases}$$ The dynamic nature of this function introduces selection scenarios that are fundamentally different from the traditional Grover search.\
For analysis let us consider the selected states be represented by $\ket{ x_s} $ with coefficient $a_s$ and unselected states by $\ket{ x_{us}} $ with coefficients $a_{us}$. The state of the system at a given time can be represented as $$\ket{ \psi } = \sum_{s} a_s\ket{ x_s} + \sum_{us} a_{us}\ket{ x_{us}} .$$ The probability of sampling from selected states is given by $P_s(=\sum_{s}|a_s|^2)$. Similarly for unselected states we have the corrosponding probability as $P_{us}(=\sum_{us}|a_{us}|^2)$. We define gain $G(=\frac{P_s}{P_{us}})$ as an indicator for achievability of the desired result.

Analysis of Grovers Search in a different scenario
--------------------------------------------------

In this subsection we discuss the impact of dynamic selection function on the execution of Grover’s search. We also analyze the required conditions for a Grover step to complete successfully.\
**Corollary 1:** For proper execution of Grover search following conditions must be satisfied.\

1.  The mean $\mu$ calculated in the inversion step should be positive.

2.  The probability amplitude $a_{us}$ of the unselected states $\ket{ x_{us}} $ remain positive.

3.  The number of selected states $\ket{ x_{s}} $ for Gain $G$ should be $$N_{s} < \frac{N}{2G} \;\;\;\; where \;\; G \gg 1$$

*Proof 1:* The mean $\mu$ (calculated in the inversion step) should be positive. If the mean is less than 0 then the coefficients of the selected states will decrease and the coefficients of the unselected states will become negative as given by,

$$\begin{aligned}
&&a_{x_{s}} = \mu - (- a_{x_{s}} - \mu) = 2\mu + a_{x_{s}}{}\nonumber
\\&&
a_{x_{us}} = \mu - (a_{x_{us}} - \mu) = 2\mu - a_{x_{us}}\end{aligned}$$

*Proof 2:* The coefficients of the unselected states remain positive. If the coefficient of the unselected state is negative the mean will be negative.\
*Proof 3:* For successfully having a gain $G$, $$N_{sel} < \frac{N}{2G} \;\;\;\; where \;\; G \gg 1$$ as described in Appendix A1.\
**Corollary 2:** If a state is selected in a Grover iteration and not in the next one, coefficient of the selected state after the next iteration will be less than those states which are not selected in both these rounds.\
*Proof :* Consider $\ket{ \psi_{i}} $ to be the input state to the iteration process. The first Grover step inverts the selected state to $\ket{ \psi_{iv}} $ and then calculates the mean state $\ket{ \psi_{\mu}} $. The final probability of the selected state $\ket{ \psi_{s}} $ is increased and the state $\ket{ \psi_{us}} $ is decreased as compared to the $\psi_{i}$, as described earlier in introduction.\
Let $a_s$, $a_{us}$ be the coefficients, $\mu_1$ be the mean and $a_{s1}$, $a_{us1}$ be the output for the first Grover iteration. Then we have,\
$$\begin{aligned}
&& a_{s1} = 2 \mu_1 + a_s {}\nonumber \\&&
 a_{us1} = 2 \mu_1 - a_{us}\end{aligned}$$

For the second iteration when no states are selected, let $\mu_2$ be the mean and $a_{s2}$, $a_{us2}$ be the outputs of the iteration. These coefficients are given by,\
$$\begin{aligned}
&& a_{s2} = 2 \mu_2 - a_{s1} = 2\mu_2 - 2\mu_1 - a_s {}\nonumber \\&&
 a_{us2} = 2 \mu_2 - a_{us1} = 2\mu_2 - 2\mu_1 + a_{us} \end{aligned}$$

Hence the coefficient of the state $a_{s2}$ that was selected in one iteration is less that the state $a_{us2}$ that was never selected.

The Fig \[fig:GeometricReper\] shows a geometric representation of a Grover iteration with initial state (black arrow), selected and unselected states (red arrow).\

(Origin) at (0,0); (XAxisMax) at (5,0); (YAxisMax) at (0,3); (Origin) – (XAxisMax) node \[right\] [$\ket{\alpha}$]{};(Origin) – (YAxisMax) node \[right\] [$\ket{\beta}$]{};(Origin) – (15: 4) node \[above right\] [$\ket{\psi_{i}}$]{};(Origin) – (-15: 4) node \[above right\] [$ \ket{\psi_{iv}}$]{};(Origin) – (13: 4) node \[right\] [$ \ket{\psi_{\mu}}$]{};(Origin) – (11: 4) node \[below right\] [$ \ket{\psi_{us}}$]{};(Origin) – (41: 4) node \[above right\] [$ \ket{\psi_{s}}$]{};(0:1.5) arc (0:15:1.5) node \[below right\] [$\theta$]{}; (0:1.5) arc (0:-15:1.5) node \[above right\] [$-\theta$]{}; (-15:2.1) arc (-15:13:2.1) node \[below right\] [$\theta_{s}$]{}; (13:2.1) arc (13:41:2.1) node \[right\] [$\theta_{s}$]{}; (15:2.5) arc (15:11:2.5) node \[above\] [$2 \theta_{us}$]{};

Further, let us suppose that in the next iteration, a state $\ket{ \psi_{s}} $ which is selected earlier is not selected and an earlier unselected state $\ket{ \psi_{us}} $ is not selected. Now consider that no state is selected and no inversion occurs, then in that case the mean $\ket{ \psi_{\mu2}} $ lies above $\ket{ \psi_{us}} $. The inversion about mean will cause the state $\ket{ \psi_{s}} $ (in black) to become the state $\ket{ \psi_{s1}} $ (in red) which has a probability lower than those states which were unselected twice $\ket{ \psi_{us1}} $.\

(Origin) at (0,0); (XAxisMax) at (5,0); (YAxisMax) at (0,3); (Origin) – (XAxisMax) node \[below right\] [$\ket{ \alpha }$]{};(Origin) – (YAxisMax) node \[right\] [$\ket{ \beta }$]{};(Origin) – (13: 4) node \[below right\] [$ \ket{ \psi_{us1} }$]{};(Origin) – (27: 4) node \[above right\] [$ \ket{ \psi_{s1} }$]{};(Origin) – (15: 4) node \[right\] [$ \ket{ \psi_{\mu2} }$]{};(Origin) – (17: 4) node \[above right\] [$\ket{ \psi_{us2} }$]{};(Origin) – (3: 4) node \[right\] [$ \ket{ \psi_{s2} }$]{}; (27:1.5) arc (27:3:1.5) node \[below right\] [$2 \theta_{s2}$]{}; (17:2.5) arc (17:13:2.5) node \[below right\] [$2 \theta_{us2}$]{};

Note that the issue is not restricted to the case where no state is selected it is inherent with the use of inversion function for unselected states. In order to overcome this issue we need to always run each iteration of Grover twice with a given result from the selection function $f_s$, so that the relative coefficients remain in the order of number of times the state was selected.\
**Corollary 3:** If no state is selected and the Grover step is repeated twice, no change happens in the coefficients.\
**Corollary 4:** If all states are selected and the Grover step is repeated twice, there is no net change in the coefficients.\
*Proof :* In first step all the coefficients will become negative of themselves so the mean will be negative and inversion around the mean will leave them in negative coefficients. In second step all the coefficients will become negative of themselves so mean will be positive and the coefficients will be rotated back to their original places around the mean.\

Dynamic Grovers Search Algorithm
--------------------------------

In this subsection we formalize the procedure of dynamic grover search algorithm.\
**Procedure: Dynamic Grover Iteration**

-   Apply the Oracle $f_{s}$ and store the result.

-   Apply the *Grover Iteration* using the stored oracle results.

-   Apply the *Grover Iteration* again using the stored oracle results, to nullify any negative affects of inversion about the mean.

**Algorithm: Dynamic Grover Search**

-   Initialize the system, such that there is same amplitude for all the N states

-   Apply *Dynamic Grover Iteration* $O(\sqrt{N})$ times

-   Sample the resulting state, where we get the expected state with $probablity > \frac{1}{2}$

IV. Applications of Dynamic Grover search
=========================================

In this section we explore two different applications of our Dynamic grover search algorithm. In the first sub section we show its application in recommendation process. In the second section we give a generic optimization problem and solution using dynamic grover search.

 Quantum Recommendation Algorithm 
----------------------------------

Now that we have described dynamic Grover algorithm, we look towards how it can be applied to recommendation systems.\
In essence a recommendation algorithm on an unstructured search space, is similar to Grover search, with the difference of selection function. If we know the search space well, we can construct a static selection function, that can select top $M$ states. In case of unknown search space, or a dynamic search space, we may not always be able to construct a static selection function. In that case we need to associate the selection dynamically to the similarity with the given state $\ket{x} $ (say). This will increase the probability of selection of desired $M$ states sufficiently.\

Recommendation Problem :
------------------------

-   Consider a standard recommendation problem,

-   Given a unstructured search space $S$,

-   The dimensionality of the space be $n$, and total number of states to be N($=2^n$).

-   We need to find $M$ recommended states for a given search result $\ket{x} $.

Let the similarity of two pure states $S(\ket{x} ,\ket{y} )$, represent a measure of the likeliness of these two states to be recommended for each other.\
**Criteria for an effective Recommendation function**\
Now we give a criteria for selection function $f_{s}$ to be effective in a dynamic system. Let the Dynamic Selection function be given as: $$\begin{aligned}
    f_{s} =
  \begin{cases}
      1 & \text{$\ket{x}$ is selected with $P_{s}$}, \\
   0 & \text{otherwise}.
  \end{cases}\end{aligned}$$

The $P_{s}$ should have the following criteria for good recommendation:

-   The most likely state is selected with high probability, $$\lim_{S(x,y) \to n } P_{s}(x) \geq \Big( 1-\frac{1}{N} \Big)$$

-   The least likely state is selected with a low probability, $$\lim_{S(x,y) \to 0 } P_{s}(x) \leq \Big( \frac{1}{N} \Big)$$

-   In order to select $M$ states, we have from Corollary 1, $$M < \frac{N}{2G}$$ The expected number of selected states, $$E(N_{s}) = \int_{x} P_{s}(x,y) \approx M$$

 Recommendation for Binomial distribution
-----------------------------------------

Consider an example for initial state space with equal probability for each of the states. The similarity of states with respect to a particular state be given by the Manhattan distance between the states. The Similarity function $S(x,y)$ would be a binomial curve Fig \[fig:BinomialDistribution\]. The probability of selection is given by the following equation: $$e^{-\log(\sqrt[n]{K}-1) S(\ket{x},\ket{y})}$$ The expected selection should be Fig \[fig:BinomialProbabilty\]

; (axis cs:4,0) – node \[fill=white\] [$S(|x\rangle, |y\rangle)$]{} (axis cs:7.2,0);

; ;

(axis cs:4,0) – node \[fill=white\] [$S(|x\rangle, |y\rangle)$]{} (axis cs:5.96,0);

coordinates [ ( 10, 7 ) ( 11, 11 ) ( 12, 17 ) ( 13, 22 ) ( 14, 32 ) ]{}; coordinates

( 10, 7 ) ( 11, 10 ) ( 12, 13 ) ( 13, 18 ) ( 14, 25 )

;

coordinates [ ( 0 , 0 ) ( 1 , 0 ) ( 2 , 0 ) ( 3 , 7.31511470083e-06 ) ( 4 , 0.000105024146776 ) ( 5 , 0.000570578946665 ) ( 6 , 0.00249286535328 ) ( 7 , 0.00745920069926 ) ( 8 , 0.0317610356855 ) ( 9 , 0.0618686957303 ) ( 10, 0.120915738795 ) ( 11, 0.179278528288 ) ( 12, 0.240100783919 ) ( 13, 0.35544023332 ) ]{};

coordinates

( 0 , 0 ) ( 1 , 0 ) ( 2 , 0 ) ( 3 , 6.428343871e-07 ) ( 4 , 9.22926512908e-06 ) ( 5 , 5.01410821938e-05 ) ( 6 , 0.000137933892775 ) ( 7 , 0.000211768013807 ) ( 8 , 0.000193217650065 ) ( 9 , 0.000106848258484 ) ( 10, 3.51263075808e-05 ) ( 11, 6.70384432261e-06 ) ( 12, 0.932631829595 ) ( 13, 0.0666165592568 )

;

We see that the dynamic selection, gives a similar performance (Fig \[fig:ExecutionComparison\]) as well as desired accuracy (Fig \[fig:accuracy\]) as would have been given by a static selection function using the Grover search. However this algorithm makes our recommendation system robust with respect to changes in search space and distribution of search space. Further details can be seen from the Appendix.

Approximate Optimization Algorithms 
------------------------------------

The Grover search algorithm was a landmark algorithm because it provided a framework[@grover-framework], that can be used to solve any NP problem, with a quadratic speedup over classical systems. Durr and Hoyer’s work on finding minimum of the search space [@min] can be considered as a tool to find the optimal value (min or max) for a search space, but it is done by applying the Grover search multiple times, and uses the quantum probability during the sampling to arrive at the optimal state.\
**Optimization Problem:** An optimization problem can be represented in the following way:\
$\boldsymbol{Given:}$ A function $f : A \to R$ from some set $A$ to the set of all real numbers $R$.\
$\boldsymbol{Sought:}$ An element $\ket{x_o} $ (optimal) in $A$ such that $f(\ket{x_o}  \leq f(\ket{x} )$ for all $\ket{x} $ in $A$ (minimization) or such that $f(\ket{x_o} ) \geq f(\ket{x} )$ for all $\ket{x} $ in $A$ (maximization).\

Solving Optimization Problem using Durr and Hoyer’s Min Approach
----------------------------------------------------------------

To solve the Optimization problem using Durr and Hoyer’s approach[@min], the selection function would use the following:

1.  Set $\ket{x_o}  = \ket{0} $

2.  Set $f_{s} = f(\ket{x} ) \geq f(\ket{x_o} )$

3.  Run Grover Search using $f_{s}$, sample out $\ket{y} $

4.  **if** $ f(\ket{y} ) > f(\ket{x_o}) $

    -   $\ket{x_o}  = \ket{y} $

    -   Repeat from 2

5.  **else** return $\ket{x_o} $.

The algorithm runs in expected $O(\log(N)\sqrt{N})$ Grover iterations.\
**Solving Optimization Problem using Dynamic Grover Search :** With the Dynamic Grover System, we present a generic framework for solving optimization problems using classical probability. Consider the distribution function $D(\ket{x} ) = f(\ket{x} )$, we use a Probabilistic function $P_{s}: A \to [0,1]$ such that,\
$$\lim_{f(\ket{x} ) \to f_{max} } P_{s}(\ket{x} ) \geq \Big( 1-\frac{1}{N} \Big)$$

$$\lim_{f(x) \to f_{min}} P_{s}(\ket{x} ) \leq \Big( \frac{1}{N} \Big)$$

Using a good heuristic, a probabilistic function $P_{s}$ can be chosen to get optimal results with high probability by running Grover search algorithm once. Hence the Dynamic Grover search can be modeled for any Optimization Problem, which runs in $O(\sqrt{N})$ Grover iterations. And the accuracy of the search depends on the Probability function $P_{s}$.\

[99]{} \[bb\] L. K. Grover, A fast quantum mechanical algorithm for database search, arXiv:quant-ph/9605043.

P. W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM. J. Comp. 26(5), 1484 (1997). arXiv:quant-ph/9508027

D. Deutsch and R. Zozsa, Proc. R. Soc. London A, 439, (1992).

Richard P. Feynman, Simulating physics with computers, Keynote speech, Dept. of Physics, California Institute of Technology, Pasedena. http://www.cs.berkeley.edu/ christos/classics/Feynman.pdf

A framework for fast quantum mechanical algorithms, Lov K. Grover, arXiv:quant-ph/9711043v2

C. Durr, P. Hoyer, A Quantum Algorithm for Finding the Minimum, arXiv:quant-ph/9607014v2.

L. K. Grover, A fast quantum mechanical algorithm for estimating the median, Bell Lab Technical Memorandum No. ITD-96-30115J, arXiv:quant-ph/9607024v1.

R. R. Tucci, Quantum Circuit for Calculating Mean Values Via Grover-like Algorithm, arXiv:quant-ph/1404.0668.

S.K. Lee, Y.H. Cho, S.H. Kim, Collaborative filtering with ordinal scale-based implicit ratings for mobile music recommendations, Information Sciences 180 (11) (2010) 2142–2155.

E.R. Núñez-Valdéz, J.M. Cueva-Lovelle, O. Sanjuán-Martınez, V. Garcıa-Dıaz, P. ́Ordoñez, C.E. Montenegro-Marın, Implicit feedback techniques on recommender systems applied to electronic books, Computers in Human Behavior 28 (4) (2012) 1186–1193.

K. Choi, D. Yoo, G. Kim, Y. Suh, A hybrid online-product recommendation system: combining implicit rating-based collaborative filtering and sequential pattern analysis. Electronic Commerce Research and Applications, in press, doi: 10.1016/j.elerap.2012.02.004.

D.H. Park, H.K. Kim, I.Y. Choi, J.K. Kim, A literature review and classification of recommender Systems research, Expert Systems with Applications 39 (2012) 10059–10072.

W. Carrer-Neto, M.L. Hernández-Alcaraz, R. Valencia-Garcıa, F. Garcıa- Sánchez, Social knowledge-based recommender system, Application to the movies domain. Expert Systems with Applications 39 (12) (2012) 10990– 11000; P. Winoto, T.Y. Tang, The role of user mood in movie recommendations, Expert Systems with Applications 37 (8) (2010) 6086–6092.

J. Serrano-Guerrero, E. Herrera-Viedma, J.A. Olivas, A. Cerezo, F.P. Romero, A google wave-based fuzzy recommender system to disseminate information in University Digital Libraries 2.0., Information Sciences 181 (9) (2011) 1503– 1516; C. Porcel, E. Herrera-Viedma, Dealing with incomplete information in a fuzzy linguistic recommender system to disseminate information in university digital libraries, Knowledge-Based Systems 23 (1) (2010) 32–39; C. Porcel, J.M. Moreno, E. Herrera-Viedma, A multi-disciplinar recommender system to advice research resources in university digital libraries, Expert Systems with Applications 36 (10) (2009) 12520–12528; C. Porcel, A. Tejeda-Lorente, M.A. Martınez, E. Herrera-Viedma, A hybrid recommender system for the selective dissemination of research resources in a technology transfer office, Information Sciences 184 (1) (2012) 1–19.

O. Zaiane, Building a recommender agent for e-learning systems, in: Proceedings of the International Conference on Computers Education (ICCE’02), vol. 1, 2002, pp. 55–59; J. Bobadilla, F. Serradilla, A. Hernando, Collaborative filtering adapted to recommender systems of e-learning, Knowledge Based Systems 22 (2009) 261–265.

Z. Huang, D. Zeng, H. Chen, A comparison of collaborative filtering recommendation algorithms for e-commerce, IEEE Intelligent Systems 22 (5) (2007) 68–78.

J.J. Castro-Sanchez, R. Miguel, D. Vallejo, L.M. López-López, A highly adaptive recommender system based on fuzzy logic for B2C e-commerce portals, Expert Systems with Applications 38 (3) (2011) 2441–2454.

E. Costa-Montenegro, A.B. Barragáns-Martınez, M. Rey-López, Which App? A recommender system of applications in markets: implementation of the service for monitoring users’ interaction, Expert Systems with Applications 39 (10) (2012) 9367–9375.

K. Mcnally, M.P. O’mahony, M. Coyle, P. Briggs, B. Smyth, A case study of collaboration and reputation in social web search, ACM Transactions on Intelligent Systems and Technology 3 (1) (2011).

Hromkovic, Juraj (2002), Algorithmics for Hard Problems, Texts in Theoretical Computer Science (2nd ed.), Springer, ISBN 978-3-540-44134-2

Kann, Viggo (1992), On the Approximability of NP-complete Optimization Problems, Royal Institute of Technology, Sweden, ISBN 91-7170-082-X

Quantum Computation and Quantum Information, Nielsen, Chuang.

A. Appendices
=============

 Proof of Corollary 1
---------------------

**Corollary 1.** *In order for the Grover’s search to have a meaningful next step, following conditions must be satisfied.*

1.  The Mean ($\mu$) (calculate in the inversion step) should be positive.

2.  The coefficients of the unselected states remain positive.

3.  The number of selected states $N_{s}$ for Gain G($=\frac{P_{s}}{P_{us}})$ should be $$N_{s} < \frac{N}{2G} \;\;\;\; where \;\; G \gg 1$$

**Proof:** Let $N$, $N_s$ and $N_{us}$ be total number of states, number of selected states, and number of unselected states respectively. Hence $$N_{us} = N - N_s$$

Let $\mu$, $a_s$ and $a_{us}$ be the mean, the coefficient of selected states , and coefficient of unselected states respectively. Hence $$\mu = \frac{N_{us}  a_{us} - N_s  a_s}{N}$$

For Coefficient of unselected states to be positive (say in the last step)

$$a_{us1} = 2\mu - a_{us} > 0$$

$$\implies 2\frac{N_{us}  a_{us} - N_{s}  a_{s}}{N} - a_{us} > 0$$

$$\implies \frac{a_s}{a_{us}} < (\frac{N}{2 N_s} - 1)$$

Now $G = \frac{P_{s}}{P_{us}}$

$$\implies G = \frac{N_s  a_s^2}{(N - N_s)  a_{us}^2}$$

since $a_s$ and $a_{us}$ is positive,

$$\implies G < \frac{N_s}{N - N_s}  (\frac{N}{2 N_s} - 1)^2$$

for $G \gg 1 $, $$N_s < \frac{N}{2 G}$$
