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!


1 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.)


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.