Quantum algorithms for group convolution, cross-correlation, and equivariant transformations
Grecia Castelazo, Quynh T. Thanh Nguyen, Giacomo De Palma, Dirk Englund, Seth Lloyd, Bobak T. Kiani · Physical Review A · 2022
Group convolutions and cross-correlations, which are equivariant to the actions of group elements, are commonly used to analyze or take advantage of symmetries inherent in a given problem setting. Here, we provide efficient quantum algorithms for performing linear group convolutions and cross-correlations on data stored as quantum states. Runtimes for our algorithms are poly-logarithmic in the dimension of the group and the desired error of the operation. Motivated by the rich literature on quantum algorithms for solving algebraic problems, our theoretical framework opens a path for quantizing many algorithms in machine learning and numerical methods that employ group operations.