# Grover's diffusion on subset of input space

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})$$?

• 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$? Commented Jun 9, 2019 at 0:53

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

into:

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

• 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? Commented Jun 10, 2019 at 14:57
• I'm not sure I understand. What is the goal there? Commented Jun 11, 2019 at 1:09