Quantum algorithms for group convolution, cross-correlation, and equivariant transformations
arXiv:2109.11330 · doi:10.1103/PhysRevA.106.032402
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 (35)
- Quantum algorithm for solving linear systems of equations
- Variational Quantum Algorithms
- Quantum Convolutional Neural Networks
- Quantum Amplitude Amplification and Estimation
- Quantum principal component analysis
- Hamiltonian Simulation by Qubitization
- Simulating Hamiltonian dynamics with a truncated Taylor series
- Exact and Approximate Unitary 2-Designs: Constructions and Applications
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- Group Equivariant Convolutional Networks
- Tensor field networks: Rotation- and translation-equivariant neural networks for 3D point clouds
- Absence of Barren Plateaus in Quantum Convolutional Neural Networks
- Quantum algorithms for algebraic problems
- Quantum speedup of Monte Carlo methods
- Hybrid Quantum-Classical Convolutional Neural Networks
- Preconditioned quantum linear system algorithm
- On the Generalization of Equivariance and Convolution in Neural Networks to the Action of Compact Groups
- DeepSphere: Efficient spherical Convolutional Neural Network with HEALPix sampling for cosmological applications
- Programming Languages for Scientific Computing
- Exploiting Cyclic Symmetry in Convolutional Neural Networks
- Universal Invariant and Equivariant Graph Neural Networks
- Equivariance Through Parameter-Sharing
- Convergence Conditions for Random Quantum Circuits
- Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
- Quantum Analog-Digital Conversion
- Quantum Algorithms for Deep Convolutional Neural Networks
- Lorentz Group Equivariant Neural Network for Particle Physics
- Duality and Recycling Computing in Quantum Computers
- Asymptotic Quantum Algorithm for the Toeplitz Systems
- Quantum convolution and quantum correlation algorithms are physically impossible
- Quantum Circulant Preconditioner for Linear System of Equations
- Quantum advantage for differential equation analysis
- Convolution and involution on function spaces of homogeneous spaces
- Efficient quantum circuits for Toeplitz and Hankel matrices
- Quantum algorithms for abelian difference sets and applications to dihedral hidden subgroups