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

Question

I'm having trouble understanding Grover's Algorithm, so I'd like to start with the case with 1 qubit. But I don't see anyone build it for 1 qubit, only 2 is the minimum. Is it because that's impossible or too trivial? Can anyone provide me with an example of the circuit if it's trivial? Thank you!

Answer 1

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:

1. Both inputs are solutions to $f(x) = 1$.
   The classical solution takes one function evaluation, so there is no speedup.

2. Both inputs are not solutions.
   No matter how many iterations you do, Grover's algorithm is going to give you a random value which will not be a solution, which is not very interesting.

3. Exactly one of the inputs is a solution.
   This case is slightly more interesting. The classical solution is: pick a random input, and it has a 50% chance of being the answer, otherwise you'll need to check the second one.
   Grover's search will start with a superposition of both inputs $\frac{1}{\sqrt2}(|0\rangle + |1\rangle)$; if you do a measurement immediately you'll get the correct answer with 50% chance. One Grover iteration will convert the system to the $\frac{1}{\sqrt2}(|0\rangle - |1\rangle)$ state - which also has 50% chance of measuring the correct answer! If you keep doing iterations, your probability of success is going to remain the same, so you're strictly worse off compared to the classical solution.

No solutions, all solutions and exactly half of the search space being solutions are all corner cases of Grover's search algorithm, and the single-qubit case doesn't have any other scenarios, so it's not very illustrative. That's why all sources start with at least 2 qubits.