# How to construct Deutsch's gate or $\pi/8$ rotations using Toffoli+Hadamard?

It is known that Toffoli and Hadamard are Quantum Universal.

My question is - how to construct (an approximation of) the Deutsch's gate or the $$\pi/8$$ rotation using Toffoli + Hadamard?

I've seen several implementations of the Toffoli gate using Hadamard, CNOT and $$\pi/8$$ gates, but none for the other direction.

Toffoli and Hadamard are computationally universal -- that is, they can be used to carry out any quantum computation. However, they do so by implementing quantum gates in an encoded way. Indeed, this is necessary since both Toffoli and Hadamard have only real entries, so there is no way to obtain quantum gates with complex entries, unless one uses some encoding (see the paper you linked). That means that Toffoli and Hadamard are not universal in the sense that you can use them to construct any gate. In particular, there is no way to actually construct the $$\pi/8$$ or the Deutsch gate (except for special angles), or to even approximate them.
• "Toffoli and Hadamard have only real entries", ok but this is just they simply way we write it. Effectively the Toffoli $T$, that the QC implements is an element of the $SU(8)$ and is rather $\exp(i\pi/8)T$, which has complex entries... – draks ... Apr 28 '20 at 11:14
• @draks... Did you read the Aharonov paper linked above? --- It is very clear that there are different ways to define universality, and Toffoli and Hadamard are not universal in the sense where I require to be able to approximate any gate. --- Note that what you say is just a global phase, which does not get you out of the problem that e.g. a $\pi/8$ gate has entries with different phases! – Norbert Schuch Apr 28 '20 at 13:22