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

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

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-correl...

Full description

Bibliographic Details
Main Authors: Castelazo, Grecia, Nguyen, Quynh T, De Palma, Giacomo, Englund, Dirk, Lloyd, Seth, Kiani, Bobak T
Format: Article
Language:English
Published: American Physical Society 2024
Online Access:https://hdl.handle.net/1721.1/153940
Description
Summary: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.

Similar Items