# Tag Info

19

There is a good explanation by Craig Gidney here (he also has other great content, including a circuit simulator, on his blog). Essentially, Grover's algorithm applies when you have a function which returns True for one of its possible inputs, and False for all the others. The job of the algorithm is to find the one that returns True. To do this we express ...

16

Have there been any truly ground breaking algorithms besides Grover's and Shor's? It depends on what you mean by "truly ground breaking". Grover's and Shor's are particularly unique because they were really the first instances that showed particularly valuable types of speed-up with a quantum computer (e.g. the presumed exponential improvement for Shor) ...

9

It sounds like you're looking for algorithms that succeed deterministically with probability 1, instead of probabilistic algorithms that succeed with probability bounded from a 1/2 by a finite amount, say 2/3. Exact is the keyword for deterministic quantum algorithms, such as in this paper Exact quantum algorithms have advantage for almost all Boolean ...

9

I've been working on this problem as well. As a beginner and a classical programmer (i.e., I don't speak Quantum Mechanics), it is difficult to get an understanding of the concepts without complete examples. I've been working with the Microsoft Q# Database Search sample. It simply searches for a specific index/key in the database, which is not very useful. ...

8


4

While it is perhaps easiest for us to think about the function of the oracle as already having computed all these values, that's not what it's doing. In the case you described, the oracle has 8 possible inputs (i.e. encoded in 3 (qu)bits), and the oracle does all the computation that you need on the fly. So, the moment you try to evaluate the oracle for some ...

4

I am answering my question. After some google search, I found this image showing CCZ gate by CNOT, T dagger, and T gate. I tried this on IBM Q and it worked. I want to explore why it works but that's another story. For someone who is interested, here is my quantum circuit of Grover's algorithm finding |111> with one iteration.

4

According to this paper, A significant conclusion from this solution is that generically the generalized algorithm also has $O(\sqrt{N/r})$ running time Where 'r' is the number of marked states. By generalized, the authors meant a distribution with arbitrary complex amplitudes. So it seems to answer your question. That the modified initialization would ...

4

Grover focuses on gate costs, while Ambainis focuses on queries. Ambainis solves element distinctness in $O(N^{2/3})$ queries, using $O(N^{2/3})$ memory. If you used that memory to run $O(N^{2/3})$ copies of Grover's algorithm (since each copy needs poly-log space, and I'm being imprecise about logarithmic factors) then each one would search a space of size \$...

Only top voted, non community-wiki answers of a minimum length are eligible