# Why is the number of solutions given in Qiskit textbook(Quantum Counting Algorithm) as N-M instead of M?

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?

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.

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

$$U_s = 2|s\rangle\langle s| - I_n$$
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$$.