Southwest Quantum Information and Technology

Classical and quantum algorithms for trace estimation

Presenting Author: Anirban Chowdhury, Institute for Quantum Computing
Contributing Author(s): Sergey Bravyi, David Gosset, Pawel Wocjan

Estimating the trace of matrix functions is a problem commonly encountered in physics. In this talk I will present improved exponential-time classical and quantum algorithms for the problem of trace estimation, with the partition function as a specific example. I will summarize techniques to evaluate traces of block-encoded operators on quantum devices. I will show that a compression technique based on unitary 2-designs leads to a qubit-efficient quantum algorithm for estimating partition functions. I will then discuss how the same compression idea also leads to a classical algorithm with improved running-time. Lastly, I will mention some complexity theoretic results regarding the hardness of this problem. The talk will be based on some results from arXiv:2110.15466.

Read this article online: https://arxiv.org/abs/2110.15466

(Session 4 : Thursday from 3:45 pm - 4:15 pm)