Eliminate redundant commutation checks in lie_closure

[stevenkordonowy]

Feature details

In the following lie_closure code, there are many redundant combinations that are checked:

for ps1, ps2 in itertools.combinations(vspace.basis, 2):
  com = ps1.commutator(ps2)
  com.simplify()

The issue is that we do not need to always check all combinations from vspace.basis; many have been checked in previous epochs. As a simple example, if our basis is {A,B} and we find a linearly independent C = [A,B] in an epoch, we do not need to check [A,B] again.

Instead, we only need to take the commutation of an operator in the original generator set and one from the most recent epoch. See algorithm 1 in this paper:

Implementation

Here is an attempt at updating the code. Note the new variables orig, S_prev, and S_new in particular. In addition to checking if len(com) == 0, we also should check if not vspace.is_independent(com). It seems that add also does an independence check.

def lie_closure(
    generators: Iterable[Union[PauliWord, PauliSentence, Operator]],
    max_iterations: int = 10000,
    verbose: bool = False,
    pauli: bool = False,
    tol: float = None,
) -> Iterable[Union[PauliWord, PauliSentence, Operator]]:

    if not all(isinstance(op, (PauliSentence, PauliWord)) for op in generators):
        if pauli:
            raise TypeError(
                "All generators need to be of type PauliSentence or PauliWord when using pauli=True in lie_closure."
            )

        generators = [
            rep if (rep := op.pauli_rep) is not None else qml.pauli.pauli_sentence(op)
            for op in generators
        ]

    orig = PauliVSpace(generators, tol=tol)
    S_prev = PauliVSpace(generators, tol=tol)
    vspace = PauliVSpace(generators, tol=tol)

    epoch = 0
    new_length = len(vspace)

    while (new_length > 0) and (epoch < max_iterations):
        if verbose:
            print(f"epoch {epoch+1} of lie_closure, DLA size is {len(vspace.basis)}")

        S_new = PauliVSpace([], tol=tol)
        for ps1 in orig.basis:
            for ps2 in S_prev.basis:
                com = ps1.commutator(ps2)
                com.simplify()

                if len(com) == 0:  # skip because operators commute
                    continue

                # result is always purely imaginary
                # remove common factor 2 with Pauli commutators
                for pw, val in com.items():
                    com[pw] = val.imag / 2

                if not vspace.is_independent(com):
                    continue

                vspace.add(com, tol=tol)
                S_new.add(com, tol=tol)

        # Updated number of linearly independent PauliSentences from previous and current step
        new_length = len(S_new)
        S_prev = S_new
        epoch += 1

        if epoch == max_iterations:
            warnings.warn(f"reached the maximum number of iterations {max_iterations}", UserWarning)

    if verbose > 0:
        print(f"After {epoch} epochs, reached a DLA size of {len(vspace)}")

    res = vspace.basis
    if not pauli:
        res = [op.operation() for op in res]

    return res

How important would you say this feature is?

1: Not important. Would be nice to have.

Additional information

[CatalinaAlbornoz]

Thank you for your enhancement suggestion @stevenkordonowy ! 🙌

Let us know if you have any additional feedback or suggestions.

[CatalinaAlbornoz]

Hi @stevenkordonowy ,
Thanks again for your suggestion! Our team was very happy to see it. Would you be interested in creating a Pull Request to add your proposed solution?
We can guide you on the process in case you're unsure about how to do a pull request.