_parity() is O(n^2) with a list slice per iteration, on the hot path of every operator construction

[robertodr]

🤖 AI text below 🤖

What

_parity is a quadratic double loop that additionally allocates a fresh list slice on every outer
iteration.

src/monoprop/conversion_utils.py:117-135

def _parity(perm: Sequence[int]) -> int:
    parity: int = 1
    for i, x in enumerate(perm):
        for y in perm[i + 1 :]:          # new list allocated per i
            parity *= -1 if (x > y) else 1
    return parity

Why this is a problem

It sits on the hot path of every operator construction. MajoranaOperator._accumulate
(src/monoprop/majorana.py) calls Majorana.from_unsorted once per term, and that calls both
sorted(indices) and _parity(indices).

The worst case is PauliOperator.get_majorana_operator(): each term is first widened to the full
qubit count by _extend_pauli_string and mapped through _pauli_to_majorana, whose Jordan-Wigner
image spans up to 2 * num_qubits Majorana indices. So an N-qubit, T-term operator costs roughly
T · (2N)² / 2 Python-level comparisons plus 2N list allocations per term. At N = 100,
T = 10 000 that is ~2·10^8 comparisons in pure Python.

_parity is also called from _n_product once per element of an it.product over 2^len(term)
combinations, though the tuples there are short.

Suggested fix

Count inversions during a merge sort (O(n log n)), and fuse it with the sorted() call
Majorana.from_unsorted already makes — the sort and the parity are currently computed twice over the
same data.

Two properties must be preserved exactly:

1. Only strict inversions count. The current loop uses -1 if (x > y) else 1, so equal elements do
   not invert. _n_product feeds _parity sequences containing duplicates (they are cancelled
   afterwards by _remove_repeated_pairs), so a stable merge sort counting only x > y is required —
   anything counting >= changes results.
2. The docstring doctest stays. _parity([1, 2, 3, 4]) == 1 and _parity([2, 1, 3]) == -1 are
   executed by just doctest-py.

Validate the replacement against the current implementation on randomised inputs including duplicates
before deleting the old one.

Verification

• Differential test: random sequences (with and without duplicates) through both implementations.
• tests/test_majorana.py, tests/test_pauli.py, tests/test_fermi.py,
  tests/test_qiskit_conversion.py.
• just doctest-py.
• just bench serial before/after for the conversion-heavy cases.

---

Found by a code-reading review of the repository at 29a8050. No build tree was available, so the
analysis is from source inspection and should be confirmed by measurement.