Elias Combarro
University of Oviedo
Elías F. Combarro holds Master's degrees in both Mathematics and Computer Science, and a PhD in Mathematics. He is an Associate Professor at the Computer Science Department of the University of Oviedo (Spain). He has conducted research in Computability Theory, Text Categorisation and Computer-assisted Classification of Semifields. Currently, his research is focused on the application of Quantum Computing to the study of algebraic structures, in particular to the classification of finite-dimensional algebras.
Introduction
In this work, we present and compare several different quantum-based approaches for the problem of determining when a given finite-dimensional algebra is commutative. This is a practical problem of interest, for instance, in the computer-assisted classification of semifields.
A n-dimensional algebra over a field is determined by a list of n matrices of size n2 (called the multiplication constants or the structure matrices). In order to test whether the algebra is commutative or not, a certain symmetry relationship between the positions of these matrices must be tested.
Methods
We use three different approaches to construct quantum algorithms to test the commutativity of a finite-dimensional algebra: Grover’s search, quantum adiabatic computing and quantum walks.
In all the three cases, from a reversible circuit giving access to the multiplication constants of the algebra we obtain an oracle that checks wether a given position of the structure matrices is a witness of the non-commutativity of the mathematical object.
This oracle can be used in Grover’s search algorithm, turned into a Hamiltonian for the quantum adiabatic algorithm, and applied to mark vertices in the evolution of the different flavours of quantum walks that we compare in this work.
Results
While any classical (deterministic or not) algorithm requires checking a number of multiplication constants that is of the order of n3 to give the correct answer with high probability, we show that all the approaches studied in this work require only n3/2 queries to those constants (or time that is proportional to n3/2 in the case of the quantum adiabatic algorithm). We also prove that, in fact, no quantum algorithm can perform better when the number of queries is considered. The probabilities of success, however, vary from one method to another.
Discussion
In this work, he have studied several different quantum approaches for the problem of determining whether a given finite-dimensional algebra is commutative or not. All of them outperform their classical counterparts, but offer different success probabilities. Thus, depending on on the available resources, one or other may be preferable.
This work has been partially supported by MINECO-16-TEC2015-67387-C4-3-R and by MTM-2017-83506-C2-2-P.
