Why does quantum cost on gates formed from specific qubit gates not factor swap gates into account?

Question

I've been reading a number of quantum computation research papers that claim quantum cost's that do not add up.

For instance, in this paper - there is a claim that the MTSG gate is a quantum cost of 6. But to actually perform the computation, you need swap gates to get the stuff into the right order!

For instance, to even perform the first gate V(B, D), you'll need to do the following:

1) U = TENSOR(ID, SWAP, ID) 2) U = TENSOR(ID, ID, VGATE) 3) APPLY (U, R) 4) SWAP BACK

Am I getting something wrong here?

Answer 1

The paper just uses the swaps to make the diagram simpler. It allows the authors to represent the relevant operation as a single box covering four wires, instead of the six underlying operations, when making larger circuits.

Here is a screen capture of the definition of the "MTSG" gate from the paper (note: the $V$ gate is just a square-root-of-NOT gate):

(They managed to make them look pretty terrible...)

And here's a place where it's used:

If you expand each MTSG box in that larger circuit into the underlying 6 operations, and align the diagram onto a fixed set of wires, you'll find you can easily slide any implied swap gates out of the circuit.

(But do keep in mind that it's possible that the first practical quantum computers will have limitations like 'only nearest neighbors in a 2d grid can interact'. That would force the use of many swap gates.)