PauliSum reorders the qubits, possibly in a non-deterministic way

[burlemarxiste]

Description of the issue

When retrieving the terms of a PauliSum, the resulting PauliString may have their qubits reordered compared to what was their original order when added to the sum.

What is happening behind the scenes is that the Pauli string cirq.DensePauliString('XY').on(q0, q1) is added to the PauliSum, but may be turned into a cirq.DensePauliString('YX').on(q1, q0) when retrieving the first term of the sum. They represent the same operation indeed, but do not have the same representation and unitary.

As a result, everything based on PauliSum produces consistent results at the circuit level, but x and PauliSum() + x are not guaranteed to be equivalent at the representation and unitary level. In addition, PauliSum() + x might have an inconsistent representation over several calls.

How to reproduce the issue

import cirq
import numpy as np

qubits = cirq.LineQubit.range(2)
for string in ["XY", "YX"]:
  original_ps = cirq.DensePauliString(string).on(*qubits)
  in_sum_ps = list(cirq.PauliSum() + original_ps)[0]
  print(original_ps.dense(original_ps.qubits), in_sum_ps.dense(in_sum_ps.qubits))
  print(np.allclose(cirq.unitary(original_ps), cirq.unitary(in_sum_ps)))
  print(np.allclose(
      cirq.unitary(cirq.Circuit(original_ps)),
      cirq.unitary(cirq.Circuit(in_sum_ps)))
  )

Output

(cirq-py3) vagrant@ubuntu-focal:/vagrant/Cirq$ python3 pauli_sum_bug.py 
+XY +YX
False
True
+YX +YX
True
True
(cirq-py3) vagrant@ubuntu-focal:/vagrant/Cirq$ python3 pauli_sum_bug.py 
+XY +YX
False
True
+YX +YX
True
True
(cirq-py3) vagrant@ubuntu-focal:/vagrant/Cirq$ python3 pauli_sum_bug.py 
+XY +XY
True
True
+YX +XY
False
True
(cirq-py3) vagrant@ubuntu-focal:/vagrant/Cirq$ python3 pauli_sum_bug.py 
+XY +XY
True
True
+YX +YX
True
True

Output in Colab

+XY +YX
False
True
+YX +XY
False
True

Cirq version

Observed on 1.5.0.dev with python 3.11.9 (main, Apr 6 2024, 17:59:24) [GCC 9.4.0] in a dev environement. Non-deterministic behavior.

Observed on 1.5.0.dev20240531223815 with python 3.10.12 (main, Nov 20 2023, 15:14:05) [GCC 11.4.0] running in Colab. Deterministic behavior, but qubit order consistently swapped in the string repr and unitary.

[burlemarxiste]

Adding some pointers:

Each term of the PauliSum is turned back into a PauliString in _pauli_string_from_unit. The element of the Pauli string are stored in a frozenset which is not guaranteed to return items over several runs (just use the system hash, not stable with some python implementations). My suggestion is to always return the qubits in sorted order.

Suggested fix:
main...burlemarxiste:Cirq:qubit_order_in_sum

[NoureldinYosri]

cirq-sync: it makes sense to maintain the original qubit order. to do this we need to keep track of the original qubit order and use it when computing the unitary or decomposition