[Feature Request] Hutch++ trace estimator

[mfinzi]

🚀 Feature Request

An implementation of the Hutch++ trace and diagonal estimator

Motivation

The $1/\sqrt{n}$ convergence of the Hutchinson estimator can be very slow and it would be nice to have some alternative algorithms here

Pitch

Implementation going in here: https://github.com/wilson-labs/cola/tree/main/cola/algorithms and to be wired up into the cola.linalg.trace and cola.linalg.diag function via the method arguments

[Fr0do]

If we want to follow the original algorithm, option for Rademacher distribution should be available. It's possible to use xnp.sign(xnp.randn(...)), but adding xnp.rand to backends would make it less ambiguous.