10
$\begingroup$

Consider this circuit:

enter image description here

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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:

enter image description here

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

enter image description here

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.

enter image description here

Improve this answer
$\endgroup$

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.