4
$\begingroup$

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."
$\endgroup$

3 Answers 3

3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Interesting analogies to another field. Swapping between integer registers on x86 is "free" too. $\endgroup$
    – TLW
    May 15 at 17:44
  • $\begingroup$ @TLW hmm? Surely you’d need some mov or cmp opcodes to swap ax and bx. Or are you referring to jumping around hard-coded registers of flipflops? $\endgroup$
    – Mark S
    May 17 at 3:34
  • 1
    $\begingroup$ @MarkS they're probably referring to register renaming en.wikipedia.org/wiki/Register_renaming or just to the fact that swapping two registers can be skipped by rewriting later assembly. $\endgroup$ May 17 at 5:36
  • $\begingroup$ @MarkS - there are many cases on modern x86 processors where MOV has "zero" latency, accomplished by just updating the register renaming as opposed to moving bits around. $\endgroup$
    – TLW
    May 17 at 23:11
  • 1
    $\begingroup$ @TLW thanks; this old guy hasn't been paying attention to newer x86. $\endgroup$
    – Mark S
    May 17 at 23:15
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ In the case of PRESENT cypher, which is a substitution-permutation based cipher, the SWAP gates work as in-between permutation layers and the measurement will be performed at the very end (after 31 rounds). So, in this case, shall we count SWAP gates towards the overall quantum cost? $\endgroup$ May 15 at 7:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.