qiskit
qiskit copied to clipboard
Qiskit
Optimise `SparsePauliOp.from_operator`
Summary
This rewrites the from_operator handling (again!) from the initial Rust implementation of the recursive matrix-addition form into an iterative approach that re-uses the same scratch memory all the way down. This is significantly faster, and allocates far less often, although in practice the peak heap memory usage will be not dissimilar.
The algorithm is rewritten to be a manual stack-based iteration, rather than a functional recursion. The size of a single stack entry in the iteration is one usize, which is drastically smaller than whatever per-function-call stack will have been used before.
Details and comments
This is the rewrite alluded to in #11133. Using the same timing script, the new graph looks like:
where the absolute timing of the the 10q operator is ~40ms compared to ~227ms, so it's a 5-6x speedup at that scale (for a fully dense operator). Decompositions of up to 4q operators are now entirely lost in the noise of the construction time of SparsePauliOp (which tbh probably says more about the overheads of the quantum_info module than anything else...).
Still no parallelism here, but honestly, I'm not even sure it's worth putting in the time to do that other than casual interest.
One or more of the the following people are requested to review this:
- @Eric-Arellano
@Qiskit/terra-core@kevinhartman@mtreinish
Pull Request Test Coverage Report for Build 10957420702
Details
- 278 of 302 (92.05%) changed or added relevant lines in 1 file are covered.
- 11 unchanged lines in 3 files lost coverage.
- Overall coverage increased (+0.009%) to 88.788%
| Changes Missing Coverage | Covered Lines | Changed/Added Lines | % |
|---|---|---|---|
| crates/accelerate/src/sparse_pauli_op.rs | 278 | 302 | 92.05% |
| <!-- | Total: | 278 | 302 |
| Files with Coverage Reduction | New Missed Lines | % |
|---|---|---|
| crates/accelerate/src/two_qubit_decompose.rs | 1 | 91.45% |
| crates/qasm2/src/lex.rs | 4 | 91.48% |
| crates/qasm2/src/parse.rs | 6 | 97.61% |
| <!-- | Total: | 11 |
| Totals | |
|---|---|
| Change from base Build 10949079071: | 0.009% |
| Covered Lines: | 73634 |
| Relevant Lines: | 82932 |
💛 - Coveralls
Now rebased over main. Apparently I touched a couple of unrelated comments at some point that I mistakenly thought were part of this PR not a previous one, but oh well.
Before looking into this very smart, efficient and complicated code, I looked into the tests, and found only one very simple test for the SparsePauliOp.from_operator method (which tests only operators which are 2-qubit Paulis with coefficient=1):
https://github.com/Qiskit/qiskit/blob/dcd41e9fcedd6f51fe725c25c4ed583c22bb3525/test/python/quantum_info/operators/symplectic/test_sparse_pauli_op.py#L148
Since this PR (as well the one before it #11133) replaced a simple code of about ~10 lines in Python by a quite complicated and much longer code in Rust, I would suggest to enhance the test code by some tests of the following form:
labels = ["XI", "YZ", "YY", "ZZ"] # it's better to provide a longer list of labels, preferably 3-4 qubits
coeffs = [-3, 4.4j, 0.2 - 0.1j, 66.12] # provide a random list of coefficients, include also complex numbers
target = np.zeros((4, 4), dtype=complex)
for coeff, label in zip(coeffs, labels):
target += coeff * pauli_mat(label)
op = SparsePauliOp.from_operator(Operator(target))
# assert that op and target are the same (up to a permutation)
There are also several methods that tests the to_matrix and to_operator methods - it's also possible to add a from_operator method to these tests (although all of them use the same parameters given above):
https://github.com/Qiskit/qiskit/blob/dcd41e9fcedd6f51fe725c25c4ed583c22bb3525/test/python/quantum_info/operators/symplectic/test_sparse_pauli_op.py#L239 https://github.com/Qiskit/qiskit/blob/dcd41e9fcedd6f51fe725c25c4ed583c22bb3525/test/python/quantum_info/operators/symplectic/test_sparse_pauli_op.py#L303
