Cost of SWAP gate

Question

We know that a SWAP gate needs three CNOT gates but I have seen papers which say that a SWAP gate can be achieved by necessary rewiring can are not counted towards the final quantum cost. I am confused about whether to count the SWAP gate (which accounts for the cost of 3 CNOT gates) or not to count its cost at all. This is necessary for the overall depth of the circuit and also gate count.

Example papers:

1. In Implementing Grover oracles for quantum key search on AES and LowMC, section 4.2 ShiftRow and RotByte, they said "we consider rewiring as free and do not include it in our cost estimates."
2. In Efficient Implementation of PRESENT and GIFT on Quantum Computers, section 3.1.3. Permutation of PRESENT Block Cipher, they said ". Otherwise, this can be implemented with qubits relabeling. Therefore, Swap gates are not counted as gate cost. Therefore, the quantum cost for Permutation of PRESENT block cipher is zero."

Answer 1

Swaps are never truly free. The papers you linked are just ignoring the cost of routing, and then hiding the cost of swapping in that ignorance.

We ignore all concerns of layout and communication costs for the Grover oracle circuit. [...] uncontrolled swaps are free, since the classical controller can simply track such swaps

Making it possible to ignore the cost of an operation is expensive. For example, the paper "A Game of Surface Codes" contains a strategy for running quantum circuits that allows you to ignore the cost of all Clifford operations. It pays for this by having every non-Clifford gate cover the entire computer (touching every qubit in the system). It's an elegant approach, and it feels really good to be able to ignore the cost of Cliffords... but paying that touch-everything cost really starts to hurt at larger scales (>10 magic state factories). For example, if you used this approach when factoring 2048 bit numbers, you'd easily double the space usage and 10x the running time compared to keeping operations local.

Some hardware architectures have all to all connectivity (e.g. ion traps), but that won't remain true as they scale up to thousands or millions of physical qubits. Routing costs cannot truly be ignored.

Answer 2

It's free in the sense that a quantum circuit with SWAP, CNOT, and one-qubit gates can be transformed into an equivalent circuit with the same number of CNOT and one-qubit gates, but where all SWAP gates are at the end of circuit. Those SWAP gates at the end can be skipped, since a measurement in the standard basis will just have swapped classical results.

In practice it's not free because quantum computers can have different connectivity between qubits (in the sense of CNOT availability). For example, Google's Sycamore has a grid-like connectivity between qubits. So that, CNOT between some qubits is not available as a single operation, but as a number of operations.

Answer 3

If the SWAP gate is right before a measurement, we can remove it and re-target the classical bit of the measurement instruction.

Qiskit does exactly this when you transpile your circuit with optimization_level = 3 using OptimizeSwapBeforeMeasure^[1] transpiler pass.