# Tag Info

28

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

26

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

22

TL;DR: This is probably going to be disappointing. If a cat enters a superposition and we lose track of the relative phase $\phi$ then there is only one deterministic operation that returns to the $|\text{alive}\rangle$ state: the state preparation channel. In other words, we have to get a new cat. Let us represent the states of the cat on the Bloch sphere ...

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

13

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

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

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

10


10


6

You need to convert the oracle to hold the database too, as a result, the general Oracle (Phase Inversion) will have two sub-oracles take a look the figure. The first sub-oracle that have to prepared is the memory circuit, in contrast to QRAM which stores quantum data (state) in its body, this memory (array) circuit is prepared to store only classical ...

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