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...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2024
|
| Online Access: | https://hdl.handle.net/1721.1/153940 |
| _version_ | 1824458320103079936 |
|---|---|
| author | Castelazo, Grecia Nguyen, Quynh T De Palma, Giacomo Englund, Dirk Lloyd, Seth Kiani, Bobak T |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Castelazo, Grecia Nguyen, Quynh T De Palma, Giacomo Englund, Dirk Lloyd, Seth Kiani, Bobak T |
| author_sort | Castelazo, Grecia |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T14:51:34Z |
| format | Article |
| id | mit-1721.1/153940 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2025-02-19T04:24:01Z |
| publishDate | 2024 |
| publisher | American Physical Society |
| record_format | dspace |
| spelling | mit-1721.1/1539402025-01-06T04:25:28Z Quantum algorithms for group convolution, cross-correlation, and equivariant transformations Castelazo, Grecia Nguyen, Quynh T De Palma, Giacomo Englund, Dirk Lloyd, Seth Kiani, Bobak T Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Research Laboratory of Electronics Massachusetts Institute of Technology. Department of Mechanical Engineering 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. 2024-03-25T19:05:38Z 2024-03-25T19:05:38Z 2022 2024-03-25T18:49:57Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/153940 Castelazo, Grecia, Nguyen, Quynh T, De Palma, Giacomo, Englund, Dirk, Lloyd, Seth et al. 2022. "Quantum algorithms for group convolution, cross-correlation, and equivariant transformations." Physical Review A, 106 (3). en 10.1103/physreva.106.032402 Physical Review A Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf American Physical Society American Physical Society |
| spellingShingle | Castelazo, Grecia Nguyen, Quynh T De Palma, Giacomo Englund, Dirk Lloyd, Seth Kiani, Bobak T Quantum algorithms for group convolution, cross-correlation, and equivariant transformations |
| title | Quantum algorithms for group convolution, cross-correlation, and equivariant transformations |
| title_full | Quantum algorithms for group convolution, cross-correlation, and equivariant transformations |
| title_fullStr | Quantum algorithms for group convolution, cross-correlation, and equivariant transformations |
| title_full_unstemmed | Quantum algorithms for group convolution, cross-correlation, and equivariant transformations |
| title_short | Quantum algorithms for group convolution, cross-correlation, and equivariant transformations |
| title_sort | quantum algorithms for group convolution cross correlation and equivariant transformations |
| url | https://hdl.handle.net/1721.1/153940 |
| work_keys_str_mv | AT castelazogrecia quantumalgorithmsforgroupconvolutioncrosscorrelationandequivarianttransformations AT nguyenquynht quantumalgorithmsforgroupconvolutioncrosscorrelationandequivarianttransformations AT depalmagiacomo quantumalgorithmsforgroupconvolutioncrosscorrelationandequivarianttransformations AT englunddirk quantumalgorithmsforgroupconvolutioncrosscorrelationandequivarianttransformations AT lloydseth quantumalgorithmsforgroupconvolutioncrosscorrelationandequivarianttransformations AT kianibobakt quantumalgorithmsforgroupconvolutioncrosscorrelationandequivarianttransformations |