FullPeepholeOptimise does not preserve Connectivity although allow_swaps=False

[nquetschlich]

Hi,

I think I may found a case (using pytket v1.11.1) where the FullPeepholeOptimise compilation pass did not preserve the connectivity although allow_swaps=False is set.

Here is the code leading to valid_connectivity(...) returning False:

from pytket import architecture, OpType
from qiskit.providers.fake_provider import FakeMontreal
from pytket.passes import (
    RoutingPass,
    auto_rebase_pass,
    PlacementPass, 
    FullPeepholeOptimise
)
from pytket.placement import LinePlacement
from pytket.qasm import circuit_from_qasm_str

cmap = FakeMontreal().configuration().coupling_map
arch = architecture.Architecture(cmap)
native_gate_set_rebase = auto_rebase_pass({OpType.Rz, OpType.SX, OpType.X, OpType.CX, OpType.Measure})

qc_tket = circuit_from_qasm_str('OPENQASM 2.0;\ninclude "qelib1.inc";\n\nqreg q[11];\ncreg meas[11];\ncx q[4],q[3];\ncx q[4],q[3];\ncx q[3],q[2];\ncx q[4],q[2];\ncx q[3],q[2];\ncx q[4],q[2];\ncx q[2],q[1];\ncx q[3],q[1];\ncx q[2],q[1];\ncx q[4],q[1];\ncx q[2],q[1];\ncx q[3],q[1];\ncx q[2],q[1];\ncx q[4],q[1];\ncx q[1],q[0];\ncx q[2],q[0];\ncx q[1],q[0];\ncx q[3],q[0];\ncx q[1],q[0];\ncx q[2],q[0];\ncx q[1],q[0];\ncx q[4],q[0];\ncx q[1],q[0];\ncx q[2],q[0];\ncx q[1],q[0];\ncx q[3],q[0];\ncx q[1],q[0];\ncx q[2],q[0];\ncx q[1],q[0];\ncx q[4],q[0];\nccx q[1],q[7],q[8];\nccx q[2],q[8],q[9];\nccx q[3],q[9],q[10];\nccx q[4],q[10],q[6];\nccx q[3],q[9],q[10];\ncx q[6],q[5];\nccx q[2],q[8],q[9];\ncx q[6],q[5];\nccx q[1],q[7],q[8];\ncx q[6],q[5];\ncx q[6],q[5];\nccx q[6],q[0],q[5];\ncx q[6],q[5];\ncx q[6],q[5];\nccx q[6],q[0],q[5];\ncx q[6],q[5];\ncx q[6],q[5];\nccx q[6],q[1],q[5];\ncx q[6],q[5];\ncx q[6],q[5];\nccx q[6],q[1],q[5];\nccx q[1],q[7],q[8];\ncx q[6],q[5];\ncx q[6],q[5];\nccx q[6],q[2],q[5];\ncx q[6],q[5];\ncx q[6],q[5];\nccx q[6],q[2],q[5];\nccx q[2],q[8],q[9];\ncx q[6],q[5];\ncx q[6],q[5];\nccx q[6],q[3],q[5];\ncx q[6],q[5];\ncx q[6],q[5];\nccx q[6],q[3],q[5];\nccx q[3],q[9],q[10];\ncx q[6],q[5];\ncx q[6],q[5];\nccx q[6],q[4],q[5];\ncx q[6],q[5];\ncx q[6],q[5];\nccx q[6],q[4],q[5];\nccx q[4],q[10],q[6];\nccx q[3],q[9],q[10];\nccx q[2],q[8],q[9];\nccx q[1],q[7],q[8];\n')

native_gate_set_rebase.apply(qc_tket)
placer = LinePlacement(arch) 
PlacementPass(placer).apply(qc_tket)
RoutingPass(arch).apply(qc_tket)
native_gate_set_rebase.apply(qc_tket)
FullPeepholeOptimise(target_2qb_gate=OpType.TK2, allow_swaps=False).apply(qc_tket)
print(qc_tket.valid_connectivity(arch, directed=True))

In this case, three invalid operations were inserted:

