What applications does Grover's Search Algorithm have?

Question

Grover's Search algorithm is usually talked about in terms of finding a marked entry in an unsorted database. This is a natural formalism that lets it be applied directly to searching for solutions to NP problems (where a good solution is easily recognised).

I was interested to learn about other applications of Grover's search to finding the minimum, mean and median of a set of numbers. That leaves me wondering if there are any other less-obvious applications of Grover's search (or applications of its generalisations such as amplitude amplification) which are already known? Any brief insight about how this is done would be appreciated.

Answer 1

Apart from the ones you mentioned, another application of (a modified) Grover's algorithm which I'm aware of is solving the Collision problem in complexity theory, quantum computing and computational mathematics. It's also called the BHT algorithm.

Introduction:

The collision problem most often refers to the 2-to-1 version which was described by Scott Aaronson in his PhD thesis. Given that $n$ is even and a function $f:\{1,...,n\}\to\{1,...,n\}$ we know beforehand that either $f$ is 1-to-1 or 2-to-1. We are only allowed to make queries about the value of $f(i)$ for any $i\in\{1,2,...,n\}$. The problem then asks how many queries we need to make to determine with certainty whether $f$ is 1-to-1 or 2-to-1.

Solving the 2-to-1 version deterministically requires $n/2+1$ queries, and in general distinguishing r-to-1 functions from 1-to-1 functions requires $n/r+1$ queries.

Deterministic classical solution:

This is a straightforward application of the pigeonhole principle: if a function is r-to-1, then after $n/r+1$ queries we are guaranteed to have found a collision. If a function is 1-to-1, then no collision exists. If we are unlucky then $n/r$ queries could return distinct answers. So $n/r+1$ queries are necessary.

Randomized classical solution:

If we allow randomness, the problem is easier. By the birthday paradox, if we choose (distinct) queries at random, then with high probability we find a collision in any fixed 2-to-1 function after $\Theta(\sqrt{n})$ queries.

Quantum BHT solution:

Intuitively, the algorithm combines the square root speedup from the birthday paradox using (classical) randomness with the square root speedup from Grover's (quantum) algorithm.

First, $n^{1/3}$ inputs to $f$ are selected at random and $f$ is queried at all of them. If there is a collision among these inputs, then we return the colliding pair of inputs. Otherwise, all these inputs map to distinct values by $f$. Then Grover's algorithm is used to find a new input to $f$ that collides. Since there are only $n^{2/3}$ such inputs to $f$, Grover's algorithm can find one (if it exists) by making only $\mathcal{O}(\sqrt{n^{2/3}})=\mathcal{O}(n^{1/3})$ queries to $f$.

Sources:

1. https://en.wikipedia.org/wiki/Collision_problem

2. https://en.wikipedia.org/wiki/BHT_algorithm

3. Quantum Algorithm for the Collision Problem - Gilles Brassard, Peter Hoyer, Alain Tapp

Answer 2

Grover's algorithm is used extensively in quantum cryptography as well. It can be used to solve problems such as the Transcendental Logarithm Problem, Polynomial Root Finding Problem etc.

Answer 3

Grover's algorithm can be used to solve any numerical optimization problem faster than brute-force search, because any optimization problem can be formulated as a search problem (where you are searching for a function output greater/less than some fixed $M$ within each run, and you repeat for a logarithmic number of runs using binary search to home into the optimal $M$): https://epubs.siam.org/doi/abs/10.1137/040605072?journalCode=sjope8.

In fact, Grover's algorithm is the best-known quantum algorithm for many difficult optimization problems (such as NP-complete ones) that don't have much structure that is amenable to a classical algorithm cleverer than brute-force search: https://link.springer.com/chapter/10.1007/978-3-540-78773-0_67.

Answer 4

I can't comment on previous answers but I would like to comment on the BHT.

You first choose $n^{1/3}$ inputs. Check for collison there. If there's no collision, than as Wikipedia says, all f values are distinct. Now you know there're $n^{1/3}$ inputs that are pairs to those you first chose and weren't tested.

How many do you have to sample to get a collision? by randomly sampling an input from the $n-n^{1/3}$ not tested inputs, you get chances of $\frac{n^{1/3}}{n}$ to find collision.

If you sample $n^{2/3}$ inputs you get that with constant probability you find a collision. Use Grover to make a speedup to $n^{1/3}$.

A more formal solution will be to think of how many iterations Grover algorithm takes when you have a promise that $K$ of the "oracle elements" are 1 (and not 1 only which is the worst case). When computing the number of iteration we use the initial angle between $A$ and $B$ (defined later) and you can see the relation to $K$:

$ A = \frac{1}{\sqrt n} \sum_{i\in[n]} |i> $ (super position on all possible inputs)

$ B = {\frac{1}{\sqrt K}} \sum_{i \in [n] \land O_i=1} |i> $