The problem of inverting a matrix that represents group convolution and/or cross-correlation has been studied by Seth Lloyd team at MIT and at Waterloo University. The algorithm’s complexity does not depend on the sparsity of the matrix. Quantum Group Convolution is used to solve linear partial differential equations (PDEs) over domains that contain a certain symmetry (periodic PDE questions can be reformulated as cross-correlations). Achievements of polynomial speedups with respect to the dimension of the problem, while enjoying from a polylogarithmic dependence on the inverse precision.
Another Quantum Algorithm from Set Lloyd for estimating the matrix determinant based on quantum spectral sampling will be explored. The algorithm estimates the logarithm of the determinant of an n×n positive sparse matrix , exponentially faster than previously existing classical or quantum algorithms that scale linearly in n. The algorithm allows the efficient estimation of the partition function.
Extension of study of Quantum Group Convolution for Quantum Equivariant Neural Network.
Study of Quantum estimation of the matrix determinant to compute, for Gibbs sampling:
Arsalan Motamedi, Grecia Castelazo, Group convolution quantum algorithms: an application to PDEs, QTML 2024 Conference, 24–29 nov. 2024, University of Melbourne, https://indico.qtml2024.org/event/1/contributions/214/
Castelazo, Grecia and Nguyen, Quynh T. and De Palma, Giacomo and Englund, Dirk and Lloyd, Seth and Kiani, Bobak T., Quantum algorithms for group convolution, cross-correlation, and equivariant transformations, Phys. Rev. A, vol.106 ,issue 3, American Physical Society, Sept. 2022, https://link.aps.org/doi/10.1103/PhysRevA.106.032402
Cristopher Moore, Daniel Rockmore, Alexander Russell, Generic quantum Fourier transforms, ACM Transactions on Algorithms (TALG), Volume 2, Issue 4, pp. 707-723, October 2006, https://doi.org/10.1145/1198513.1198525
Castelazo, Grecia, Prospects for Quantum Equivariant Neural Networks, Master of Engineering in Electrical Engineering and Computer Science at the MIT, September 2022, https://dspace.mit.edu/handle/1721.1/147273
Wim van Dam, Sean Hallgren, and Lawrence Ip, Quantum Algorithms for Some Hidden Shift Problems, SIAM Journal on Computing, Vol. 36, Issue 3, 2006, https://epubs.siam.org/doi/10.1137/S009753970343141X
Andrew M Childs, Jin-Peng Liu, and Aaron Ostrander. High-precision quantum algorithms for partial differential equations. Quantum, 5:574, 2021, https://quantum-journal.org/papers/q-2021-11-10-574/pdf/
Arsalan Motamedi and Pooya Ronagh. Gibbs sampling of periodic potentials on a quantum computer. arXiv preprint arXiv:2210.08104 (to appear in ICML 2024), 2022
Childs, Andrew M. and van Dam, Wim, Quantum algorithms for algebraic problems, Rev. Mod. Phys., volume = 82, issue 1, pp.1-52, 2010, American Physical Society, https://link.aps.org/doi/10.1103/RevModPhys.82.1
Ronald de Wolf, Quantum Computing Lecture Notes, arXiv:1907.09415v5 [quant-ph] 16 Jan 2023, https://arxiv.org/abs/1907.09415
Alain Guichardet, La méthode des orbites : historique, principes, résultats, Leçons de mathématiques d’aujourd’hui, volume 4, chap. 2, Cassini, décembre 2010, https://store.cassini.fr/fr/le-sel-et-le-fer/70-lecons-de-mathematiques-d-aujourd-hui-vol-4.html?search_query=mathematiques+d%27aujourd%27hui&results=16
Gregory D. Kahanamoku-Meyer, John Blue, Thiago Bergamaschi, Craig Gidney, Isaac L. Chuang, A log-depth in-place quantum Fourier transform that rarely needs ancillas, arXiv:2505.00701v1 [quant-ph], https://doi.org/10.48550/arXiv.2505.00701
Gregory D. Kahanamoku-Meyer, Norman Y. Yao, Fast quantum integer multiplication with zero ancillas, arXiv:2403.18006v4 [quant-ph], https://doi.org/10.48550/arXiv.2403.18006
Vittorio Giovannetti, Seth Lloyd, Lorenzo Maccone, A quantum algorithm for estimating the determinant, arXiv:2504.11049v2 [quant-ph], https://doi.org/10.48550/arXiv.2504.11049
David Layden, Guglielmo Mazzola, Ryan V. Mishmash, Mario Motta, Pawel Wocjan, Jin-Sung Kim, Sarah Sheldon, Quantum-enhanced Markov chain Monte Carlo, arXiv:2203.12497v1 [quant-ph], https://doi.org/10.48550/arXiv.2203.12497
Timothe Presles, Cyrille Enderli, Gilles Burel, El Houssain Baghious, Quantum Computing for Partition Function Estimation of a Markov Random Field in a Radar Anomaly Detection Problem, arXiv:2501.01154v1 [cs.ET], https://doi.org/10.48550/arXiv.2501.01154