A Quantum Algorithm for Symmetry-Exploitation in Exact Diagonalization of Quantum Many-Body Systems

Grover’s search algorithm can be extended to a minimization procedure on a quantum computer. Here, we find a new application for this procedure – the symmetry-based size reduction of matrices corresponding to quantum many-body Hamiltonians before they are diagonalized. This is currently a memory/computational bottleneck on classical computers. In this case, the minimization problem cannot tolerate an approximate minimum ruling out variational quantum algorithms, and adiabatic minimization is unsuitable since there is no notion of a finite energy gap protecting the ground state during the evolution from the starting to the final state. Instead, Grover’s minimization procedure provides a reliable means to obtain a quadratic speedup over classical algorithms. We discuss both the theory and full circuit implementation of Grover minimization as applied to this problem. We find that the oracle for this problem only scales as poly-log in the size of the search space, in contrast to many oracles in proposed applications for Grover’s algorithm which scale polynomially. Further, we design an error mitigation scheme that significantly reduces the effects of noise on the computation, making it a plausible candidate for the Noisy Intermediate Scale Quantum era.