  Various implementations of the Toffoli gate up to a relative phase have been
known for years. The advantage over regular Toffoli gate is their smaller
circuit size. However, their use has been often limited to a demonstration of
quantum control in designs such as those where the Toffoli gate is being
applied last or otherwise for some specific reasons the relative phase does not
matter. It was commonly believed that the relative phase deviations would
prevent the relative phase Toffolis from being very helpful in practical
large-scale designs.
  In this paper, we report three circuit identities that provide the means for
replacing certain configurations of the multiple control Toffoli gates with
their simpler relative phase implementations, up to a selectable unitary on
certain qubits, and without changing the overall functionality. We illustrate
the advantage via applying those identities to the optimization of the known
circuits implementing multiple control Toffoli gates, and report the reductions
in the CNOT-count, T-count, as well as the number of ancillae used. We suggest
that a further study of the relative phase Toffoli implementations and their
use may yield other optimizations.
