Tag Info

18

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

15

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

8

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

8


4

Your algorithm is working exactly as it should. Grover's algorithm does not monotonically converge. Instead, the better intuition is to think about a point moving around a circle at constant speed. If you choose the right moment, you will be close to a particular point, but leave it longer and it'll go past, although it will eventually come back again. ...

4

I am going to try to give guesses that can make sense: More qubits does not mean better machines. They may be less noise-tolerant and with less connectivity between qubits. That is why, when you benchmark them (with or without error-correction), you look first at the simplest implementations of state of art algorithms. Plus, you may change some calibrations ...

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