Estimating the trace of matrix functions is a problem commonly encountered in physics. In this talk I will discuss exponential-time classical and quantum algorithms for the problem of trace-estimation, with the partition function as a specific example. I will present a classical algorithm for trace-estimation which improves in running-time upon the state-of-the-art by using a compression technique based on unitary 2-designs. I will then show that this technique also leads to a qubit-efficient quantum algorithm for estimating traces of block-encoded matrix functions. Lastly, I will talk about using block-encodings to estimate traces in the one-clean-qubit model.
This talk will be based on results from arXiv:2110.15466 and Phys. Rev. A 103, 032422.
Copyright. All Rights Reserved.