Experiments testing the commutativity of finite‐dimensional algebras with a quantum adiabatic algorithm. Issue 1 (20th February 2019) - Combarro, Elías F.; Ranilla, José; Rúa, Ignacio F.
Abstract : Determining whether a given algebra is commutative or not is important in the study of these algebraic objects in general and in the classification of semifields in particular. The best classical (ie, nonquantum) algorithm for this task has a running time that is of order O ( n 3 ), where n is the dimension of the algebra. To reduce this cost, in this paper, we study an approach to test the commutativity of a finite‐dimensional algebra using quantum adiabatic computing. Previous quantum algorithms solving the same problem were based on Grover's quantum search. The algorithm is built from a quantum oracle for the multiplication constants of the algebra. Results of the experiments carried out on a quantum computer simulator, based on two different annealing schedules, are presented, showing that a quantum adiabatic algorithm for the problem can determine the commutativity of finite‐dimensional algebras with one‐side bounded error with a running time of order O ( n 3 ), achieving a quadratic speedup over the classical case.