# 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$? – Mark S Jun 9 '19 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^*$$ (if they are not the same) where $$B\left|0\right> = \left|\phi\right>$$

From a fully general perspective, if your subset selection method is weird, like all prime-numbered states, I suspect realistically implementing $$B$$ (and having $$\left|\phi\right>$$ in the first place) on, say, IBM Q may be difficult to the point of voiding the advantage of the algorithm, since you'd have to include individual gates to zero the probability of all the specific irrelevant states in the implementation of $$B$$.

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? – Chase Roberts Jun 10 '19 at 14:57
• I'm not sure I understand. What is the goal there? – Joseph Geipel Jun 11 '19 at 1:09