Compiling non-nearest neighbor 2-qubit gate

[andyliphys]

For instance, if we want to compile a CNOT gate between qubit (0, 0) and qubit (1, 1) to Foxtail.

import cirq
circuit = cirq.Circuit()
circuit.append([cirq.CNOT.on(cirq.GridQubit(0,0), cirq.GridQubit(1,1))])
cirq.google.optimized_for_xmon(circuit, new_device=cirq.google.Foxtail)

It raises an error ValueError: Non-local interaction: GateOperation(Exp11Gate(half_turns=1.0), (GridQubit(0, 0), GridQubit(1, 1))). Is there a way to automatically add SWAP gates to the circuit, or other automatic methods, to compile the non-nearest neighbor 2-qubit gate?

[vtomole]

Is there a way to automatically add SWAP gates to the circuit, or other automatic methods, to compile the non-nearest neighbor 2-qubit gate?

Yes. But if we are talking about NISQ, SWAP gates are expensive. What we could do is "fake" CNOT((0,0), (1,1)) by compiling it qubits that are local CNOT((0,0), (1,1)) compiles to CNOT((0,1), (1,1)) . Maybe add a flag for it to make it explicit.

[andyliphys]

Yes. But if we are talking about NISQ, this is an expensive operation. What we could do is "fake" CNOT((0,0), (1,1)) by compiling it qubits that are local CNOT((0,0), (1,1)) compiles to CNOT((0,1), (1,1)) . Maybe add a flag for it to make it explicit.

I agree with you that those SWAP operations are expensive, and mapping the qubits alternatively is definitely a better solution for the simple example I quoted. Nonetheless, I am encountering situations with multiple 2-qubit gates and simply re-mapping cannot solve the problem of nonlocal 2-qubit gates. SWAP gates are unavoidable in those situations, and it would be nice if the compiler can adapt to those cases. The compiled circuits may be beyond the reach of near-term devices, but it is still useful to get some ideas on the gate count and circuit depth.

[bryano]

You might be interested in the cirq.contrib.acquaintance module. It doesn't automatically insert swaps to implement non-local gates, but rather gives a way of specifying an "acquaintance strategy" that swaps qubits around so that they're locally adjacent when you need them to be. If you know both the structure of the circuit and hardware, you can often do this in a way that doesn't introduce too much overhead, i.e. could be feasible on NISQ devices.

[andyliphys]

@bryano Thanks! Will try the module.

[Strilanc]

At the moment, we do not ever insert swap operations for the user. The reasoning is that this drastically changes the cost of the circuit, and we wouldn't be able to do a good job of it anyways. If you want to test non-local circuits, the current way to do that is by not specifying a device.

All that being said, I guess we could add something like a "RemoteCzViaSwaps" gate. Hmm..

[Strilanc]

For reference, here is a code to apply a gate across a path of qubits. If the path has length L, this circuit has depth L+7 (not accounting for CZ adjacency constraints).

def apply_gate_across_path(path: Sequence[cirq.QubitId],
                           gate: cirq.Gate) -> cirq.OP_TREE:
    k = len(path) // 2
    left, right = path[:k], path[k:][::-1]

    left_pairs = list(zip(left, left[1:]))
    right_pairs = list(zip(right, right[1:]))
    pairs = left_pairs + right_pairs
    kick_forward = [cirq.CNOT(a, b) for a, b in pairs],
    kick_backward = [cirq.CNOT(b, a) for a, b in pairs]
    matrix = cirq.unitary(gate, None)
    is_diagonal = matrix is not None and cirq.is_diagonal(
        matrix, tolerance=cirq.Tolerance(atol=0.00001))
    meetup = ([kick_backward, kick_forward]
              if is_diagonal
              else [kick_forward, kick_backward, kick_forward])

    return cirq.Circuit.from_ops(
        meetup,
        gate.on(left[-1], right[-1]),
        cirq.inverse(meetup),
        strategy=cirq.InsertStrategy.EARLIEST,
    ).all_operations()

c = cirq.Circuit.from_ops(apply_gate_across_path(cirq.LineQubit.range(10), cirq.SWAP))
print(c)

0: ───@───────X───────@───────────────────────────────@───────X───────@───
      │       │       │                               │       │       │
1: ───X───@───@───X───X───@───────────────────────@───X───X───@───@───X───
          │       │       │                       │       │       │
2: ───────X───@───@───X───X───@───────────────@───X───X───@───@───X───────
              │       │       │               │       │       │
3: ───────────X───@───@───X───X───@───────@───X───X───@───@───X───────────
                  │       │       │       │       │       │
4: ───────────────X───────@───────X───×───X───────@───────X───────────────
                                      │
5: ───────────────X───────@───────X───×───X───────@───────X───────────────
                  │       │       │       │       │       │
6: ───────────X───@───@───X───X───@───────@───X───X───@───@───X───────────
              │       │       │               │       │       │
7: ───────X───@───@───X───X───@───────────────@───X───X───@───@───X───────
          │       │       │                       │       │       │
8: ───X───@───@───X───X───@───────────────────────@───X───X───@───@───X───
      │       │       │                               │       │       │
9: ───@───────X───────@───────────────────────────────@───────X───────@───

d = cirq.Circuit.from_ops(apply_gate_across_path(cirq.LineQubit.range(10), cirq.CZ**0.5))
print(d)

0: ───X───────@───────────────────────────────────@───────X───
      │       │                                   │       │
1: ───@───X───X───@───────────────────────────@───X───X───@───
          │       │                           │       │
2: ───────@───X───X───@───────────────────@───X───X───@───────
              │       │                   │       │
3: ───────────@───X───X───@───────────@───X───X───@───────────
                  │       │           │       │
4: ───────────────@───────X───@───────X───────@───────────────
                              │
5: ───────────────@───────X───@^0.5───X───────@───────────────
                  │       │           │       │
6: ───────────@───X───X───@───────────@───X───X───@───────────
              │       │                   │       │
7: ───────@───X───X───@───────────────────@───X───X───@───────
          │       │                           │       │
8: ───@───X───X───@───────────────────────────@───X───X───@───
      │       │                                   │       │
9: ───X───────@───────────────────────────────────@───────X───

[andyliphys]

Understand. Thanks for the explanation and the sample code 👍

[dabacon]

Placement is challenging, and the acquaintance module in contrib is one answer to this. The question is whether we want other simple solutions for this for uses who want to build these circuits. I think @Strilanc suggestion is good and don't see a reason why this basic primitive should be put into device.

[95-martin-orion]

Paging @MichaelBroughton and @tanujkhattar: I feel like between Devices and Transformers this should have been resolved.

[95-martin-orion]

Discussed offline: qubit placement is now the responsibility of Feature Testbed. At lower levels, specific qubits chosen do not matter.