Quantum algorithms for group convolution, cross-correlation, and equivariant transformations

Abstract

Group convolutions and cross-correlations, which are equivariant to the actions of group elements, are commonly used in mathematics 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 logarithmic in the dimension of the group thus offering an exponential speedup compared to classical algorithms when input data is provided as a quantum state and linear operations are well conditioned. 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.

References in corpus (9)

• Quantum algorithm for solving linear systems of equations
• Variational Quantum Algorithms
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Absence of Barren Plateaus in Quantum Convolutional Neural Networks
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• Lorentz Group Equivariant Neural Network for Particle Physics
• Quantum convolution and quantum correlation algorithms are physically impossible
• Quantum advantage for differential equation analysis
• Quantum algorithms for abelian difference sets and applications to dihedral hidden subgroups

Cited by in corpus (3)

• Efficient classical algorithms for simulating symmetric quantum systems
• On efficient quantum block encoding of pseudo-differential operators
• Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra