4 added 1 character in body
source | link

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\}$$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

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

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

3 added 2197 characters in body
source | link

Apart from searching a database, estimating mean, median and minimum of a set of numbers, the other well knownones you mentioned, another application of (a slightly modifieda 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$.

Relevant paperSources: Quantum Algorithm for the Collision Problem - Gilles Brassard, Peter Hoyer, Alain Tapp

  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

Apart from searching a database, estimating mean, median and minimum of a set of numbers, the other well known application of (a slightly modified) Grover's algorithm which I'm aware of is solving the Collision problem in complexity theory, quantum computing and computational mathematics. It's called the BHT algorithm.

Relevant paper: Quantum Algorithm for the Collision Problem - Gilles Brassard, Peter Hoyer, Alain Tapp

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

2 added 78 characters in body
source | link

Apart from searching a database, estimating mean, median and minimum of a set of numbers, the other well known application of (a slightly modified) Grover's algorithm which I'm aware of is solving the Collision problem in complexity theory, quantum computing and computational mathematics. It's called the BHT algorithm.

Relevant paper: Quantum Algorithm for the Collision Problem - Gilles Brassard, Peter Hoyer, Alain Tapp

Apart from searching a database, estimating mean, median and minimum of a set of numbers, the other well known application which I'm aware of is solving the Collision problem in complexity theory, quantum computing and computational mathematics.

Relevant paper: Quantum Algorithm for the Collision Problem - Gilles Brassard, Peter Hoyer, Alain Tapp

Apart from searching a database, estimating mean, median and minimum of a set of numbers, the other well known application of (a slightly modified) Grover's algorithm which I'm aware of is solving the Collision problem in complexity theory, quantum computing and computational mathematics. It's called the BHT algorithm.

Relevant paper: Quantum Algorithm for the Collision Problem - Gilles Brassard, Peter Hoyer, Alain Tapp

1
source | link