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.

  • 1
    $\begingroup$ I'm not sure I understand what "However, they do so by implementing quantum gates in an encoded way" means. If I have a circuit which uses a Deutsch gate, I shouldn't I be able to come up with another circuit that performs the same operation but using only Toffoli and Hadamard? $\endgroup$
    – GuyWberg
    Apr 27 '20 at 18:00
  • $\begingroup$ @GW1 No, that circuit will not actually implement the same gate. It will however implement something else which, upon measurement, will give exactly the meas. outcomes you would get from the circuit you were aiming for. As I said, it is easy to see it is impossible to actually get any gate, since there are only real number involved in Hadamard and Toffoli, and multiplying real numbers gives again real numbers. -- If you want to know what "implementing quantum gates in an encoded way" means, read the paper you linked to. If I remember it correctly, it was rather short and to the point! $\endgroup$ Apr 27 '20 at 18:16
  • $\begingroup$ "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... $\endgroup$
    – draks ...
    Apr 28 '20 at 11:14
  • 1
    $\begingroup$ @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! $\endgroup$ Apr 28 '20 at 13:22
  • 1
    $\begingroup$ @draks... I am delighted. In any case, you should read it. It is brief and insightful! $\endgroup$ Apr 28 '20 at 13:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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