Using Grover on entangled states

Question

I am trying to implement Grover's algorithm on an entangled state. The idea is that I will have a state $\sum_x\alpha_x|f(x),x\rangle$ and I want to measure the $x$, for which $f(x)=0$. Note that $f$ is a complicated function, that I want to assume to not know.

I started by considering a 4-qubit toy example, but I can't seem to get the result I expect: Assume we have the state $|\psi\rangle = \frac{1}{2}(|0011\rangle + |0110\rangle + |1001\rangle + |1100\rangle)$. I chose the first two and last two qubits to be opposite as an example.

So, the goal of my algorithm is that I want to increase the amplitude of the states, where the first two qubits are 0. In this example this is represented by the state $|0011\rangle$. The first step is a simple phase flip, which I implemented with a controlled gate, that simply flips the sign, whenever the first two qubits are both 0.

But then, I already struggle on how/where to implement a Grover step. The standard idea I wanted to go with, was to simply use Grover on the 4-qubit state $\frac{1}{2}(-|0011\rangle + |0110\rangle + |1001\rangle + |1100\rangle)$, which actually slightly increases the amplitude of the state I wanted but ends up giving me a mess of an output state. Basically, the other three (input) states get a negative phase and I get many more "mixed" states. With such a state, I wouldn't even know how to start a second iteration. I guess this messy state might have to do with the fact that my input state is not a superposition of all possible states and so the standard Hadamard basis change might not be right way to go, but I'm not really certain what I can do.

I also tried Grover on either qubit-pair separately, but that made things even worse!

Thank you for any help!

Answer 1

Grover’s search uses an equal superposition of all basis states in the search space both as its starting state and as a part of “reflection about the mean” step. So if you're searching among these 4 states, you need to have an operation that prepares this superposition from the $|0000\rangle$ state to start with, and then your "reflection about the mean" step will look as follows:

1. Use adjoint of the state prep operation
2. Reflect about the $|0000\rangle$ state
3. Use state prep operation again

I don't have a pointer to a good theory writeup on this on hand, but I have a code example - a Sudoku solver which encodes part of the constraints in the limitation of the search space. (The Grover's search implementation is ApplyGroversAlgorithmLoop.)