Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

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 ...

18

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


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'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.

4

Although popular explanations of Grover's algorithm talk about searching over a list, in actuality you use it to search over possible inputs 0..N-1 to a function. The cost of the algorithm is $O(\sqrt{N} \cdot F)$ where $N$ is the number of inputs you want to search over and $F$ is the cost of evaluating the function. If you want that function to search over ...

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


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