Learning Boolean functions with multi-controlled X gates
File(s)
Author(s)
Pham Ngoc, Viet
Type
Thesis
Abstract
As of late, both the fields of quantum computing and machine learning have experienced simultaneous developments. It is thus naturally that the interplay between these two fields is being investigated with the hope that they could benefit from one another. In this thesis, we explore one of the facets of this union called quantum machine learning. More accurately, throughout this thesis, the aim will be to learn Boolean functions using quantum circuits.
To do so, we first study a type of circuit, that we named tunable quantum neural network, exclusively made of multi-controlled X gates and we formally show that this type of circuit is able to express any Boolean function, provided that it is tuned correctly. We then devise a learning algorithm, that makes use of a specific quantum superposition to identify misclassified inputs. This algorithm intends to minimise the number of updates to the quantum circuit as it can be a costly operation. However, because of the large number of measurements required, it may not be practical.
To tackle this limitation and to guide our design of a learning algorithm that is indeed practical, we take advantage of the still ongoing field of quantum learning theory and design two other learning algorithms to be used in their respective framework. The first algorithm is used to train the network in the quantum probably approximately correct (QPAC) learning framework. By leveraging a quantum procedure called amplitude amplification, we show that this algorithm is efficient. The second algorithm also uses amplitude amplification but this time to train the network in the quantum exact learning framework with access to a uniform quantum example oracle. In both frameworks, we show that, in some cases, our algorithms perform better than what can be found in the literature.
To do so, we first study a type of circuit, that we named tunable quantum neural network, exclusively made of multi-controlled X gates and we formally show that this type of circuit is able to express any Boolean function, provided that it is tuned correctly. We then devise a learning algorithm, that makes use of a specific quantum superposition to identify misclassified inputs. This algorithm intends to minimise the number of updates to the quantum circuit as it can be a costly operation. However, because of the large number of measurements required, it may not be practical.
To tackle this limitation and to guide our design of a learning algorithm that is indeed practical, we take advantage of the still ongoing field of quantum learning theory and design two other learning algorithms to be used in their respective framework. The first algorithm is used to train the network in the quantum probably approximately correct (QPAC) learning framework. By leveraging a quantum procedure called amplitude amplification, we show that this algorithm is efficient. The second algorithm also uses amplitude amplification but this time to train the network in the quantum exact learning framework with access to a uniform quantum example oracle. In both frameworks, we show that, in some cases, our algorithms perform better than what can be found in the literature.
Version
Open Access
Date Issued
2023-08
Date Awarded
2023-11
Copyright Statement
Creative Commons Attribution NonCommercial Licence
License URL
Advisor
Wiklicky, Herbert
Publisher Department
Computing
Publisher Institution
Imperial College London
Qualification Level
Doctoral
Qualification Name
Doctor of Philosophy (PhD)