Is it possible to run grover's diffusion step on a subset of the possible input space?

By this, I mean is it possible to do the diffusion process with a state space isn't in a total superposition of all states.

Let's say I have a 2 qubit system in a equal superposition of states $\left|00\right>$, $\left|01\right>$ and $\left|10\right>$, but have exactly a 0 probability of measuring a $\left|11\right>$. Also, let's say I have a function $f$ that only outputs a 1 for the input 00. Is there a modification to Grover's where I can do the diffusion only on the $\left|00\right>$, $\left|01\right>$ and $\left|10\right>$ states and leave the $\left|11\right>$ state unchanged?

If that is possible, does it speedup the diffusion? Say I have a state with $n$ qubits but $2^x$ non-zero states where $x < n$, does this modified grover's algorithm still run in $\mathcal O(2^{n/2})$, or can it run in $\mathcal O(2^{x/2})$?

  • 1
    $\begingroup$ It seems like with your toy example you want to have a superposition of two qubits having the $\mathsf{NAND}$ being equal to $1$. You could calculate the $\mathsf{NAND}$ and post-select on the $\mathsf{NAND}$ of the two qubits being $1$, then run Grover's algorithm on the $\mathsf{NOR}$ being $1$. I think it would save you time on the Grover diffusion but it would still cost you time to post-select on the $\mathsf{NOR}$ being $1$. It's probably more efficient to run Grover diffusion conditioned on one output having $\mathsf{NOR}$ being $1$ and another output being $\mathsf{NAND}$ being $1$? $\endgroup$ Commented Jun 9, 2019 at 0:53

1 Answer 1


This can work. There's no reliance on powers of two or anything like that in the basic conception of the algorithm.

If $S$ is a subset of computational basis states with $N$ elements and you have a superposition: $$\left |\phi\right> = \frac{1}{\sqrt{N}}\sum_{x \in S}\left|x\right>$$ then basically all you need to do is change the classic Grover diffusion operator with the complete $n$-qubit uniform superposition $\left|\psi\right>$: $$2\left|\psi\right>\left<\psi\right| - I$$


$$2\left|\phi\right>\left<\phi\right| - 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\left|0\right>\left<0\right| - 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^{\dagger}$ (if they are not the same) where $B\left|0\right> = \left|\phi\right>$

From a fully general perspective, if determining whether something is in $S$ is itself difficult, implementing $B$ and having $\left|\phi\right>$ in the first place would void any advantage gained by subsetting.

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.

  • $\begingroup$ Awsome. Follow up question then. Let's say I had a function $g(x)$ that returns a 1 if $x \in S$ and 0 otherwise. If we assume I already have my qubits in $|\phi\rangle$. Could I use an extra qubit to conditionally apply $2|0\rangle\langle0| - I$ based on $|0\oplus g(x)\rangle$?Would this still leave all of the 0 elements of $|\phi\rangle$ as 0s? $\endgroup$ Commented Jun 10, 2019 at 14:57
  • $\begingroup$ I'm not sure I understand. What is the goal there? $\endgroup$ Commented Jun 11, 2019 at 1:09

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.