I'm currently learning Simon's algorithm, from IBM Quantum Experiene. For the given string $s=11$, they display the implemented function $Q_f$ like this:

Image taken from https://quantum-computing.ibm.com/

Can someone explain to me, why the CNOT gates are arranged like this, for $s=11$? The way I see it, the outcome of the the qubits below, should be $f(x \oplus 11)$, but we still don't know about the implementation of $f$, just because we know $s$, if I'm not wrong. So how can we display $Q_f$ here?


1 Answer 1


Remember that we're not told what function $f$ is being implemented by this circuit, it is simply claimed that $f(x)=f(y)$ if and only if $y=x$ or $x\oplus 11=\bar{x}$. So, we need to identify what the function is, and then we can verify if it has that property.

The first thing we observe is that, actually, it's just a one-bit function repeated twice - the second qubit of the second register will always be equal to the first qubit of the second register. So, let's just think about the function applied to the first qubit. Remember what controlled-not does: enter image description here

so, if the bit values of the first register are $x$ and $y$, we compute $0\oplus x=x$ with the first controlled not, and $x\oplus y$ with the second. Now we can make a truth table for the function. If the two inputs are the same, the output is 0. If the two outputs are different, the outputs are 1. So, in both cases, the two inputs that give the same output are related to each other by $\oplus 11$, as required.

  • $\begingroup$ Wow, thanks so much! I finally understand it :P $\endgroup$
    – Robinbux
    Feb 14, 2020 at 13:11

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.