`cirq.optimize_for_target_gateset(circuit, gateset=cirq_ionq.IonQTargetGateset())` doesn't take advantage of ion trap's all-to-all connectivity

[vtomole]

The text book compilation of the Toffoli gate consists of 6 CX gates with a depth of 12. This is because textbook compilations don't take into account the connectivity of the device it compiles to. A pro of the Ion trap architecture is it's all-to-all connectivity. It seems like Cirq is not using that to compile to the best circuit suited for the ion trap.

import cirq
import cirq_ionq

circuit = cirq.optimize_for_target_gateset(
    cirq.Circuit(cirq.TOFFOLI(cirq.q(0), cirq.q(1), cirq.q(2))),
    gateset=cirq_ionq.IonQTargetGateset(),
)


print(circuit)
# prints
# 0: ───T───@──────────────@───────@──────────@──────────────
#           │              │       │          │
# 1: ───T───X───@───T^-1───X───@───X──────@───X──────@───────
#               │              │          │          │
# 2: ───H───T───X───T──────────X───T^-1───X───T^-1───X───H───


print(f"Depth: {len(circuit)}")
print(
    f"Number of CX gates: {len([op for op in circuit.all_operations() if isinstance(op.gate, cirq.CXPowGate)])}"
)
# prints
# Depth: 11
# Number CX gates: 8

[yinghui-hu]

I'm trying working on this issue. The root cause is that currently the three qubits gates, e.g. the CCZ gate only has one hard-coded decomposition, which does not apply to all-to-all connectivity. To solve this problems, there can be two approaches (we can implement either or both):

1. Support an alternative decomposition for all-to-all connectivity in these gates. And when IonQTargetGateset is used to decompose a circuit, use this alternative decomposition.
2. Add new qubit class that supports all-to-all connectivity, and decide which decomposition of these gates should be returned based on the connectivity between the qubits. Currently no qubit class (as I know) can achieve all-to-all connectivity between 3 qubits.

[tanujkhattar]

Support an alternative decomposition for all-to-all connectivity in these gates. And when IonQTargetGateset is used to decompose a circuit, use this alternative decomposition.

The way to add an alternative decomposition for a gate like CCZ, for this specific use case, would be to create a free function that accepts an instance of cirq.CCZ and returns a decomposed OP_TREE. Call this free function by overriding the _decompose_multi_qubit_operation method in the IonQTargetGateset, which is an instance of TwoQubitCompilationTargetGateset

[shawn-peng]

Hi, @yinghui-hu are you still working on this issue? I want to give it a try and continue your previous work.

[yinghui-hu]

I'm waiting for feedback from @tanujkhattar on #6095

[shawn-peng]

Thanks! @tanujkhattar @yinghui-hu do we need anything else on this issue or this is resolved by #6095?