Unary Quantum Finite State Automata with Control Language
We study quantum finite automata with control language (<span style="font-variant: small-caps;">qfc</span>s), a theoretical model for finite memory hybrid systems coupling a classical computational framework with a quantum component. We constructively show how to simulate measu...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-02-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/14/4/1490 |
| _version_ | 1797299007862603776 |
|---|---|
| author | Carlo Mereghetti Beatrice Palano Priscilla Raucci |
| author_facet | Carlo Mereghetti Beatrice Palano Priscilla Raucci |
| author_sort | Carlo Mereghetti |
| collection | DOAJ |
| description | We study quantum finite automata with control language (<span style="font-variant: small-caps;">qfc</span>s), a theoretical model for finite memory hybrid systems coupling a classical computational framework with a quantum component. We constructively show how to simulate measure-once, measure-many, reversible, and Latvian <span style="font-variant: small-caps;">qfa</span>s by <span style="font-variant: small-caps;">qfc</span>s, emphasizing the size cost of such simulations. Next, we prove the decidability of testing the periodicity of the stochastic events induced by a given <span style="font-variant: small-caps;">qfc</span>. Thanks to our <span style="font-variant: small-caps;">qfa</span> simulations, we can extend such a decidability result to measure-once, measure-many, reversible, and Latvian <span style="font-variant: small-caps;">qfa</span>s as well. Finally, we focus on comparing the size efficiency of quantum and classical finite state automata on unary regular language recognition. We show that unary regular languages can be recognized by isolated cut point <span style="font-variant: small-caps;">qfc</span>s for which the size is generally quadratically smaller than the size of equivalent <span style="font-variant: small-caps;">dfa</span>s. |
| first_indexed | 2024-03-07T22:43:19Z |
| format | Article |
| id | doaj.art-26bcdaa8965a41ac83a757631010faad |
| institution | Directory Open Access Journal |
| issn | 2076-3417 |
| language | English |
| last_indexed | 2024-03-07T22:43:19Z |
| publishDate | 2024-02-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj.art-26bcdaa8965a41ac83a757631010faad2024-02-23T15:06:10ZengMDPI AGApplied Sciences2076-34172024-02-01144149010.3390/app14041490Unary Quantum Finite State Automata with Control LanguageCarlo Mereghetti0Beatrice Palano1Priscilla Raucci2Dipartimento di Informatica “Giovanni Degli Antoni”, Università degli Studi di Milano, Via Celoria 18, 20133 Milano, ItalyDipartimento di Informatica “Giovanni Degli Antoni”, Università degli Studi di Milano, Via Celoria 18, 20133 Milano, ItalyDipartimento di Informatica “Giovanni Degli Antoni”, Università degli Studi di Milano, Via Celoria 18, 20133 Milano, ItalyWe study quantum finite automata with control language (<span style="font-variant: small-caps;">qfc</span>s), a theoretical model for finite memory hybrid systems coupling a classical computational framework with a quantum component. We constructively show how to simulate measure-once, measure-many, reversible, and Latvian <span style="font-variant: small-caps;">qfa</span>s by <span style="font-variant: small-caps;">qfc</span>s, emphasizing the size cost of such simulations. Next, we prove the decidability of testing the periodicity of the stochastic events induced by a given <span style="font-variant: small-caps;">qfc</span>. Thanks to our <span style="font-variant: small-caps;">qfa</span> simulations, we can extend such a decidability result to measure-once, measure-many, reversible, and Latvian <span style="font-variant: small-caps;">qfa</span>s as well. Finally, we focus on comparing the size efficiency of quantum and classical finite state automata on unary regular language recognition. We show that unary regular languages can be recognized by isolated cut point <span style="font-variant: small-caps;">qfc</span>s for which the size is generally quadratically smaller than the size of equivalent <span style="font-variant: small-caps;">dfa</span>s.https://www.mdpi.com/2076-3417/14/4/1490quantum finite state automataperiodic stochastic eventsunary regular languages |
| spellingShingle | Carlo Mereghetti Beatrice Palano Priscilla Raucci Unary Quantum Finite State Automata with Control Language Applied Sciences quantum finite state automata periodic stochastic events unary regular languages |
| title | Unary Quantum Finite State Automata with Control Language |
| title_full | Unary Quantum Finite State Automata with Control Language |
| title_fullStr | Unary Quantum Finite State Automata with Control Language |
| title_full_unstemmed | Unary Quantum Finite State Automata with Control Language |
| title_short | Unary Quantum Finite State Automata with Control Language |
| title_sort | unary quantum finite state automata with control language |
| topic | quantum finite state automata periodic stochastic events unary regular languages |
| url | https://www.mdpi.com/2076-3417/14/4/1490 |
| work_keys_str_mv | AT carlomereghetti unaryquantumfinitestateautomatawithcontrollanguage AT beatricepalano unaryquantumfinitestateautomatawithcontrollanguage AT priscillaraucci unaryquantumfinitestateautomatawithcontrollanguage |