Recorded 26 January 2022. Anirban Chowdhury of the University of Waterloo presents "Classical and quantum algorithms for estimating traces and partition functions" at IPAM's Quantum Numerical Linear Algebra Workshop Abstract: 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. Learn more online at: http://www.ipam.ucla.edu/programs/workshops/quantum-numerical-linear-algebra/?tab=schedule