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:

slide showing the math of cnot gate action on 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?

  • $\begingroup$ is the question about how to realise that that particular length-four vector can be written as tensor product of two length-2 vectors, or about why the CNOT seems to change the control qubit in this case? $\endgroup$
    – glS
    Commented Sep 9, 2019 at 13:39
  • $\begingroup$ @glS I'm looking for a generic way to factor the result, so that I can implement it using classical code. I'm thinking there are too possible way, one is to detect which qbit is changed, and handle each case. That would require knowing why the CNOT act the way it does. However, if there is a generic way to factor the vector without knowing one of the input, then that would be what I'm most interested in $\endgroup$
    – leloctai
    Commented Sep 9, 2019 at 15:06

3 Answers 3


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.

  1. 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.

  • $\begingroup$ Thank you for the answer. Is there a way to know the signs of $\psi^B$ using the first technique? $\endgroup$
    – leloctai
    Commented Sep 10, 2019 at 5:00
  • $\begingroup$ It seem that the sign does not matter for my case. $\endgroup$
    – leloctai
    Commented Sep 10, 2019 at 5:24
  • 1
    $\begingroup$ @leloctai sure, you also get the signs. Just remember that ket states are defined up to a global phase, thus $\psi^B$ and $-\psi^B$ represent the same state $\endgroup$
    – glS
    Commented Sep 10, 2019 at 8:19

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.


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


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.