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.

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

Giacomo De Palma;
2022

Abstract

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.
2022
Grecia Castelazo; Quynh T. Nguyen; Giacomo De Palma; Dirk Englund; Seth Lloyd; Bobak T. Kiani
File in questo prodotto:
File Dimensione Formato  
Quantum algorithms for group convolution, cross-correlation, and equivariant transformations.pdf

accesso aperto

Tipo: Postprint
Licenza: Licenza per accesso libero gratuito
Dimensione 6.74 MB
Formato Adobe PDF
6.74 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/897666
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact