Geometric quantum machine learning of provably efficient quantum algorithms

Demonstrating problems and datasets where quantum machine learning shows a provably better performance than classical algorithms is important for understanding its capabilities and potential use-cases. We approach this challenge by designing classification problems for which there are quantum algorithms with known quantum-classical complexity separation. Using geometric quantum machine learning (GQML) guided by symmetries of data, we demonstrate efficient learning of optimal quantum algorithms. With this, we gain understanding of how to build high-performing quantum models and embed datasets in an equivariant way. Our first study focuses on Boolean function classification, where we incorporate symmetries to learn Simon's algorithm. This approach demonstrates that GQML allows to recover the corresponding circuit and perform classification with excellent generalization. The second study targets the analysis of bit sequences, or "barcodes," with the aim of capturing global correlations. Here, we show that geometric quantum machine learning can recognize these correlations using few examples, while classical approaches based on deep neural networks do not generalize. We link this learning advantage with the ability of quantum computers of solving the forrelation problem, and perform quantum similarity testing. Our results highlight the importance of symmetries in quantum machine learning and point to use-cases where efficient quantum learning is possible.