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.

Guest Column: Quantum Finite Automata: From Theory to Practice / C. Mereghetti, B. Palano. - In: SIGACT NEWS. - ISSN 0163-5700. - 52:3(2021), pp. 38-59. [10.1145/3494656.3494666]

Guest Column: Quantum Finite Automata: From Theory to Practice

C. Mereghetti
Primo
;
B. Palano
Ultimo
2021

Abstract

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.
Quantum Computing; Automata Theory; Quantum Finite Automata
Settore INF/01 - Informatica
Article (author)
File in questo prodotto:
File Dimensione Formato  
3494656.3494666.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 5.97 MB
Formato Adobe PDF
5.97 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2434/885518
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact