The disclosure describes various aspects of techniques for optimal fault-tolerant implementations of controlled-Za gates and Heisenberg interactions. Improvements in the implementation of the controlled-Za gate can be made by using a clean ancilla and in-circuit measurement. Various examples are described that depend on whether the implementation is with or without measurement and feedforward. The implementation of the Heisenberg interaction can leverage the improved controlled-Za gate implementation. These implementations can cut down significantly the implementation costs associated with fault-tolerant quantum computing systems.