Qiskit / qiskit / 32872068892

88%

main: 88%

Build Type

push

github

Committed by web-flow

Commit Message

Allow `calloc`-like optimisations in `SparsePauliOp` allocations (#16830)

* Allow `calloc`-like optimisations in `SparsePauliOp` allocations

As of Rust 1.98, `vec![0.0; 2 * len]` lowers to OS/kernel-level
"allocate zero-filled" functions, but using a non-primitive type in the
`Vec` (like `Complex64`) doesn't permit this optimisation.  We want to
use `calloc` instead of manually writing zeros into the vector because
it often gets kernel-level support to have zero impact on pages that are
never written to, whereas manually issuing write calls across each row
guarantees that we have to page in everything.

This has a larger performance impact for large dense matrices with high
sparsity factors.

Using a benchmark script:

```python
import timeit
import numpy as np
from qiskit.quantum_info import SparsePauliOp

def make_sparse_list(num_qubits, num_terms, locality, rng):
    terms = []
    for _ in range(num_terms):
        indices = rng.choice(num_qubits, size=locality, replace=False)
        label = "".join(rng.choice(tuple("XYZ")) for _ in indices)
        coeff = complex(rng.normal(), rng.normal())
        terms.append((label, indices, coeff))
    return terms

rng = np.random.default_rng(42)
print(f"{'n':>3} {'terms':>6} {'locality':>8} {'time (s)':>10}")
configs = [
    (6, 10, 2),
    (10, 10, 2),
    (10, 50, 2),
    (10, 100, 4),
    (14, 10, 2),
    (14, 50, 2),
    (14, 100, 4),
]
for num_qubits, num_terms, locality in configs:
    terms = make_sparse_list(num_qubits, num_terms, locality, rng)
    op = SparsePauliOp.from_sparse_list(terms, num_qubits=num_qubits)
    reps, tot = timeit.Timer(op.to_matrix).autorange()
    print(f"{num_qubits:>3} {num_terms:>6} {locality:>8} {tot / reps:>10.4f}")
```

On main (as of aae0d80eaf), on a Macbook Pro M4 Max using 16 threads,
the timings were:
```text
  n  terms locality   time (s)
  6     10        2     0.0000
 10     10        2     0.0003
 10     50        2     0.0003
 10    100        4     0.000... (continued)

Coverage Stats

1 of 1 new or added line in 1 file covered. (100.0%)

16 existing lines in 2 files now uncovered.

114157 of 130115 relevant lines covered (87.74%)

987495.86 hits per line