Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a circuit that has 4 wires and 2 following each other Toffoli gates.

I have permutation matrix for each Toffoli gate (A and B).

Do I have to multiply that 2 matrices to get the entire permutation matrix of that 2 Toffoli gates?

And if I do that is $A\times B$ or $B\times A$?

share|cite|improve this question
Don't Toffoli gates have three wires? Do these 2 Toffoli gates act on the same three wires or two different sets of three? – Peter Shor Mar 23 '13 at 17:36
I have 4 wires. One gate occupies 3 wires from above. The following gate occupies 3 wires from below. I have permutation matrices for both of them. I want to calculate the entire permutation matrix, which results of the work of these 2 toffoli gates. Thanks much in advance!!! – ABCD Mar 23 '13 at 17:40
One way to do it: take the Kronecker product of the permutation matrices for each of the Toffoli gates with the 2 $\times$ 2 identity matrix, to get two 16 $\times$ 16 matrices, and then multiply those. – Peter Shor Mar 23 '13 at 17:43
up vote 1 down vote accepted

Yes, of course !

This nevertheless suppose that no time is lost between the two gates, but it is a usual assumption in basic lectures. If the state vector $\left| \Psi_0 \right>$ enters at the left of the circuit, then reach the gate A, represented by matrix $A$, then the B one represented by matrix $B$, and end up at the right of the logic circuit as $\left| \Psi_1 \right>$, then the final state is $\left| \Psi_1 \right> = \left( B \cdot A \right) \left| \Psi_0 \right>$, since A applies first, then B.

In your case, I suppose $\left| \Psi_0 \right> = \alpha_{0000} \left| 0 0 0 0 \right> + \alpha_{0010} \left| 0 0 1 0 \right> + \alpha_{0100} \left| 0 1 0 0\right> + ... $ has 16 entries, since you have 4 wires. Each wire usually represents the time evolution of a single q-bit. A Toffoli gate is usually a 3 q-bits gate, so you have to correctly generalise the Toffoli gate given on the Wikipedia page. Well, it means that you must put extra diagonal 1's in front of the untouched q-bit. You also have to change block-wise for the second gate I presume. (Please tell me if this last point is unclear for you, it is simpler to understand on a black-board than on internet actually :-) !)

share|cite|improve this answer
Ok, you answered P.Shor question during my typing, it's what I expected, the only complication in your case is to find the second permutation matrix (supposing you're not afraid of $16 \times 16$ multiplication matrix of course :-). I let you playing with what I said. If you have further difficulties to find the second matrix, please tell us. – FraSchelle Mar 23 '13 at 17:52
Don't worry about that if you do not really understand. Kronecker product is an other word for tensor product = how to get one $4 \times 4$ matrix from two $2 \times 2$ matrix, say. I think you already did the job without thinking of the mathematical construction behind ;-). – FraSchelle Mar 23 '13 at 18:04
Thanks much!!!! – ABCD Mar 23 '13 at 18:28

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.