Reorder terms of a Pauli operator before Trotterization

[altaris]

What should we add?

Background: If op is a Pauli operator, then the depth of the Trotterization of PauliEvolutionGate(operator, ...), as implemented in qiskit, depends on the order of the Pauli terms in op.

Suggestion: It would be nice to have the Trotterizer (e.g. qiskit.synthesis.LieTrotter) optimize the order of the terms first to produce shallower circuits.

I think finding the optimal "parallelization" is essentially a graph coloring problem. If you think this suggestion has merit, I'd be interested to tryyyyyyyyyy to implement it myself. I don't have much experience with qiskit's internals though.

Example: Let's consider the operator $H = Z_1 Z_2 + Y_2 Y_3 + X_3 X_4$. Note that $Z_1 Z_2$ and $Y_2 Y_3$ don't commute, $Y_2 Y_3$ and $X_3 X_4$ don't commute, but $Z_1 Z_2$ and $X_3 X_4$ do commute. The circuits qc1 and qc2 are both (approximate) implementations of $e^{-i H t}$, but as you can see, their depth differ:

op1 = SparsePauliOp(["XXII", "IYYI", "IIZZ"])
op2 = SparsePauliOp(["XXII", "IIZZ", "IYYI"]) 

dt = Parameter("δt")
gate1 = PauliEvolutionGate(op1, dt)
gate2 = PauliEvolutionGate(op2, dt)

qc1 = SuzukiTrotter(reps=1).synthesize(gate1)
qc2 = SuzukiTrotter(reps=1).synthesize(gate2)

print(qc1.draw())
print(qc2.draw())

q_0: ─────────────────────────────────■───────────
                     ┌──────────────┐ │ZZ(2.0*δt) 
q_1: ────────────────┤0             ├─■───────────
     ┌──────────────┐│  Ryy(2.0*δt) │             
q_2: ┤0             ├┤1             ├─────────────
     │  Rxx(2.0*δt) │└──────────────┘             
q_3: ┤1             ├─────────────────────────────
     └──────────────┘                             

q_0: ──■─────────────────────────────
       │ZZ(2.0*δt)   ┌──────────────┐
q_1: ──■─────────────┤0             ├
     ┌──────────────┐│  Ryy(2.0*δt) │
q_2: ┤0             ├┤1             ├
     │  Rxx(2.0*δt) │└──────────────┘
q_3: ┤1             ├────────────────
     └──────────────┘                

[Cryoris]

There is a more general compilation algorithm for Pauli evolutions, that takes into account what you're suggesting above: https://arxiv.org/pdf/2109.03371. IIRC, there's been prior work to implement this in Qiskit, I don't remember the details right now, but maybe @ajavadia has a better memory than me? 🙂

[Cryoris]

It seems the code I was referring to is outdated, if you want you can give it a try 🙂 Probably a good approach would be to add a function reorder_paulis or something to the ProductFormula synthesis class and re-order the pauli_list in the LieTrotter.synthesize and SuzukiTrotter.synthesize functions -- but let me know if you have other ideas!

[altaris]

I gave it a shot #12925