by Gábor Ivanyos, Attila Pereszlényi and Lajos Rónyai (ELKH SZTAKI, BME)
The Theory of Computing Research Group of the Informatics Laboratory at ELKH SZTAKI has studied quantum algorithms for various computational problems. We outline two projects in this area: one in computational algebra and one in machine learning.
Computing with black box groups
We are investigating possible applications of quantum computing to algorithmic problems from algebra and arithmetic. Examples of algorithms of this kind include Shor's famous quantum algorithms for factoring integers and computing discrete logarithms. The method for the discrete logarithm actually works in black box groups with unique encoding of elements.
The notion of black box groups was introduced by Babai and Szemerédi to study the complexity of problems related to the structure of matrix groups. The elements of a black box group are encoded (represented) by binary strings and the group operations are given by oracles (also called black boxes). In order to capture factor groups, they allowed the same element to be represented by more than one string and they added a further oracle for testing equality with the identity element. In a recent manuscript [1], with our colleagues from France and Singapore, we studied the complexity of the discrete logarithm problem in an Abelian black box group with non-unique encoding of elements. We assumed encoding of the group elements by a covering group in a natural way. It turns out that in this setting the quantum query complexity becomes exponential. The same holds for the closely related, possibly easier, computational Diffie-Hellman problem, which is the following: we are given three elements of the group: g, ga and gb , where the exponents a and b are hidden, compute gab. In the decision version, four group elements are given: g, ga, gb , and gc and the task is to decide if gc=gab. We showed that if the elements of a cyclic group of order p are encoded by the elements of a covering group of rank two, then, while the computational Diffie-Hellman problem is hard even for a quantum computer, the decisional version can be solved in polynomial time with a classical algorithm. Curiously, this difference disappears in higher ranks: even with encoding by a group of rank three both the decisional and computational problems have exponential quantum query complexity.
Quantum- and classical machine learning
Recent results in quantum machine learning show that many proposed quantum algorithms do not have much benefit over classical algorithms. We investigated the quantum classifier of Schuld and Petruccione [Scientific Reports, 2018] that selects a weak learner according to a distribution based on how good they are. It can be interpreted as a stochastic boosting algorithm on a finite set of learners where the learners are determined in advance. We simplified their algorithm to the point where it is intuitively easy to give an equivalent classical algorithm. We showed that a simple classical randomised method achieves the same result without changing the time complexity. We also gave an even simpler, constant time classical algorithm. We showed that this quantum ensemble method has no advantage over classical algorithms.
Independently from our work, Abbas, Schuld, and Petruccione [Quantum Machine Intelligence, 2020] also showed that the ensemble method can be turned into a classical algorithm. Our construction, however, is arguably simpler and more direct, especially the constant time algorithm.
We further developed the idea and, as the main contribution of our paper [2], we proposed classical methods that are inspired by combining the quantum ensemble method with adaptive boosting. We compute two types of weights in an alternating way: one on the samples, representing how difficult they are to learn and one on the learners, representing how well they perform on the chosen samples. We considered only the case of binary classification, but the methods can be extended. In our experiments we had different implementations of the above idea. We tested the algorithms on publicly available datasets and we found them comparable to the AdaBoost algorithm, which is one of the most efficient meta machine learning algorithms.
References:
[1] G. Ivanyos, A. Joux and M. Santha: “Discrete Logarithm and Diffie-Hellman Problems in Identity Black-box Groups”, arXiv:1911.01662 [quant-ph].
[2] B. Daróczy, et al.: “Quantum Inspired Adaptive Boosting”, arXiv:2102.00949
Please contact:
Gábor Ivanyos and Lajos Rónyai
ELKH SZTAKI, Hungary