for com in qc_tket:
    if len(com.args)>1:
        if not ((com.args[0], com.args[1]) in arch.coupling):
            print(com.args[0], com.args[1])

node[1] node[3]
node[8] node[3]
node[19] node[14]

If the FullPeepholeOptimise pass is not used, everything works as expected.

[CalMacCQ]

Hi, Thanks a lot for rasing this. One of us will take a look.

[yao-cqc]

Hi, FullPeepholeOptimise is not connectivity preserving even with allow_swaps set to false. This is because it uses a three-qubit synthesis that can introduce non-local gates, which may break connectivity constraints. You may want to experiment with other passes for post-routing optimisation, such as CliffordSimp(allow_swaps =False) and KAKDecomposition(allow_swaps=False).

[CalMacCQ]

I think it should be made a bit clearer to the user what the allow_swaps=False flag means. In the case of FullPeepholeOptimise does allow_swaps=False just prevent implicit swaps?

We do have FullPeepholeOptimise2Q which omits the three qubit squashing so this should preserve connectivity.

[yao-cqc]

I think it should be made a bit clearer to the user what the allow_swaps=False flag means. In the case of FullPeepholeOptimise does allow_swaps=False just prevent implicit swaps?

That's right, allow_swaps=False just prevent implicit swaps.

[nquetschlich]

I think it should be made a bit clearer to the user what the allow_swaps=False flag means. In the case of FullPeepholeOptimise does allow_swaps=False just prevent implicit swaps?

We do have FullPeepholeOptimise2Q which omits the three qubit squashing so this should preserve connectivity.

Thank you very much for pointing me to that optimization pass. I tried it out but it seems that even PeepholeOptimise2Q does not preserve the connectivity. In the attached code snippet, the pass leads to an invalid connectivity. If it is commented out, the connectivity is valid.

from pytket import architecture, OpType
from qiskit.providers.fake_provider import FakeMontreal
from pytket.passes import (
    auto_rebase_pass,
    CXMappingPass,
    PeepholeOptimise2Q
)
from pytket.placement import LinePlacement
from pytket.qasm import circuit_from_qasm_str

cmap = FakeMontreal().configuration().coupling_map
arch = architecture.Architecture(cmap)
native_gate_set_rebase = auto_rebase_pass({OpType.Rz, OpType.SX, OpType.X, OpType.CX, OpType.Measure})

