# Tag Info

Accepted

### Is there a layman's explanation for why Grover's algorithm works?

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 ...
• 10.6k
Accepted

### How is the oracle in Grover's search algorithm implemented?

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

### Has there been any truly ground breaking advance in quantum algorithms since Grover and Shor?

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 ...
• 47.1k
Accepted

• 47.1k

### How is the Grover-Algorithm applied to a database?

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 ...
• 111
Accepted

### Can anyone provide me with an example of the for Grover's algorithm on one qubit?

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 ...
• 8,116
Accepted

### How is Grover's algorithm used to estimate the mean and median of a set of numbers?

The idea for estimating the mean is roughly as follows: For any $f(x)$ that gives outputs in the reals, define a rescaled $F(x)$ that gives outputs in the range 0 to 1. We aim to estimate the mean of ...
• 47.1k
Accepted

### Can adiabatic quantum computing be faster than Grover's algorithm?

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 ...
• 2,107
Accepted

### Is there any (really) quantum procedure that's an algorithm and not a Las Vegas algorithm?

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

### Nielsen and Chuang, Exercise 6.5: How to simulate oracle for n+1 qubits using one oracle gate for n qubits and one extra qubit?

The simplest solution is to use an ancilla in the $|+\rangle$ state. Swap that ancilla for the oracle's output qubit, conditioned on the control qubit being false, before and after applying the oracle....
• 22.5k

• 47.1k
Accepted

### Grover's Algorithm and its relation to complexity classes?

Summary There is a theory of complexity of search problems (also known as relation problems). This theory includes classes called FP, FNP, and FBQP which are effectively about solving search problems ...
• 10.9k