Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
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?
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.
