I'm following the Qiskit textbook for Quantum Counting. We have assumed $M$ as the number of states containing solutions throughout the algorithm but at last, $N-M$ has been taken as the solution. What am I missing?

enter image description here

Here $|w\rangle$ corresponds to the number of states that contain solutions and $|𝑠'\rangle$ corresponds to the number of states that don't contain solutions.

$\langle s'|s\rangle = \cos \frac{\theta}{2}$

$\langle s'|s\rangle = \sqrt \frac{N-M}{N}$

We combine these equations to obtain:

$N \sin^2 \frac{\eta}{2} = M$

The theory part is understandable, and it clearly shows that $M$ is the number of states containing solutions, yet, the answer is given as $N-M$.

Can anyone help me with it?


(I'm unsure if you were asking for a derivation of the inner product, but hopefully this is insightful). Let's call the set of target states $T$. Recognize that, because $|\omega\rangle$ is the equal superposition of $ M$ states, each of the marked bitstrings will have a coefficient of $ \frac{1}{\sqrt{M}} $. For clarity, we can write:

$$ | \omega \rangle = \frac{1}{\sqrt{M}} \sum_{k \in T} | k \rangle $$

In contrast, $| s' \rangle $ is the orthogonal state, so it has $N - M $ states that are in a uniform superposition. Thus,

$$ |s' \rangle = \frac{1}{\sqrt{N - M}} \sum_{k \not \in T} | k \rangle $$

Finally, we note the initial state is a uniform superposition over all potential states. Thus, there are $N$ potential states, so we can write:

$$ |s \rangle = \frac{1}{\sqrt{N}} \sum_{k} | k \rangle = \frac{1}{\sqrt{N}} \Big( \sum_{k \in T} | k \rangle + \sum_{k \not \in T} |k \rangle \Big)$$

Thus, we take the inner product:

$$ \langle s' | s \rangle = \Big(\frac{1}{\sqrt{N - M}} \sum_{k \not \in T} \langle k | \Big) \Big( \frac{1}{\sqrt{N}} \sum_{j} |j \rangle \Big) $$

Note that unless $k = j $, $ \langle k | j \rangle $ vanishes as two distinct basis vectors are orthogonal. Thus, we can rearrange the summation:

$$ \sum_{k \not \in T} \frac{1}{\sqrt{N - M}} \frac{1}{\sqrt{N}} \langle k | k \rangle = \sum_{k \not \in T} \frac{1}{\sqrt{N- M }} \frac{1}{\sqrt{N}} $$

Recall that we have $M$ target states, so there are $N - M$ nontarget states (or $N - M$ times where $k \not \in T$), so:

$$ \frac{N - M}{\sqrt{N - M}} \frac{1}{\sqrt{N}} = \sqrt{\frac{N - M}{N}} $$.

As desired.

| improve this answer | |

yes you are correct there is some missing information! This is known in the textbook and should be added in this PR.

The reason is that the easiest way (I know of at least) to create a diffuser circuit is to actually create a circuit that inverts $|s\rangle$, instead of every state orthogonal to $|s\rangle$ as is required by the diffuser. I.e. we implement:

$$-U_s = -2|s\rangle\langle s| + I_n$$

instead of:

$$ U_s = 2|s\rangle\langle s| - I_n $$

These two operations are equivalent up to a phase of -1. As this phase is global in Grover's algorithm and doesn't introduce any effects and we can use the two circuits interchangeably, but when the iterator is controlled, we see this phase become relative and affect our results.

This iterator with negative phase is equivalent to an iterator that searches for 'not-solutions' (of which there are $N-M$), hence an easy fix to do $N - $ our result at the end.

tl; dr: The iterator in that example implements $-U_s$ instead of $U_s$.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.