I am trying to implement the Grover's search algorithm using Q# and I am not able to implement the oracle (black box) part for the search of state $|1010\rangle$. How to implement the controlled NOT gate using 5 qubits with 4 qubits (q[0] ... q[3]) used as the control qubits and q[4] as the target qubit in Q#?

Please correct me if this is wrong, I am trying to implement Grover's algorithm using 4 qubits where 3 qubits are for the states and the 4th qubit is the auxiliary qubit so the auxiliary bit should be the target qubit?


1 Answer 1


You can implement a controlled version of any gate in Q# using Controlled functor; for the oracles, you'll use something like Controlled X(controlQubits, targetQubit), where controlQubits is an array of qubits that have to be in 1 state for the X gate to be applied and targetQubit is the qubit to which the gate is applied.

Q# also has a neat library function ControlledOnBitString which allows to apply controlled version of the gate if the control qubits are in a state given by the bit string. So if you want to encode a specific state to use as control, like $|1010\rangle$ in your example, you can use

(ControlledOnBitString([true, false, true, false], X))(controlQubits, targetQubit);

You can see examples of implementing Grover's search using Q# in the GroverSearch kata (task 1.2 is almost exactly your example of looking for a state 1010).

  • $\begingroup$ thank you very much it works now. Can you please clarify my doubts on the implementation of the circuit for Reflecion over the mean and the final parts of Grover's Algorithm implementation $\endgroup$ Commented Jan 27, 2020 at 5:57
  • $\begingroup$ If you clarify what your doubts are... If you're converting marking oracle to phase oracle, or use the same technique for implementing reflections, then yes, you use auxiliary qubit as target qubit. You can see examples in the same kata. $\endgroup$ Commented Jan 27, 2020 at 6:18
  • $\begingroup$ I did not understand the part "use the same technique for implementing reflections" can you please clarify mam. $\endgroup$ Commented Jan 27, 2020 at 14:13
  • $\begingroup$ "Conditional phase shift" step of Grover's search can be implemented in a similar way to the oracle application using an auxiliary qubit with a marked state 0..0. That is shown in ConditionalPhaseFlip_Reference operation in the same kata. $\endgroup$ Commented Jan 27, 2020 at 17:41

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.