How to factor the output of a CNOT acting on the input $|-,+\rangle$

Question

I am trying to implement the Deutsch oracle in classical computer, using direction from this talk.

There is this slide where they show how the CNOT gate modify 2 Hadamard transformed Qubits:

While I understand the math, I'm having trouble implementing the last part, where the resulting tensor product is factored into 2 qubits:

$ \frac{1}{2} \begin{pmatrix} 1\\ -1\\ 1\\ -1 \end{pmatrix} = \begin{pmatrix} \frac{1}{\sqrt2}\\ \frac{1}{\sqrt2}\\ \end{pmatrix} \otimes \begin{pmatrix} \frac{1}{\sqrt2}\\ \frac{-1}{\sqrt2}\\ \end{pmatrix} $

In the talk, they say the control qubit is supposed to stay the same, so it is simple to derive the target qubit. However, in this case, the control qubit is modified, while the target qubit is not.

So should I implement this by using 2 different calculation for each case (control/target qubit stay the same)? If so, how do I choose which calculation to use?

Or is there a better way to do this, using just a single calculation?

Answer 1

There are really two different questions here.

1. How can you figure out that a given output can be written as tensor product of two vectors?

This is equivalent to asking: how do you figure out whether an output is separable? For pure states, which is what you are considering, this is rather easy.

In your specific case (two qubits), you might simply notice that if $\psi=\psi^A\otimes \psi^B$ then there must be some specific relations between its elements. More specifically, in your notation, you should have $$\psi_2/\psi_1=\psi_4/\psi_3=\psi^B_2/\psi^B_1,\tag A$$ assuming $\psi_1,\psi_3,\psi^B_1\neq0$ (you should be able to work out the special cases with zeros without much difficulty).

In this way you get the value of $\psi^B_2/\psi^B_1$, which is enough to know the full $\psi^B$ remembering that it must a normalised vector. You can similarly work out the $\psi^A$ vector.

If condition (A) is not satisfied, then you know that the output cannot be written as a product state, i.e. does not admit this kind of tensor product decomposition.

A more general technique to check for separability of pure states is to compute the entanglement entropy, which is the Von Neumann entropy of the reduced states. Given a pure bipartite state $\psi_{ij}$ (I'm using the notation $|\psi\rangle\equiv\sum_{ij}\psi_{ij}|i,j\rangle$ and then identifying $|\psi\rangle$ with $\psi_{ij}$), the associated density matrix is $\rho_{ijk\ell}\equiv\psi_{ij}\bar\psi_{k\ell}$, and the reduced density matrix is $\rho_{ik}=\sum_j \rho_{ijkj}$, which then reads $\rho_{ik}=\sum_j \psi_{ij}\bar \psi_{kj}.$

In the case of the output being separable, you have $\psi_{ij}=a_i b_j$ for some (normalised) vectors $a_i,b_j$, and thus $\rho_{ik}=a_i \bar a_k$, whose entropy is zero. As it turns out, the Von Neumann entropy is zero if and only if the (pure) state is separable, and therefore this method gives you a definitive answer about the separability.

2. Why is the first qubit changed if the CNOT changes only the second one?

The simple answer is that the statement "with the CNOT the control qubit is supposed to stay the same" is only true in the computational basis. Indeed, as an example, by simply applying local Hadamard operations on the two qubits you can convert a CNOT into a CNOT in which control and target qubits are inverted. How to do this is shown for example in the Wikipedia page.

Answer 2

If you have already got, mathematically, to the point of having the vector $(1,-1,1,-1)/2$, you don't have to worry about the action of the controlled-not any more. You've already done that! All you have to do is factor the answer. Personally, I usually find the answer quite difficult to see when expressed in this way. Once you've got the answer you can easily verify that it's the right thing, however.

Instead, I would tend to write out the kets: $$ (|00\rangle-|01\rangle+|10\rangle-|11\rangle)/2. $$ You can start by grouping the terms on the first qubit: $$ |0\rangle(|0\rangle-|1\rangle)+|1\rangle(|0\rangle-|1\rangle), $$ where we recognise that the second qubit is in the same state in both parts, so this is the same as $$ (|0\rangle+|1\rangle)(|0\rangle-|1\rangle)/2. $$

---

Let me come back to the question about the action of the controlled-not, because even if you've already taken care of the maths, the conceptual aspect that you're asking about is hugely important in the context of quantum algorithms. Yes, the controlled-not should always be thought of as "do nothing if the control is 0, and flip the target if the control is 1", and in that sense, it sounds as if the control should never change. If the control was classical, it would never change. This should make sense because that description we've given is very much based on a classical intuition of what an input is like. But weird stuff can happen when you input a superposition. As you've observed, you get this effect, called 'phase kick-back', where the change ought to happen on the target (from a classical perspective), but actually it changes the control. You still get there by arguing very carefully in the standard way. You don't have to do anything special, and the answer will just come out. It's just that you do actually have to do the maths, and can't just hand-wave.

Answer 3

I don't think you can factor. There are many cases where the result of the gate will produce a combined CNOT output (4 numbers) that cannot be factored. I think most states between two qbits is entangled from our perspective. So you cannot trust in factoring. Instead, the four products remain in memory while your program writes the data to both of your inputs so that they now share the memory in different ways. Then when you apply the Hadamard to the lines after the CNOT, it actually operates on the 4 numbers as a whole to obtain the observed results.

I don't know the answer yet, but I am looking at the exact same problem and I think I know what you mean. I am seeing a connection between Cayley-Dickson constructions (complex numbers of high dimension) and probability states and manipulations. Gates also look like multiplications by (hyper) complex numbers.

Once you write a Cayley-Dickson calculator with tensor functions you can model the rotations of single gate manipulations. But I am also having trouble getting the CNOT gate to work. I suspect it is just a simple Cayley Dickson number something like this: 1/sqrt(4)*(1-i+j-k) or something simple like that.

CNOT works for me when producing a tensor and flipping the complex side.

I'm working on some code to do this here: https://metacpan.org/source/PEASWORTH/Tangle-0.01