cuPauliProp: questions on deduplication after operator application and on buffer copies per gate

Hi all,

I’m a master’s student working on GPU performance of Pauli propagation (Heisenberg-picture simulation with coefficient truncation), and I’m comparing approaches on an A100. cuPauliProp has been a very useful reference, thanks for making it available. I have a few questions about how to use it well and how it behaves, which I couldn’t answer from the documentation:

  1. Deduplication. The docs say deduplication works on a sorted Pauli expansion view, and the 0.5.1 release notes mention sorting during operator application. Is the intended pattern “sort the newly created terms, merge them into the already sorted ones, then reduce equal keys”, or is the whole expansion re-sorted per gate? Is there a recommended way to keep an expansion sorted across many gates so that each gate only pays for the new terms?

  2. Device-to-device copies. In a profile of a long rotation-gate circuit I see the expansion data copied device-to-device around each gate (in total about twice the size of each gate’s output). Is that the expected behaviour of out-of-place application with two expansion buffers, and is there an API pattern (e.g. reusing or swapping buffers) that avoids it?

  3. Workspace. Is there guidance on how large the workspace should be relative to the expansion capacity for best performance, and does a larger workspace change which algorithms are used?

  4. Sort order. What does sortOrder = INTERNAL mean in practice, and should it be preferred when only deduplication (not a specific order) is needed?

  5. Wide strings. How does performance scale with the number of qubits once the packed strings get wider (e.g. a few hundred qubits)? Is there a recommended configuration for that regime?

  6. 0.5.0 vs 0.5.1. The 0.5.1 notes say a sorting optimisation from 0.5.0 was disabled because of run-to-run variability. Roughly what kind of workloads was it affecting, and is it planned to come back?

  7. Sampling. Are there plans for Monte Carlo / resampling-based propagation (truncation by sampling rather than by coefficient threshold)?

Any pointers to talks, papers or examples that describe the design would also be very welcome. Thanks a lot!

Hi there,

Thanks for your interest in cuPauliProp - those are some fantastic questions!

  1. It is true that our current approach for deduplication sometimes entails sorting, and that a deduplicating operation upon a prior sorted expansion is sometimes faster than upon an unsorted one.

    However, we have exposed sorting and deduplication as independent parameters of the operator application functions. Their internal relationship is totally abstracted, so as a user, you don’t need to think about it - if you require deduplication, request that, sorting may be involved automatically. Only additionally request sorting if you actually need the property that the output expansion arrives in sorted order. The sort parameter itself is not intended as a performance parameter in the process of deduplication. There are in fact scenarios where it hurts performance to demand sorting on top of deduplication, such as when applying Clifford gates upon deduplicated expansions! So when in doubt, request keepDuplicates=0 but sortOrder=NONE, which will utilise optimisations specific to the operation, some analogous to what you mention with “only pays for the new terms”.

  2. The device-to-device copies are indeed an unavoidable consequence of the current out-of-place API, and occur even with our intended “buffer ping pong” pattern demonstrated in the examples. We intend to expose other API patterns in upcoming versions!

  3. The API is indeed deliberately designed such that larger workspaces could permit more memory-intensive optimisations, at the discretion of our internals. Within v0.5.1 and earlier however, there are no such pathways, so all sufficiently large workspaces yield identical performance.

  4. The INTERNAL sort order is a little tricky to understand right now in our current state of development, but best understood by thinking of it as an output of cupaulipropPauliExpansionGetSortOrder(). It informs you that the expansion is currently sorted, as may be relevant to the performance of subsequent operations, but does not disclose the ordering, which may be specific to the history of operations upon the expansion, or some internal decision.

    As an input parameter, the INTERNAL sort order is less clear - it can be understood as a demand that the expansion is to be sorted, but in an undisclosed/non-deterministic ordering, and so cannot be relied upon for establishing mutual orderedness as needed for expansion comparison, for example. Since it is forcing some kind of sort, passing INTERNAL sort ordering can actually worsen performance over NONE, if sorting under any ordering was otherwise unnecessary or non-beneficial for the operation (like in the Clifford example above). Thankfully it is not necessary to pass INTERNAL because NONE still licenses us to internally sort, when efficient. And further, as mentioned above, the sort parameter is decoupled from the deduplication parameter, so you can safely pass NONE and retain best deduplication performance.

    The utility of being able to pass an INTERNAL sort order is not yet fully realised in our API, and presently has no use. In a future version, we envision passing it may slow down an operation, but establish a postcondition which speeds up a sequence of subsequent operations, outweighing the slowdown. We will of course document and demonstrate this when implemented!

  5. We do not yet have a public performance model, and performance can be greatly impacted by your device, so alas it will be necessary to perform your own benchmarks to find the scaling in practice. I can say however that the asymptotic runtime costs of the Pauli propagation algorithmic paradigm in general scale linearly with the number of qubits.

  6. We believe the disabled sort optimisation was affecting expansions of “high average weight”, and was disabled since we observed potential performance regressions in more typical settings.

  7. We do have plans to expand the truncation schemes, but it is not yet concrete which approaches will come first.

Alas we do not have any online material describing our internal nor algorithmic designs. Note too we are in experimental stage, so more API and algorithmic / performance changes are expected in upcoming releases.

I hope this helps!
Tyson and team