# Minimum number of T gates needed to perform two overlapping Toffolis

Consider this circuit:

How many T gates are needed to implement it, in the stabilizer+T gate set? The circuit can use cliffords, measurement, classical feedback, ancilla qubits, and T gates. Only T gates cost.

I know how to do it with 8 T gates, but don't know an easy way to show it can't be done with 4.

Here's an intermediate result: it takes at least 5 T gates.

The T count of the overlapping Toffoli construction has to be exactly equal to the T count of two Toffolis that overlap at exactly one control, and those two Toffolis can be used to produce a state known to require 5 T states to produce.

This circuit with single-common-control Toffolis:

Is equivalent to this circuit with the overlapping Toffolis accompanied by various stabilizer operations:

I proved this using Quirk by using one circuit to uncompute the other under the state channel duality.

Also I did the reverse direction. Both operations can be used to perform the other, when stabilizer operations are free.

The single-overlapping-control circuit can be used to produce the state $$|CCZ_{123,145}\rangle$$ which, according to "Lower bounds on the non-Clifford resources for quantum computations", requires at least 5 T gates to produce. Therefore the T count is at least 5, but could be as high as 8.