Implementing a controlled-controlled-U using controlled-U

Question

Suppose I know how to implement a 2 qubit gate $C-U$ (i.e controlled U), and I want to implement $CC-U$ using $C-U$ and other 1 or 2 qubit gates, is that possible?

Answer 1

Yes, generally it is possible by using a three qubits Toffoli gate (or series of Toffoli gates) to evaluate whether all controling qubits are in state $|1\rangle$. If this is a case then $C-U$ gate is applied.

Here is an example of $CC-H$ (i.e. controlled-controlled Hadamard gate):

If qubits $q_0$ and $q_1$ are in state $|1\rangle$, a first Toffoli gate return $|1\rangle$ to qubit $q_2$ and $C-H$ gate acts on qubit $q_3$. Eventually, you have Hadamard gate controlled by two qubits. Qubit $q_2$ is so-called ancila qubit and in the end it has to be in state $|0\rangle$ (so-called uncomputation). This is done by another Toffoli gate because Toffoli is inverse to itself.

If you want to implement general $C \dots C-U$ gate you can do it followingly:

Please note that in some cases you can construct a simpler circuit (i.e with less quantum gates and those being only two qubits). But generally the above mentioned approach works always.