Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2001.10749 · Physical Review Research

Photonic realization of a quantum finite automaton

Carlo Mereghetti, Beatrice Palano, Simone Cialdi, Valeria Vento, Matteo G. A. Paris, Stefano Olivares

Published Jan 28, 2020• 17 citations
arXivHTMLPDF

Abstract

This paper uncovers an all-optical implementation of a two state quantum finite automata, whose accepted language would require an unbounded number of states to be accepted on classical finite automata. Our device is based on the polarization of a single photon and its manipulation through linear optical elements.
DOI
10.1103/physrevresearch.2.013089

Related papers

An Enhanced Photonic Quantum Finite Automaton

Alessandro Candeloro, Carlo Mereghetti, Beatrice Palano +3 more

In a recent paper we have described an optical implementation of a measure-once one-way quantum finite automaton recognizing a well-known family of unary periodic languages, accepting words not in the language with a given error probability. To process input words, the automaton exploits the degree of polarization of single photons and, to reduce the acceptance error probability, a technique of confidence amplification using the photon counts is implemented. In this paper, we show that the performance of this automaton may be further improved by using strategies that suitably consider both the orthogonal output polarizations of the photon. In our analysis, we also take into account how detector dark counts may affect the performance of the automaton.

arXiv:2109.10101•Applied Sciences•Sep 21, 2021•7 citations

Experimental Demonstration Advantage of Photonic Finite Automata

Yuanyuan Zhao, Keren Li, Chao Li +2 more

Finite automata have abundant applications such as finding reachability and so on. This work presents the first experimental implementation of the two-way quantum finite automaton with the optical platform and demonstrates its potential quantum advantages.

Asia Communications and Photonics Conference•Nov 4, 2023•4 citations

Linear optical implementation of a single-mode quantum filter and generation of multiphoton polarization entangled states

Xu‐Bo Zou, K. Pahlke, Wolfgang M. Mathis

We propose a scheme to implement a single-mode quantum filter, which selectively eliminates the one-photon state in a quantum state $\ensuremath{\alpha}|0〉+\ensuremath{\beta}|1〉+\ensuremath{\gamma}|2〉.$ The vacuum state and the two-photon state are transmitted without any change. This scheme requires single-photon sources, linear optical elements, and photon detectors. Furthermore, we demonstrate how this filter can be used to realize a two-qubit projective measurement and to generate multiphoton polarization entangled states.

arXiv:quant-ph/0210096•Physical Review A•Dec 26, 2002•13 citations

2-tape 1-way Quantum Finite State Automata

Debayan Ganguly, Kumar S. Ray

1-way quantum finite state automata are reversible in nature, which greatly reduces its accepting property. In fact, the set of languages accepted by 1-way quantum finite automata is a proper subset of regular languages. We introduce 2-tape 1-way quantum finite state automaton (2T1QFA(2))which is a modified version of 1-way 2-head quantum finite state automaton(1QFA(2)). In this paper, we replace the single tape of 1-way 2-head quantum finite state automaton with two tapes. The content of the second tape is determined using a relation defined on input alphabet. The main claims of this paper are as follows: (1)We establish that 2-tape 1-way quantum finite state automaton(2T1QFA(2)) can accept all regular languages (2)A language which cannot be accepted by any multi-head deterministic finite automaton can be accepted by 2-tape 1-way quantum finite state automaton(2T1QFA(2)) .(3) Exploiting the superposition property of quantum automata we show that 2-tape 1-way quantum finite state automaton(2T1QFA(2)) can accept the language L=ww.

arXiv:1607.00811•Jul 4, 2016•1 citation

Superiority of one-way and realtime quantum machines

Abuzer Yakaryılmaz

