Will the quantum counting algorithm work if the input is not a uniform superposition (even not a superposition of all basis states)?

For example, if I use a state such as :

$$\frac{1}{4}(2\vert 0000\rangle+\sqrt 3\vert 1000\rangle+\sqrt 6\vert 0011\rangle+\sqrt 3\vert 1111\rangle)$$

as the input of the quantum counting algorithm and I set the oracle of Grover iteration subject to state $\vert 1000\rangle$.

Would the algorithm work with my state?


1 Answer 1


For this answer it is important to know what the quantum counting algorithm is based on. To understand this algorithm, it is important that you first understand both Grover’s algorithm and the quantum phase estimation algorithm. Whereas Grover’s algorithm attempts to find a solution to the Oracle, the quantum counting algorithm tells us how many of these solutions there are. This algorithm is interesting as it combines both quantum search and quantum phase estimation.

So an important step in Grover's algorithm is Grover's diffusion step which is repeated in Grover's algorithm for about $\sqrt{N}$ times, as seen in this paper.

The input of the diffusion step doesn't have to be in total superposition like seen in this post. Here is why:

If $\mathcal{S}$ is a subset of computational basis states with $N$ elements and you have a superposition: $$ |\phi\rangle=\frac{1}{\sqrt{N}}\sum_{x\in\mathcal{S}}|x\rangle $$ then basically all you need to do is change the classic Grover diffusion operator with the complete $n$-qubit uniform superposition $|\psi\rangle$: $$ 2|\psi\rangle\langle\psi|-I $$ into: $$ 2|\phi\rangle\langle\phi|-I $$ A common way of composing the Grover diffusion operator for an $n$-qubit system without fancy gates is to make it out of two Hadamards and some implementation of the diagonal matrix $$ 2|0\rangle\langle0| - I $$ via: $$ H^{\otimes n}(2 \left|0\right>\left<0\right| - I)H^{\otimes n} $$

To get our new diffusion operator, we just need to replace the left Hadamard gate with a gate $B$ and the right Hadamard with $B$(if they are not the same) where $B\left|0\right> = \left|\phi\right>$.

Assuming no difficulty with $B$, it will run in $\mathcal{O}(\sqrt{N})$ with your new $N$. The ideal stopping point will also still be $\approx \frac{\pi}{4}\sqrt{N}$ iterations.

To understand how Grover's diffusion step works, check out this answer.

  • $\begingroup$ @leafkoi does that answer your question? $\endgroup$ Commented Sep 2, 2021 at 14:30
  • $\begingroup$ @christewizz Thanks for the answer, it does help a lot.But I am wondering a new question that for a superposition state which I know what basis state it consists but have no idea about the exact amplititude of each basis state , if I can build a diffuser or an approximate diffuser for Quantum Counting ?And what should I do if I want to get the amplititude of a basis state from the superposition state? $\endgroup$
    – leafkoi
    Commented Sep 3, 2021 at 1:35
  • $\begingroup$ @christhewizz: welcome to QCSE! I edited your answer so it used Latex for the equations instead of images. Please check this out so you can use this format in future posts! $\endgroup$
    – epelaez
    Commented Sep 3, 2021 at 9:50
  • 1
    $\begingroup$ Hi @epelaaez, thanks for editing, the question migrated from SO, where you can't use latex to qcse. That's why there were a lot of images instead of latex formulas. It looks a lot better now $\endgroup$ Commented Sep 3, 2021 at 11:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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