Efficient Gradient Estimation of Variational Quantum Circuits with Lie Algebraic Symmetries

Hybrid quantum-classical optimization and learning strategies are among the most promising approaches to harnessing quantum information or gaining a quantum advantage over classical methods. However, efficient estimation of the gradient of the objective function in such models remains a challenge due to several factors including the exponential dimensionality of the Hilbert spaces, and information loss of quantum measurements. In this work, we developed an efficient framework that makes the Hadamard test efficiently applicable to gradient estimation for a broad range of quantum systems, an advance that had been wanting from the outset. Under certain mild structural assumptions, the gradient is estimated with the measurement shots that scale logarithmically with the number of parameters and with polynomial classical and quantum time. This is an exponential reduction in the measurement cost and polynomial speed up in time compared to existing works. The structural assumptions are (1) the dimension of the dynamical Lie algebra is polynomial in the number of qubits, and (2) the observable has a bounded Hilbert-Schmidt norm.