Qiskit / qiskit / 8851171785

88%

Build Type

push

github

Committed by web-flow

Commit Message

Add Rust-based `SparsePauliOp.to_matrix` and Miri tests (#11388)

* Add Rust-based `SparsePauliOp.to_matrix`

This rewrites the numerical version of `SparsePauliOp.to_matrix` to be
written in parallelised Rust, building up the matrices row-by-row rather
than converting each contained operator to a matrix individually and
summing them.

The new algorithms are complete row-based, which is embarrassingly
parallel for dense matrices, and parallelisable with additional copies
and cumulative sums in the CSR case.

The two new algorithms are an asymptotic complexity improvement for both
dense and sparse matrices over the "sum the individual matrices"
version.  In the dense case, the cost goes from

        O(4 ** num_qubits * num_ops)

to

        O(4 ** num_qubits + (2 ** num_qubits) * reduced_num_ops)

where the first term is from the zeroing of the matrix, and the second
is from updating the elements in-place.  `reduced_num_ops` is the number
of explicitly stored operations after Pauli-operator uniqueness
compaction, so is upper-bounded as `4 ** num_qubits`.  (The Pauli
compaction goes as `O(num_ops)`, so is irrelevant to the complexity
discussion.) The CSR form of the algorithm goes as

        O(2 ** num_qubits * reduced_num_ops * lg(reduced_num_ops))

which (I think! - I didn't fully calculate it) is asymptotically the
same as before, but in practice the constant factors and intermediate
memory use are *dramatically* reduced, and the new algorithm is
threadable with an additional `O(2 ** num_qubits * reduced_num_ops)`
intermediate memory overhead (the serial form has only
`O(reduced_num_ops)` memory overhead).

The `object`-coefficients form is left as-is to avoid exploding the
complexity in Rust space; these objects are already slow and unsuited
for high-performance code, so the effects should be minimal.

* Add non-blocking Miri to CI

As we begin to include more `unsafe` code in the Rust-accelerated
components, it is becoming more important for us t... (continued)

Run Details

417 of 474 new or added lines in 3 files covered. (87.97%)

17 existing lines in 2 files now uncovered.

60920 of 68121 relevant lines covered (89.43%)

218071.94 hits per line