quantum-computing - Q#中如何实现格罗弗的扩散算子？

Answer 1

The diffusion operation is a bit tricky. I find it easiest to decompose it into pieces:

1. As you point out, it's much simpler to look at the diffusion operation in the X basis. If you apply H to every qubit before and after, then in the middle the uniform state looks like the 000...0 state.
2. The diffusion operation (in the X basis) is -1 on the 000...0 state, and the identity (+1) on all other basis states. The first step is to pick out the 000...0 state; I can do that with a multi-controlled X gate -- except I need to flip all of the qubits first from 0 to 1 (and vice versa), since controlled operations look for 1s, not 0s. Of course, after the controlled X I'll need to undo the flips.
3. To generate the -1, I can start with the ancilla in the |-> state, so that the X will turn it into -|->.
4. After I'm done with everything, I need to reset the ancilla so I can return it in the |0> state.

This all turns into:

// register is the Qubit[] that we want to apply the diffusion operation to
using (ancillae = Qubit[1])
{
  let ancilla = ancillae[0];

  X(ancilla); // Puts the ancilla into the |1> state
  H(ancilla); // And now into the |-> state

  ApplyToEach(H, register);  // Put the register qubits into the X basis
  ApplyToEach(X, register);  // Flip 0->1 and 1->0
  (Controlled X)(register, ancilla);  // Do the controlled flip of the ancilla
  ApplyToEach(X, register);  // Undo the flip
  ApplyToEach(H, register);  // Undo the basis change

  H(ancilla); // Put the ancilla back into |1>
  X(ancilla); // And back to |0> so we can return it
}

This is uncompiled code, so there might be some typos...