Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
I found some examples of implementing the oracle when the marked state is $|000\rangle$. But how can we know what gate we should use inside of the oracle?
Besides, for the part implementation, the example shows like this:
Mathematically, it should be $2|0\rangle\langle 0|-I$, but how can it be realized by X gates and controlled-Z gate?
The Boolean oracle applies X gates to the three qubits. This way the state |000⟩ becomes |111⟩. Then the multi-CX gate flips the target qubit if the state is |000⟩, from which you then get |0001⟩, or |x,y,z,0⟩ otherwise.
The phase oracle flips the phase of your qubits. So when you apply the X gates on the three qubits, what you are doing is essentially getting the state |111⟩ if it was |000⟩, and then mark it by changing the sign in front to negative, so -|111⟩. Then when you add the X gates again, you change it to -|000⟩.
So basically the phase oracle applies a phase in order to mark your result, whereas a boolean oracle stores the result in an additional qubit, so the choice of gates depends on what you are trying to achieve. For algorithms like Grover's, phase oracles are generally used.
Those two circuits are two different approches in implementing the oracle.
In the first one, the idea is to implement a function $f$ such that $f(x)=1$ iff $x=|000\rangle$. If the input is $|000\rangle$, then a NOT gate is applied to $q_a$ which is the ancilla qubit. If the ancilla qubit is prepared in state $|-\rangle$, then using phase kickback the sign of the amplitude of the state $|000\rangle$ is flipped.
In the second one, the sign of the amplitude of the state $|000\rangle$ is flipped directly through controlled Z gate, which adds an overall of phase of -1 if all control qubits are in state 1.
The reason why we have X gates is to be able to control them. If initially they are all 0, then applying the X gates all of them are in state 1 and we can apply the controlled operations. For instance oracle for 010 would have X gates only on the first and third qubits.
About your other question, think of the effect of that operation on an arbitrary basis state. If you apply it to state $|0\rangle$, then the output is $|0\rangle$ and the output is $-|x\rangle$ for any other input $|x\rangle$. Think about the converse, where you only flip the amplitude of state $|0\rangle$. Those two operations are indistinguihable and therefore the latter is implemented, which is exactly the same as the oracle implementation where $|000\rangle$ is the marked element. (Check this link:Gate corresponding to $-I$)