qc_tket = circuit_from_qasm_str('OPENQASM 2.0;\ninclude "qelib1.inc";\n\nqreg q[11];\ncreg meas[11];\nry(0.5156200785337115*pi) q[0];\nry(0.5259212361027874*pi) q[1];\nry(0.5311490773594357*pi) q[2];\nry(0.5256341606456719*pi) q[3];\nry(0.48185482198855123*pi) q[4];\nry(0.3749999999999992*pi) q[5];\nx q[6];\nx q[7];\nx q[8];\ncx q[4],q[3];\nry(0.2821957516304727*pi) q[3];\ncx q[4],q[3];\ncx q[3],q[2];\nry(0.08637935492365122*pi) q[2];\ncx q[4],q[2];\nry(0.03914176090442699*pi) q[2];\ncx q[3],q[2];\nry(0.17701662922799363*pi) q[2];\ncx q[4],q[2];\ncx q[2],q[1];\nry(0.02736736175234687*pi) q[1];\ncx q[3],q[1];\nry(0.006775452169044077*pi) q[1];\ncx q[2],q[1];\nry(0.05465580935192185*pi) q[1];\ncx q[4],q[1];\nry(0.028714621193555362*pi) q[1];\ncx q[2],q[1];\nry(0.00293352636765904*pi) q[1];\ncx q[3],q[1];\nry(0.014080566388901176*pi) q[1];\ncx q[2],q[1];\nry(0.10244302344157596*pi) q[1];\ncx q[4],q[1];\ncx q[1],q[0];\nry(0.007775077506101111*pi) q[0];\ncx q[2],q[0];\nry(0.001240726382892508*pi) q[0];\ncx q[1],q[0];\nry(0.015455307725784545*pi) q[0];\ncx q[3],q[0];\nry(0.004852553186980698*pi) q[0];\ncx q[1],q[0];\nry(0.000403832853185929*pi) q[0];\ncx q[2],q[0];\nry(0.002436170270185542*pi) q[0];\ncx q[1],q[0];\nry(0.030093570893275967*pi) q[0];\ncx q[4],q[0];\nry(0.016793599745076833*pi) q[0];\ncx q[1],q[0];\nry(0.0014820670980056393*pi) q[0];\ncx q[2],q[0];\nry(0.00024834944107055316*pi) q[0];\ncx q[1],q[0];\nry(0.002959396507430131*pi) q[0];\ncx q[3],q[0];\nry(0.008651443455406324*pi) q[0];\ncx q[1],q[0];\nry(0.0007488027442816633*pi) q[0];\ncx q[2],q[0];\nry(0.0043527049236130886*pi) q[0];\ncx q[1],q[0];\nry(0.05440168109764556*pi) q[0];\ncx q[4],q[0];\ncry(0.0*pi) q[0],q[5];\ncry(0.0*pi) q[1],q[5];\nx q[1];\ncry(0.0*pi) q[2],q[5];\nccx q[1],q[7],q[8];\ncry(0.0*pi) q[3],q[5];\nx q[1];\nccx q[2],q[8],q[9];\ncry(0.0*pi) q[4],q[5];\nx q[7];\nx q[1];\nccx q[3],q[9],q[10];\nx q[4];\nu1(0.0*pi) q[5];\nx q[7];\nx q[10];\nccx q[4],q[10],q[6];\nx q[4];\nu1(0.0*pi) q[6];\nx q[10];\nccx q[3],q[9],q[10];\ncx q[6],q[5];\nccx q[2],q[8],q[9];\nu3(0.09366343673910417*pi,0.0*pi,0.0*pi) q[5];\ncx q[6],q[5];\nx q[8];\nccx q[1],q[7],q[8];\nu3(3.9063365632608957*pi,0.0*pi,0.0*pi) q[5];\nu1(0.0*pi) q[6];\nx q[1];\nu1(0.0*pi) q[5];\nx q[7];\ncx q[6],q[5];\nx q[7];\nu3(3.9964731703751757*pi,0.0*pi,0.0*pi) q[5];\ncx q[6],q[5];\nu3(0.0035268296248242787*pi,0.0*pi,0.0*pi) q[5];\nccx q[6],q[0],q[5];\nu1(0.0*pi) q[5];\nu1(0.0*pi) q[6];\ncx q[6],q[5];\nu3(0.0035268296248242787*pi,0.0*pi,0.0*pi) q[5];\ncx q[6],q[5];\nu3(3.9964731703751757*pi,0.0*pi,0.0*pi) q[5];\nccx q[6],q[0],q[5];\nu1(0.0*pi) q[5];\nu1(0.0*pi) q[6];\ncx q[6],q[5];\nu3(3.9929463407503514*pi,0.0*pi,0.0*pi) q[5];\ncx q[6],q[5];\nu3(0.007053659249648525*pi,0.0*pi,0.0*pi) q[5];\nccx q[6],q[1],q[5];\nu1(0.0*pi) q[5];\nu1(0.0*pi) q[6];\ncx q[6],q[5];\nu3(0.007053659249648525*pi,0.0*pi,0.0*pi) q[5];\ncx q[6],q[5];\nu3(3.9929463407503514*pi,0.0*pi,0.0*pi) q[5];\nccx q[6],q[1],q[5];\nx q[1];\nu1(0.0*pi) q[5];\nu1(0.0*pi) q[6];\nccx q[1],q[7],q[8];\ncx q[6],q[5];\nx q[1];\nu3(3.9858926815007027*pi,0.0*pi,0.0*pi) q[5];\nx q[7];\nx q[8];\nx q[1];\ncx q[6],q[5];\nx q[7];\nu3(0.01410731849929705*pi,0.0*pi,0.0*pi) q[5];\nccx q[6],q[2],q[5];\nu1(0.0*pi) q[5];\nu1(0.0*pi) q[6];\ncx q[6],q[5];\nu3(0.01410731849929705*pi,0.0*pi,0.0*pi) q[5];\ncx q[6],q[5];\nu3(3.9858926815007027*pi,0.0*pi,0.0*pi) q[5];\nccx q[6],q[2],q[5];\nccx q[2],q[8],q[9];\nu1(0.0*pi) q[5];\nu1(0.0*pi) q[6];\ncx q[6],q[5];\nu3(3.971785363001406*pi,0.0*pi,0.0*pi) q[5];\ncx q[6],q[5];\nu3(0.0282146369985941*pi,0.0*pi,0.0*pi) q[5];\nccx q[6],q[3],q[5];\nu1(0.0*pi) q[5];\nu1(0.0*pi) q[6];\ncx q[6],q[5];\nu3(0.0282146369985941*pi,0.0*pi,0.0*pi) q[5];\ncx q[6],q[5];\nu3(3.971785363001406*pi,0.0*pi,0.0*pi) q[5];\nccx q[6],q[3],q[5];\nccx q[3],q[9],q[10];\nu1(0.0*pi) q[5];\nu1(0.0*pi) q[6];\ncx q[6],q[5];\nx q[10];\nu3(3.943570726002812*pi,0.0*pi,0.0*pi) q[5];\ncx q[6],q[5];\nu3(0.0564292739971882*pi,0.0*pi,0.0*pi) q[5];\nccx q[6],q[4],q[5];\nu1(0.0*pi) q[5];\nu1(0.0*pi) q[6];\ncx q[6],q[5];\nu3(0.0564292739971882*pi,0.0*pi,0.0*pi) q[5];\ncx q[6],q[5];\nu3(3.943570726002812*pi,0.0*pi,0.0*pi) q[5];\nccx q[6],q[4],q[5];\nx q[4];\nccx q[4],q[10],q[6];\nx q[4];\nx q[6];\nx q[10];\nccx q[3],q[9],q[10];\nccx q[2],q[8],q[9];\nccx q[1],q[7],q[8];\nx q[1];\nx q[7];\nx q[8];\nbarrier q[0],q[1],q[2],q[3],q[4],q[5],q[6],q[7],q[8],q[9],q[10];\nmeasure q[0] -> meas[0];\nmeasure q[1] -> meas[1];\nmeasure q[2] -> meas[2];\nmeasure q[3] -> meas[3];\nmeasure q[4] -> meas[4];\nmeasure q[5] -> meas[5];\nmeasure q[6] -> meas[6];\nmeasure q[7] -> meas[7];\nmeasure q[8] -> meas[8];\nmeasure q[9] -> meas[9];\nmeasure q[10] -> meas[10];\n')
diff = 27 - qc_tket.n_qubits
qc_tket.add_blank_wires(diff)

