How can a CNOT gate change the control qbit (e.g. in the Deutsch Oracle problem)?

Question

It is very confusing how the CNOT gate can change the properties of the controlled qubit (possibly because I am still stuck in the classical programming mindset):

Many books have explained the phenomenon using a $4\times 4$ matrix multiplication and tensor products to show how this happens. However, the math doesn't seem to agree because if I don't do the tensor product of the two qubits and instead just do the math separately by applying $2\times 2$ matrices to the top and bottom qubit based on what is happening and then tensor the two together in the end, the two methods don't agree.

Here is (what is in my mind) a simple example to show the mathematical error:

As we can see from the bottom qubit. The $X$ in the very beginning obviously transforms the $|0\rangle$ to a $|1\rangle$. The controlled dot doesn't do anything: it merely observes the bottom qubit in order to decide whether to apply the $X$ gate onto the top qubit. Thus, it does nothing to the bottom qubit. As everyone knows, all functions of quantum computing are inverses of each other. Hence, the 2 H gates cancel out. It thus makes no sense to me how the bottom qubit can be 100% off all the time when it should logically be "On" (and if we do out the matrices it will work out as such).

Thank you so much for your help and I apologize if this question is basic.

Answer 1

The controlled dot doesn't do anything: it merely observes the bottom qubit in order to decide whether to apply the 𝑋 gate onto the top qubit.

In the answer below, the qubit that appears first is the control qubit, it maps to the bottom qubit in your diagram, and the second one is the target qubit.

• The CNOT gate works on two qubits at once. You can't think of it's operation separately on the first and second qubit, and you can't do the math using two separate $2*2$ matrices.
• The definition of what CNOT does to a basis is this: $$CNOT(|00\rangle) = |00\rangle$$ $$CNOT(|01\rangle) = |01\rangle$$ $$CNOT(|10\rangle) = |11\rangle$$ $$CNOT(|11\rangle) = |10\rangle$$

Sure, when you look at the definition of the basis, it seems like CNOT doesn't do anything to the first qubit, and only observes the first and flips the second if necessary. But consider applying CNOT on a non-basis state:

$$CNOT(|+\rangle |0\rangle)$$ $$=CNOT \left(\frac{|0\rangle + |1\rangle}{\sqrt 2}|0\rangle \right)$$ $$=CNOT \left(\frac{|00\rangle}{\sqrt 2} + \frac{|10\rangle}{\sqrt 2}\right)$$ Now, exploiting the linear property of quantum gates, we have $$= \frac{|00\rangle + |11\rangle}{\sqrt 2}$$

Notice that the first qubit is not in the $|+\rangle$ state anymore, even though it was the qubit just being observed. It in fact does not have any pure representation. It has gotten entangled with the second qubit.

So CNOT does infact effect the control qubit in the sense that it ties it up with outcomes of the target qubit.

• Now, in your first example

After applying $X$ on both qubits, you have $|11\rangle$.

After applying $H$ on both qubits you have $|--\rangle$, or $\frac{|00\rangle - |01\rangle - |10\rangle + |11\rangle}{\sqrt 2}$.

After applying the CNOT on this qubit set, you have $\frac{|00\rangle - |01\rangle - |11\rangle + |10\rangle}{\sqrt 2}$ which you can factorise as $|+-\rangle$

And now applying the two $H$'s, you have $|01\rangle$. Hence the bottom qubit is 'off' and the top qubit is 'on'.

Answer 2

As everyone knows, all functions of quantum computing are inverses of each other. Hence, the 2 H gates cancel out.

Quantum gates all have inverses, but the inverse of a gate is not necessarily the same gate, though Hadamard gates, which are the ones being most considered here, are their own inverse. I'm not sure if by "2 H gates" you mean the two gates before the CNOT in the smaller diagram, which are on different qubits, or the two $H^{\otimes 2}$ gates flanking the CNOT in the larger diagram. In the former case, there's no cancellation since they are on different qubits. In the other case, they don't cancel because there is the CNOT between them and matrix multiplication is non-commutative: since $AB \neq BA$ is possible, you can't conclude $A^{-1}BA = A^{-1}AB = B$, and thus the two sets of Hadamards don't cancel out.

Now that we know that they don't just cancel out, you can derive that a CNOT with $H^{\otimes 2}$ flankings actually together make another CNOT with swapped control and target qubits. First, here is the conceptually simple but really tedious matrix multiplication of that:

$$\frac{1}{4}\begin{bmatrix}1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{bmatrix} \begin{bmatrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0\end{bmatrix} \begin{bmatrix}1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{bmatrix} = \frac{1}{4}\begin{bmatrix}1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{bmatrix} \begin{bmatrix}1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & -1 & -1 & 1 \\ 1 & 1 & -1 & -1\end{bmatrix} = \begin{bmatrix}1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0\end{bmatrix}$$.

With $a\left|00\right> + b\left|01\right> + c\left|10\right> + d\left|11\right> = \begin{bmatrix} a \\ b \\ c \\ d \end{bmatrix}$, we see the original in the flank swaps the probability amplitudes of $\left|10\right>$ and $\left|11\right>$ (left qubit is control), while the new one swaps the amplitudes of $\left|01\right>$ and $\left|11\right>$ (right qubit is control).

A harder but interesting and less tedious way to recognize this is through the symmetry of the controlled-$Z$ gate, as described in page 5 of https://arxiv.org/pdf/1110.2998.pdf. A controlled-$Z$ gate's control and target qubits are indistinguishable since the only probability amplitude in computational basis that changes is the sign flip of the probability amplitude of $\left|11\right>$. However, if one of the qubits in the controlled-$Z$ has Hadamards flanking it, they together are a CNOT with the Hadamard-flanked qubit being the target. Add the $H^{\otimes 2}$ on both sides to this CNOT and you have the "control" qubit of the controlled-$Z$ gate with a Hadamard behind and in front of it, and the "target" qubit with two on each side. The two Hadamards on each side for that qubit cancel out since there is nothing between them, so it ends up with a controlled-$Z$ with Hadamards behind and in front of what we previously noted as the control, but, since a controlled-$Z$ doesn't distinguish control and target, that is instead the target of a CNOT due to the Hadamards, and we have the switch.

Answer 3

I am not sure what the second question is about, but in the first one you are probably inquiring about the concept of "phase kickback":

Why does the "Phase Kickback" mechanism work in the Quantum phase estimation algorithm?