Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
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.
