Ricerc@Sapienza

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.