# Tag Info

26

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

24

The function $f$ is simply an arbitrary boolean function of a bit string: $f\colon \{0,1\}^n \to \{0,1\}$. For applications to breaking cryptography, such as [1], [2], or [3], this is not actually a ‘database lookup’, which would necessitate storing the entire database as a quantum circuit somehow, but rather a function such as \begin{equation*} x \...

21

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

14

If you have 8 items in the list (like in your card's example), then the input of the oracle is 3 (qu)bits. Number of cards in the deck (52) is irrelevant, you need 3 bits only to encode 8 cards. You can think that 3 bits encode the position in the list of the card you are searching; then you don't know the position, but the oracle knows. So if you are ...

11

Applying the Grover iterate a total number of $\lfloor \frac{\pi}{4}\sqrt{N}\rfloor$ times is the best choice if we want to maximize the success probability of Grover's algorithm. This is to some extent explained in Kaye, Laflamme and Mosca (KLM), but let me elaborate on the most important details here. Let $n$ be a natural number, $N = 2^n$, and suppose ...

11

The case of 1 qubit turns out to be pretty bad for understanding Grover's algorithm. There are several scenarios for the function you're looking at: Both inputs are solutions to $f(x) = 1$. The classical solution takes one function evaluation, so there is no speedup. Both inputs are not solutions. No matter how many iterations you do, Grover's algorithm is ...

9

Good question. For unstructured search, adiabatic quantum computation indeed gives the exact same $\sqrt{N}$ speedup that the standard gate-based Grover's algorithm does, as proven in this important paper by Roland and Cerf. This agrees with the equivalence between adiabatic and gate-based quantum computation that you mentioned. (One minor correction to ...

9


6

It's a good question, as the number of solutions is sometimes unknown. The approach is described in Algorithm 2 of this paper. Essentially, you can repeatedly apply Grover's, but incrementally (yet exponentially) increase the number of applications of the Grover iterate; thus, if you find the solution, you're done. Otherwise, because the prior trial failed, ...

6

There are different ways to achieve that, my favorite is probably this one: The oracle you describe above is just a classical function ("True if my bitstring is 101 or 110") converted to a quantum phase flip. So essentially you only have to build a circuit that implements that classical logic plus some gates to do the phase flip. Option A: Via ...

6

A lot of explanations of Grover's search suffer from the common issue of claiming it's a database search or, worse yet, looking for a hardcoded element. (You have examples of both in your question, so you've already noticed this!) In reality Grover's search is best thought of as a way of searching for an element that satisfies a certain condition, i.e., ...

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