Hacktoberfest 2026: le issue che i maintainer hanno segnato per ottobre, aperte e adatte ai principianti. Sfoglia le issue Hacktoberfest

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

Aperta
  • Qualcosa non va?
#196 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub

I maintainer di solito rispondono entro 1 giorno

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
4/5
Tempo stimato
3-5 giorni
Idoneità per principianti
47/100
Tipo di issue
Refactoring
Chiarezza
Specificata chiaramente
Stato di attività
Ferma
Stack tecnologico
python
Ambito
performance

Direzione di ricerca

Start with _parity in src/monoprop/conversion_utils.py and its callers in src/monoprop/majorana.py; compare the current behavior on randomized inputs, including duplicates. Check tests/test_majorana.py, tests/test_pauli.py, tests/test_fermi.py, and tests/test_qiskit_conversion.py, then run just doctest-py and just bench serial. Done means strict inversions and the doctest behavior are preserved, tests pass, and the conversion-heavy benchmark can be compared before and after.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

performance

🤖 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.

Lingua principale
C++
Stelle
52
Fork
2
Merge medio
22h 23m
PR unite (30g)
36

Preparare l'ambiente

Apri in Codespaces

Avvia il container di sviluppo del progetto nel browser, con il tuo account GitHub.

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di Algorithmiq/monoprop

Tutte le issue di Algorithmiq/monoprop

Issue simili

Altre issue su C++

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.