Optimizations in quantum circuits

Question

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?

Balint Pato · Answer

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

equivalent to

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 :)

Craig Gidney · Answer

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:

Optimizations in quantum circuits

2 Answers

Add your own answers!

Ask a Question