native_gate_set_rebase.apply(qc_tket)
CXMappingPass(arc=arch, placer=LinePlacement(arch), directed_cx=True, delay_measures=False).apply(qc_tket)
PeepholeOptimise2Q().apply(qc_tket)
native_gate_set_rebase.apply(qc_tket)

print(qc_tket.valid_connectivity(arch, directed=True))

Am I using the PeepholeOptimise2Q not as intended?

[yao-cqc]

Hey @nquetschlich, sorry for the confusion. I found the issue - turns out that PeepholeOptimise2Q isn't preserving connectivity because the allow_swaps flag for its underlying KAKDecomposition and KAKDecomposition passes are set to True.

To fix this, we can add an allow_swaps argument to PeepholeOptimise2Q and setting it to False preserves connectivity. But in the meantime, you can do the same thing by following these steps:

SynthesiseTket().apply(qc_tket)
KAKDecomposition(allow_swaps=False).apply(qc_tket)
CliffordSimp(allow_swaps=False).apply(qc_tket)
SynthesiseTket().apply(qc_tket)

[nquetschlich]

Hi @yao-cqc, thank you very much for finding out. I will use the work-around you suggested and change as soon as the updated PeepholeOptimise2Q pass is released.

[CalMacCQ]

Hi,

Now that pytket 1.16 is released you should be able to use the allow_swaps=False flag in FullPeepholeOptimise2Q

[github-actions[bot]]

This issue has been automatically marked as stale.