Guest Column: Quantum Finite Automata: From Theory to Practice

We study how the adoption of the quantum paradigm leads to reducing the amount of hard- ware in computational devices with finite memory, both from a theoretical and a practical point of view. We theoretically design quantum finite automata for certain tasks, whose size is incredibly smaller with respect to that of their classical counterparts. Then, we report our physical implementation of these succinct quantum finite automata, which exploits the polarization de- gree of freedom of single photons and their manipulation through linear optical elements. This implementation provides concrete quantum components to be employed in some modular design frameworks we theoretically describe, aiming to build more sophisticated and succinct quantum finite automata.