Skip to content

Improve the accuracy of Trotterisation with randomisation and commuting groups #596

@TysonRayJones

Description

@TysonRayJones

The function applyTrotterizedPauliStrSumGadget() effects an approximation of exp(i angle PauliStrSum) using higher-order Suzuki-Trotter decomposition. Users can improve its accuracy by increasing the order and reps parameters.

The base accuracy however can be improved either/both by:

  • randomising the effected order of the PauliStrSum terms within each repetition (as described here).
  • grouping PauliStrSum terms into commuting groups which, when exp(i term) within are effected contiguously, induce no Trotter error.

Note that optimally grouping commuting terms is known to be NP-hard, but there exist a myriad of greedy/heuristic terms to find suboptimal groups. For example this work greedily reduces the number of needed gadgets, offering both an accuracy and runtime improvement, and this work.

The applyTrotterizedPauliStrSumGadget() function can be improved by:

  • introducing randomisation, using the RNG in randomiser.cpp, which users can ergo control (to deterministically repeat a previous Trotter circuit) using routines like setSeeds()
  • pre-grouping PauliStrSum into (suboptimal) commuting groups. If sufficiently quick, this could be done each time the Trotter function is called.
  • pre-grouping could alternatively be done once, caching the commuting groups for re-use on subsequent Trotter invocation. This could be elegantly done via added a new int* groupSizes term, initially NULL. When applyTrotterizedPauliStrSumGadget() is first called, the .strings and .terms fields of PauliStrSum can be reordered, and .groupSizes heap-allocated to contain the number of contiguous terms in each group. When needed, the total number of groups can be runtime inferred by enumerating .groupSizes until its reduction equals numTerms.
    • An alternative, simpler design could preserve .strings and .terms ordering and add new fields .groupSizes, .groupIndices and .numGroups fields.

Beware that a new commuting-groups field will mean that an existing PauliStrSum must never have its fields directly modified, since this
might corrupt the groups.

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementunitaryhack2025Issues associated with challenges in unitaryHACK 2025

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions