In an actual quantum computer, are we designing circuits with Toffoli Gates and then using compilers or optimizers to remove redundancies so that we can use fewer qubits than a full Toffoli gates would require? Or are multiple gates composed by the compilers into a single quantum circuit?

Are these operations mathematically equivalent if you use Toffoli Gates or Fredkin gates, or is one gate easier for optimizers to work with?


2 Answers 2


I guess you assume that you can implement any quantum circuit using Toffoli gates only; this is not true.

Toffoli gate is classically universal, but not quantum universal. The importance of Toffoli gate in quantum information science is based on 2 facts:

  • Toffoli gate is classically universal, that is you can implement any classical circuit using Toffoli gates only;
  • Toffoli gate is reversible, so it is also a quantum gate.

The existence of Toffoli gate is a proof that you can implement any classical circuit using quantum circuit.

The notion of universal quantum set of gates is more subtle compared with classical case. A set of quantum gates is said to be computationally universal if it can simulate any quantum circuit with arbitrarily small error, and the simplest computationally universal set of quantum gates is Toffoli and Hadamard gates; see A Simple Proof that Toffoli and Hadamard are Quantum Universal

  • $\begingroup$ This is super-useful. Thanks. $\endgroup$
    – vy32
    Sep 30, 2020 at 13:45

It depends on what you mean by an "actual quantum computer". For arithmetic circuits, and circuits to compute cryptographic operations to act as oracles for Shor's and Grover's algorithm, Toffoli gates are essential and ubiquitous. In fact many papers count Toffoli gates as the main resource.

I think part of the reason for this is that a Toffoli gate almost acts as a stand-in replacement for an "AND" gate. If you use $X$, CNOT, SWAP, and Toffoli, it's very natural to design arithmetic circuits, since these gates have a natural action on bits. If you wanted to design arithmetic circuits with a different gate set, it would probably be very difficult because the action of the gates would be very unintuitive.

Since there doesn't seem to be any quantum architecture that can perform Toffoli gates directly (they must be built out of other gates), maybe you would want to design a circuit directly out of these other gates and it would be more efficient. But if you do this, you need to pick a gate set, and maybe quantum architectures change and that gate set is no longer efficiently implementable. So then you have an overhead to convert from another gate set anyway, just as you would have if you designed in Toffoli gates.

That said, recently there has been work assuming a Clifford+T gate set where the T gate is the most expensive, based on the surface code. Then it makes sense to try to find things that are more efficient than just Toffolis. Although, in a lot of the research I've seen, it uses more qubits than a regular Toffoli, to try to make the circuit faster or use fewer T gates.

  • $\begingroup$ Why are Toffoli gates used as the main resource, and not Fredkin gates? $\endgroup$
    – vy32
    Sep 27, 2020 at 22:23
  • $\begingroup$ Fredkin gates are less powerful than Toffoli gates: scottaaronson.com/papers/gates.pdf` $\endgroup$
    – Sam Jaques
    Sep 29, 2020 at 10:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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