Consistent sparse list format in sparse operators #14067
Conversation
|
One or more of the following people are relevant to this code:
|
- use combine in test - fix comment
Yep that's definitely true, there's a lot of flexibility in how to implement these CX chains which we could optimize to maximize cancellations 🤔 |
|
@jakelishman, @Cryoris: I also think that it's a very interesting problem to consider how we can maximize cancellations. Both the way to create CX-chains and the ordering of terms seem very important on HamLib benchmarks, for example, we get significantly fewer cancellations if we call |
There was a problem hiding this comment.
I'm ok merging this in the short time frame; it's still a valid ordering. We should look into improvements in the Pauli-evolution decompositions, though, because Pauli-evolution ordering shouldn't be tightly coupled to this method - it should be ordering things itself for optimality, even if that means just re-ordering the observable itself.
* Consistent sparse list format in sparse operators * review comments - use combine in test - fix comment (cherry picked from commit 07e61c8)
Summary
Building a
PauliEvolutionGatefrom aSparsePauliOpandSparseObservablerepresenting the same Hamiltonian (both using only Paulis) currently does not generate the same circuit. Both are correct, but they are inconsistent: the CX chains in the Pauli evolution are just reversed. @alexanderivrii ran some benchmarks based on HamLib and found that, due to all our surprise, one ordering seems to be almost always result in less CX gates than the other. Somehow one order allows for better CX cancellations. The ordering comes back to what index order theto_sparse_listmethods return, which we chose opposite inSparseObservablethanSparsePauliOp, but we also could've chosen it to be consistent. Since there's now a performance impact, this PR changes to the consistent order.Details and comments
Here's the results of @alexanderivrii's benchmarks:
Another way to fix this would be to sort the indices and Paulis in the
PauliEvolutionbut this (a) comes at additional cost and (b) will not allow users to insert custom index orders (since they would get re-sorted). So changing the order which we picked for a more natural reading seems fine here to be more consistent (and get better gate decompositions).No reno since this was introduced in 2.0. I'm labelling this as bugfix/stable backport so we can fix this for 2.0.