Swap Network

In quantum compilation, the efficient networking of qubits and registers is a critical task when optimizing circuits. One of the key operators in this context is the Swap network (\text{SwapUp}), widely used in operators such QROM as described in this demo.

To understand the function of a Swap network, suppose we have N quantum registers of the same size (we assume that N is a power of 2), indexed as j \in \{0, 1, \dots, N-1\}. These registers form a composite state:

where the outer subscript j represents the position–or address–where the state |\phi_j\rangle is located.

The \text{SwapUp} operator takes as input an index state |k\rangle and the set of data registers. Its objective is to reorder the registers such that the specific state originally at position k is moved to the first position (j=0). Mathematically, this transformation is expressed as:

Inputs

• List of N quantum registers of size b.
• State acting in the \log_2(N) index-qubits.

Outputs

• New state where the k-th register is swaped to the first position for each basis state |k\rangle in the index wires.

Example

Let's use as an example a system of N = 4 registers with 2 control qubits and |k\rangle = |2\rangle. After applying the SwapUp operator, the output in the first registers would be |\phi_2\rangle

In this same example, we can build the decomposition with three \text{Controlled-Swap} gates

Each of those \text{Controlled-Swap} gates can be decomposed using one single Toffoli gate using the compute/uncompute pattern.

Note that it is common in the literature to find this operator represented as a SwapUp box on the register qubits with a control point on the index qubits; this should not be confused with a standard controlled operator. Here is a code implementation of the previous example:

def swap_blocks(ctrl, data):
    half = len(data) // 2
    for i in range(half):
        qml.CSWAP(wires=[ctrl, data[i], data[i + half]])

n_ctrl = 2
n_data = 2**n_ctrl
dev = qml.device("default.qubit", wires=n_ctrl + n_data)

@qml.qnode(dev)
def circuit():

    data_wires = list(range(n_ctrl, n_ctrl + n_data))
    
    # SwapUp operator
    for i in range(n_ctrl):
        current_range = data_wires[:len(data_wires) // (2**i)]
        swap_blocks(i, current_range)
        
    return qml.state()

print(qml.draw(circuit)())

0: ─╭●────╭●──────────┤  State
1: ─│─────│─────╭●────┤  State
2: ─├SWAP─│─────├SWAP─┤  State
3: ─│─────├SWAP─╰SWAP─┤  State
4: ─╰SWAP─│───────────┤  State
5: ───────╰SWAP───────┤  State

References

[1] "Trading T gates for dirty qubits in state preparation and unitary synthesis", Guang Hao Low et al., arXiv:1812.00954, 2018.