# Quantum Toffoli gate equation

I was reading a research article on quantum computing and didn't understand the tensor notations for the unitary operations. The article defined two controlled gates.

Let $$U_{2^m}$$ be a $$2^m \times 2^m$$ unitary matrix, $$I_{2^m}$$ be a $$2^m \times 2^m$$ identity matrix. Then, controlled gates $$C_n^j(U_{2^m})$$ and $$V_n^j(U_{2^m})$$ with $$n$$ control qubits and $$m$$ target qubits are defined by $$C_n^j(U_{2^m})=(|j\rangle \langle j|) \otimes U_{2^m}+ \sum_{i=0,i \neq j}^{2^n-1}((|i\rangle \langle i| \ \otimes I_{2^m}$$

$$V_n^j(U_{2^m}) = U_{2^m} \otimes (|j\rangle \langle j|) + \sum_{i=0,i \neq j}^{2^n-1}( I_{2^m} \otimes (|i\rangle \langle i| ))$$ Then they say that $$C_2^j(X)$$ and $$V_2^j(X)$$are toffoli gates. Can someone explain the equations that are given and how does this special case be a Toffoli?

Here $$i$$ and $$j$$ are bit strings of size $$n$$. Correspondingly, $$|i\rangle$$, $$|j\rangle$$ are some basis vectors in $$2^n$$-dimensional space, that corresponds to $$n$$-qubit register.

Those controlled operations $$C$$ and $$V$$ act on $$(n+m)$$-qubit space. You can consider first $$n$$ qubits as control register and last $$m$$ qubits as target register. Now, $$C_n^j(U_{2^m})$$ applies unitary operation $$U_{2^m}$$ on the target register if control register is in the state $$|j\rangle$$ and applies $$I_{2^m}$$ (i.e. do nothing) otherwise. You can see this by applying $$C_n^j(U_{2^m})$$ on some vector $$|x\rangle|y\rangle$$ from the $$(n+m)$$-qubit space, where $$x$$ is some $$n$$-bit string:

$$C_n^j(U_{2^m}) |x\rangle|y\rangle = (|j\rangle \langle j|x\rangle) \otimes U_{2^m} |y\rangle+ \sum_{i=0,i \neq j}^{2^n-1}((|i\rangle \langle i| x \rangle) \otimes |y\rangle)$$

Here $$|i\rangle \langle i|x\rangle = 0$$ if $$x\neq i$$ and it equals $$|i\rangle$$ if $$x=i$$. Hence $$C_n^j(U_{2^m}) |x\rangle|y\rangle = |j\rangle \otimes U_{2^m} |y\rangle + 0 = |x\rangle \otimes U_{2^m} |y\rangle ~~\text{if}~~ x=j$$ and $$C_n^j(U_{2^m}) |x\rangle|y\rangle = 0 + |x\rangle|y\rangle = |x\rangle|y\rangle ~~\text{if}~~ x\neq j.$$

Gate $$V_n^j(U_{2^m})$$ is basically the same as $$C_n^j(U_{2^m})$$, though we consider first $$m$$ qubits as target and last $$n$$ qubits as control register in this case.

Now, if $$j=11$$ then $$C_2^j(X)$$ is exactly CCNOT gate on 3 qubits. Because we apply $$X$$ (i.e. negating the value) on the last qubit only if two first qubits are in $$|11\rangle$$ state.

• $y$ is an m bit string ? hence $|y \rangle$ lies in a$2^m$ dimensional hilbert space? Apr 12, 2019 at 16:32
• yes, that is it. Apr 12, 2019 at 16:46
• why is $\langle i|x\rangle=0$ if $x\neq i$ i see that it is an inner product between them but how is it zero because two binary strings dot product can still be non zero if they are not equal Apr 12, 2019 at 16:51
• $\langle a | b \rangle = \langle a_1 | b_1 \rangle \langle a_2 | b_2 \rangle ... \langle a_n | b_n \rangle$. This is zero if $a_i \neq b_i$ at least for some $i$. Apr 12, 2019 at 16:56
• i read that is $= a_1b_1+ a_2b_2+....+a_nb_n$ Apr 12, 2019 at 17:02