# Toffoli gate
a gate that uses 2 control qubits and one input qubit. It flips the input iff both control qubits are ones: $|a,b,c\rangle\rightarrow |a,b,c\oplus ab\rangle$ i.e., it is double-controlled-NOT
Properties:
- $\text{Toffoli}\ket{a,b,0}=\ket{a,b,ab}$ i.e., it is multiplication function
- Toffoli gate requires many resources from the quantum computer
- $\text{Toffoli}=\text{Toffoli}^\dagger$
- Toffoli permutes computational basis (convince yourself by checking its truth table)
- It does not belong to [[Clifford group (quantum gates)]]
- Circuit diagram
```
a: ───●───
│
b: ───●───
│
c: ───⊕───
```
## Implement Toffoli with T-gates
In quantum computers few gates are implemented in hardware and other gates are computed with circuits based on those few gates. Toffoli gate is implemented with few $2\times H,7\times T,6\times CNOT$ gates.
T-gate definition: $T\ket a:=\omega^a\ket a$ where $\omega=e^{2\pi i/8}$.
and $T^\dagger\ket a =\omega^{-a}\ket a$.
note: do not confuse T-gate with Toffoli gate.
Definition of $CCZ$:
$
CCZ\ket{a,b,c}:=\begin{cases}Z\ket c&, a=b=1 \\ \ket c &, \text{otherwise}\end{cases} =\ket{a,b,(-1)^{abc}c}=(-1)^{abc}\ket{a,b,c}
$
We will show that $\text{Toffoli}=(I\otimes I\otimes H)CCZ(I\otimes I\otimes H)$.
note that only $\ket c$ is changed by those gates.
If $a=b=1$, then $CCZ$ is $Z$ applied to $\ket c$ and therefore the total operations on $\ket c$ is $HZH$ which is $X$ i.e., $\ket c\mapsto X\ket c\mapsto\ket{1\oplus c}=\ket{ab\oplus c}$ .
Otherwise, $CCZ$ is $I$ applied to $\ket c$ and $\ket c\mapsto\ket{0\oplus c}=\ket{ab\oplus c}$.
We showed that $H\circ CCZ\circ H=\ket{ab\oplus c}$ and this is the output of Toffoli as required.
Now, we compute $CCZ$ using $T,T^\dagger,CNOT$.
First we use $CNOT$ to compute: $a\oplus b, b\oplus c, a\oplus c$ and $a\oplus b\oplus c$.
Then, compute
$
\begin{align}
&(T\otimes T\otimes T \otimes T^\dagger\otimes T^\dagger\otimes T^\dagger \otimes T)\ket{a,b,c,a\oplus b, b\oplus c, a\oplus c, a\oplus b\oplus c}=\\
&\omega^a\omega^b\omega^c\omega^{-a\oplus b}\omega^{-b\oplus c}\omega^{-c\oplus a}\omega^{a\oplus b\oplus c}\ket{a,b,c,a\oplus b, b\oplus c, a\oplus c, a\oplus b\oplus c}=\\
&\omega^{a+b+c-a\oplus b-b\oplus c-c\oplus a+a\oplus b\oplus c}\ket{a,b,c,a\oplus b, b\oplus c, a\oplus c, a\oplus b\oplus c}= \\
&\omega^S\ket{a,b,c,a\oplus b, b\oplus c, a\oplus c, a\oplus b\oplus c}
\end{align}
$
where $S=a+b+c-a\oplus b-b\oplus c-c\oplus a+a\oplus b\oplus c$.
$S$ is symmetric in $a,b,c$. The value of $S$ is determined by the number of ones values of $a,b,c$.
| Number of $1