The computational model of quantum finite state automata (QFA) is the quantum counterpart of classical finite state automata (CFA) [1]. A CFA is a machine capable to perform computations by reading the characters that make up a string and to modify its internal state depending on the character that are read and the current state of the machine. The final state of the CFA determines the output of the computation.
QFAs rely on the concept of quantum superposition to achieve the right result, i.e., at each step of the computation the machine state can be in a superposition of more than one state. This feature allows information to be manipulated in a surprising way by interference effects, leading to beneficial effects such as succinctness [2].
A number of efforts have been made on the theoretical side since the introduction of QFAs while, on the contrary, from the experimental side, a low number of implementations have been realized. However, given the extreme relevance of QFAs as a quantum computational model, their experimental implementation is of paramount importance to evaluate their actual capabilities.
The goal of this project is to bridge the gap between theoretical results and their experimental demonstration.
We propose to achieve this objective by means of a high-fidelity, highly phase stable photonic setup capable of performing quantum computation in the polarization degree of freedom of a single photon. Simulations and preliminary tests show that the setup is able to solve the acceptance problem of unary alphabets and the promise problems of binary alphabets, the latter having no experimental implementation so far.
Moreover, a modification of the setup by inserting a Pockels cell will allow to implement more complex problems based, for example, on ternary alphabets.
[1] Bhatia, A. S., & Kumar, A. (2019). arXiv preprint arXiv:1901.07992
[2] Gruska, J., Qiu, D., & Zheng, S. (2015). International Journal of Foundations of Computer Science, 26(03), 381-398.
The proposed project represents, without any doubt, a step forward in the state of the art in the topic of QFA. While many steps have been taken from a theoretical point of view, each of which has pushed knowledge of this topic further and further forward, the same has not happened from an experimental point of view. In fact, since the inception of QFA in 1997, the number of paths taken by theoretical research has been dramatically greater than those taken experimentally. This is evident if one looks at the number of theoretical and experimental papers: more than 200 theoretical papers have been published while only 2 experiments have been conducted on the same topic. This huge difference leaves a gap that must be filled. The present project fits exactly in this line of research and tries to fill, at least partially, the gap between theory and experiment. This task can be accomplished thanks to the innovative experimental setup that will be built in the quantum optics laboratories of the Department of Physics. The high level of control provided by the setup will allow to obtain completely new results, surpassing the last experimental ones.
In the light of this, the proposed research not only represents a step forward from the experimental point of view but can also give an input from the theoretical point of view. In fact, the possibility of verifying the predicted theoretical results can pave the way for further investigation of applicable algorithms that can solve practical problems. For this reason, the present project can be considered as an important step forward in the knowledge and effective implementation of QFAs.