In a paper called On quantum circuits employing roots of the Pauli matrices, I found this figure, where I couldn't understand the equality in the circled circuits. I need an explanation of how the circuits in the circle are equal with any rules used in reduction. Especially the CNOT underlined in red - How it is reduced?
For circuit equalities I find using quirk with the state-channel duality super useful where you setup the inverse of a circuit, see the identity in the amplitude display and then play around with the gates then on the left side.
In the given equality this is my thinking:
I'm going to ignore the equivalent prefix of the two circuits
this circuit is CNOT gates, that permute the subspaces and phaser gates (T / S are all just phasing the |1> subspace of the given qubit) - you can think about "commuting" the phase gates over the CNOT gates in two ways: 1) the CNOT control commutes 2) if you have the same CNOT even times then the CNOT permutations even out, so you'll have an equivalent circuit => this explains why the S gate can be commuted over to the end
Now, if we ignore the phaser gates for a second, we get this circuit (see in quirk state-channel duality to play around with)
And the question becomes why is this equivalent to
We can remove the identities, after which the question becomes: Why is
this last one can be understood by the CNOT mirroring rule (rule VI in this paper):
adding two CNOTs is an identity
mirroring over the first CNOT results in adding the new CNOT
after which we can just commute the CNOTs to their places
I'm sure there's simpler explanations :)
The two CNOTs that have gone missing have been moved rightward until they reach the CNOT between the two top qubits. They are then moved through that CNOT, which cancels one of them out. The remaining one was then moved to the right side of the circuit using the fact that its control can travel unmodified through phasing operations (S, T) and paired CNOTs.
That being said, the decomposition you've relayed is not optimal. Because the two Toffoli operations share a target and a control, they can be merged into one Toffoli operation. Here's what that looks like:
And this can be decomposed into a circuit using four T gates (instead of eight) by using an ancilla: