14
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Some comments on the BHT solution (I didn't find the wikipedia article very enlightening): First, select $n^{1/3}$ inputs to test $f$ at random. Assume they don't collide. Sort these values $x$ according to $f(x)$. Now, if $f(x)$ is 2-to-1, there are $n^{1/3}$ values $x$ not already tested that collide with those tested. So, define a function that checks "not already tested and collides". This defines the marked entries. Collision is easy to test with the sorted list of values $f(x)$. Knowing the exact number of marked entries (if 2-to-1), Grover's (almost) guarantees a solution. $\endgroup$ – DaftWullie May 4 '18 at 14:02
  • $\begingroup$ @DaftWullie Yes, that sure makes sense. Grover's algorithm doesn't guarantee a solution but has a high probability of providing the correct solution. But isn't that quite obvious from the Wikipedia description itself? I'm not sure I understand the point or objection you're making. Am I missing something? $\endgroup$ – Sanchayan Dutta May 4 '18 at 14:40
  • $\begingroup$ All I can say is that it wasn't obvious to me. On first reading, I understood (falsely) that for Grover's, instead of preparing a superposition of all possible states, it only prepared a superposition over the ones not already tested. But that seemed crucial to the way that the speed-up was explained. Also, I was initially concerned about how the collisions were being checked: which pairs were being checked for collisions, and how efficiently could the collision be calculated? $\endgroup$ – DaftWullie May 4 '18 at 14:46
  • $\begingroup$ @DaftWullie Ah, okay. I get your point. Wikipedia doesn't go into that much detail of the algorithm. You can always refer to the original paper (arxiv.org/abs/quant-ph/9705002) for the details (which I guess you already did). Later, I will try to expand on this answer to include all the details. I'm still reading the paper. $\endgroup$ – Sanchayan Dutta May 4 '18 at 14:50
  • 1
    $\begingroup$ Unless qubits and quantum gates turn out to be unbelievably cheaper than bits and classical gates, any discussion of BHT should include the caveat that the costs exceed state-of-the-art classical collision search with the van Oorschot–Wiener machine. See cr.yp.to/papers.html#collisioncost or blog.cr.yp.to/20171017-collisions.html for details. (The latter is a response to an alleged improvement on BHT that claims to be more cost-effective than classical collision search.) $\endgroup$ – Squeamish Ossifrage Jun 6 '18 at 14:44
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Would you care to elaborate a bit? What are these problems? Where can I read more about them? $\endgroup$ – DaftWullie Jun 6 '18 at 19:05
  • 1
    $\begingroup$ ieeexplore.ieee.org/document/7016940 This is an ieee paper which seeks to develop a quantum algorithm for solving the polynomial root finding problem. You can read more about it there $\endgroup$ – da281 Jun 10 '18 at 9:40
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.