In automata theory, quantum computation has been widely examined for finite state machines, known as quantum finite automata (QFAs), and less attention has been given to QFAs augmented with counters or stacks. In this paper, we focus on such generalizations of QFAs where the input head operates in one-way or realtime mode, and present some new results regarding their superiority over their classical counterparts. Our first result is about the nondeterministic acceptance mode: Each quantum model architecturally intermediate between realtime finite state automaton and one-way pushdown automaton (one-way finite automaton, realtime and one-way finite automata with one-counter, and realtime pushdown automaton) is superior to its classical counterpart. The second and third results are about bounded error language recognition: for any k > 0, QFAs with k blind counters outperform their deterministic counterparts; and, a one-way QFA with a single head recognizes an infinite family of languages, which can be recognized by one-way probabilistic finite automata with at least two heads. Lastly, we compare the nondeterminictic and deterministic acceptance modes for classical finite automata with k blind counter(s), and we show that for any k > 0, the nondeterministic models outperform the deterministic ones.

RAIRO - Theoretical Informatics and Applications•Oct 1, 2012•20 citations

Quantum Computations with Polarized Photons

Giacomo Mauro D’Ariano, Chiara Macchiavello, Lorenzo Maccone

We propose a fully optical method to perform any quantum computation by supplying the prescriptions for a universal set of quantum gates. We also give the methods for the generation of input states and the realization of final measurements. The apparatus is scalable, and relies on high Kerr non-linearities.

Fortschritte der Physik•May 1, 2000•19 citations
In a recent paper we have described an optical implementation of a measure-once one-way quantum finite automaton recognizing a well-known family of unary periodic languages, accepting words not in the language with a given error probability. To process input words, the automaton exploits the degree of polarization of single photons and, to reduce the acceptance error probability, a technique of confidence amplification using the photon counts is implemented. In this paper, we show that the performance of this automaton may be further improved by using strategies that suitably consider both the orthogonal output polarizations of the photon. In our analysis, we also take into account how detector dark counts may affect the performance of the automaton.
We propose a scheme to implement a single-mode quantum filter, which selectively eliminates the one-photon state in a quantum state $\ensuremath{\alpha}|0〉+\ensuremath{\beta}|1〉+\ensuremath{\gamma}|2〉.$ The vacuum state and the two-photon state are transmitted without any change. This scheme requires single-photon sources, linear optical elements, and photon detectors. Furthermore, we demonstrate how this filter can be used to realize a two-qubit projective measurement and to generate multiphoton polarization entangled states.
1-way quantum finite state automata are reversible in nature, which greatly reduces its accepting property. In fact, the set of languages accepted by 1-way quantum finite automata is a proper subset of regular languages. We introduce 2-tape 1-way quantum finite state automaton (2T1QFA(2))which is a modified version of 1-way 2-head quantum finite state automaton(1QFA(2)). In this paper, we replace the single tape of 1-way 2-head quantum finite state automaton with two tapes. The content of the second tape is determined using a relation defined on input alphabet. The main claims of this paper are as follows: (1)We establish that 2-tape 1-way quantum finite state automaton(2T1QFA(2)) can accept all regular languages (2)A language which cannot be accepted by any multi-head deterministic finite automaton can be accepted by 2-tape 1-way quantum finite state automaton(2T1QFA(2)) .(3) Exploiting the superposition property of quantum automata we show that 2-tape 1-way quantum finite state automaton(2T1QFA(2)) can accept the language L=ww.
In automata theory, quantum computation has been widely examined for finite state machines, known as quantum finite automata (QFAs), and less attention has been given to QFAs augmented with counters or stacks. In this paper, we focus on such generalizations of QFAs where the input head operates in one-way or realtime mode, and present some new results regarding their superiority over their classical counterparts. Our first result is about the nondeterministic acceptance mode: Each quantum model architecturally intermediate between realtime finite state automaton and one-way pushdown automaton (one-way finite automaton, realtime and one-way finite automata with one-counter, and realtime pushdown automaton) is superior to its classical counterpart. The second and third results are about bounded error language recognition: for any k > 0, QFAs with k blind counters outperform their deterministic counterparts; and, a one-way QFA with a single head recognizes an infinite family of languages, which can be recognized by one-way probabilistic finite automata with at least two heads. Lastly, we compare the nondeterminictic and deterministic acceptance modes for classical finite automata with k blind counter(s), and we show that for any k > 0, the nondeterministic models outperform the deterministic ones.