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

Asia Communications and Photonics Conference

Experimental Demonstration Advantage of Photonic Finite Automata

Yuanyuan Zhao, Keren Li, Chao Li, Shenggen Zheng, Zhixue He

Published Nov 4, 2023• 4 citations
Publisher

Abstract

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.
DOI
10.1109/acp/poem59049.2023.10369125

Related papers

Photonic realization of a quantum finite automaton

Carlo Mereghetti, Beatrice Palano, Simone Cialdi +3 more

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.

arXiv:2001.10749•Physical Review Research•Jan 28, 2020•17 citations

Experimental demonstration of quantum finite automaton

Yuling Tian, Tianfeng Feng, Maolin Luo +2 more

Abstract In quantum information science, a major task is to find the quantum models that can outperform their classical counterparts. Automaton is a fundamental computing model that has wide applications in many fields. It has been shown that the quantum version of automaton can solve certain problem using a much smaller state space compared to the classical automaton. Here we report an experimental demonstration of an optical quantum automaton, which is used to solve the promise problems of determining whether the length of an input string can be divided by a prime number P with no remainder or with a remainder of R. Our quantum automaton can solve such problem using a state space with only three orthonormal states, whereas the classical automaton needs no less than P states. Our results demonstrate the quantum benefits of a quantum automaton over its classical counterpart and paves the way for implementing quantum automaton for more complicated and practical applications.

npj Quantum Information•Jun 11, 2019•19 citations

On the Simulation Cost of Quantum Finite Automata

Zeyu Chen, Junde Wu

This paper identifies exact probabilistic simulation cost as the natural quantitative measure of quantum advantage for finite automata under strict cutpoints. It gives sharp simulation laws for two representative models. A one-way finite automaton with $c$ classical states and a $q$-dimensional quantum register has exact probabilistic simulation cost $Θ(cq^2)$, while an $n$-dimensional measure-once one-way quantum finite automaton has worst-case cost $Θ(n^2)$. The proofs develop a prepare--test framework, in which prefixes generate the relevant real operator degrees of freedom and suffixes convert them into strict-cutpoint tests. The same obstruction is recast through finite sign-rank matrices, clarifying the role of Forster's spectral method. Placed beside the surrounding two-way separations, these results give a clean hierarchy of finite-automata quantum advantage.

quant-pharXiv:2605.10682•May 12, 2026•0 citations

Empowering measures for quantum finite automata (QFA)

Soumya Debabrata Pani, Chandan Kumar Behera

The 1-way quantum finite automata and 2-way quantum finite automata are the first ever developed quantum automatons. But they suffer from many disadvantages which make them less powerful and impracticable. To remove these drawbacks there are many ways to modify and aggrandize the quantum finite automatons. Including 1-counter with 1-way QFA significantly improve its power. Likely quantum finite automata with quantum and classical states (QCFA) and 2-way quantum finite 1-counter automata (2-QF1-CA) are the quintessence of these modifications. In our paper we first discuss about 1-QFA and 2-QFA and their drawbacks. In the section IV we introduce an algorithm by implementing 1-way quantum finite k-counter automata (1-QFk-CA). Then we discuss another algorithm by implementing quantum finite 1-counter automata (QF1-CA) with multiple scanning of the input string. These algorithms improve the power of QFAs.

International Conference on Computer Research and Development•Mar 1, 2011•1 citation

Experimental demonstration of quantum advantage for NP verification

Federico Centrone, Niraj Kumar, Eleni Diamanti +1 more

We showcase the power of linear optics through the implementation of a quantum protocol with coherent states. Our work provides evidence for a computational quantum advantage in the interactive setting, drawing near potentially useful applications.

Conference on Lasers and Electro-Optics•Jan 1, 2021•0 citations

Quantum finite automata: A modern introduction

A. C. Cem Say, Abuzer Yakaryılmaz

We present five examples where quantum finite automata (QFAs) outperform their classical counterparts. This may be useful as a relatively simple technique to introduce quantum computation concepts to computer scientists. We also describe a modern QFA model involving superoperators that is able to simulate all known QFA and classical finite automaton variants.

arXiv:1406.4048•Jun 16, 2014•5 citations
Abstract In quantum information science, a major task is to find the quantum models that can outperform their classical counterparts. Automaton is a fundamental computing model that has wide applications in many fields. It has been shown that the quantum version of automaton can solve certain problem using a much smaller state space compared to the classical automaton. Here we report an experimental demonstration of an optical quantum automaton, which is used to solve the promise problems of determining whether the length of an input string can be divided by a prime number P with no remainder or with a remainder of R. Our quantum automaton can solve such problem using a state space with only three orthonormal states, whereas the classical automaton needs no less than P states. Our results demonstrate the quantum benefits of a quantum automaton over its classical counterpart and paves the way for implementing quantum automaton for more complicated and practical applications.
This paper identifies exact probabilistic simulation cost as the natural quantitative measure of quantum advantage for finite automata under strict cutpoints. It gives sharp simulation laws for two representative models. A one-way finite automaton with ccc classical states and a qqq-dimensional quantum register has exact probabilistic simulation cost Θ(cq2)Θ(cq^2)Θ(cq2), while an nnn-dimensional measure-once one-way quantum finite automaton has worst-case cost Θ(n2)Θ(n^2)Θ(n2). The proofs develop a prepare--test framework, in which prefixes generate the relevant real operator degrees of freedom and suffixes convert them into strict-cutpoint tests. The same obstruction is recast through finite sign-rank matrices, clarifying the role of Forster's spectral method. Placed beside the surrounding two-way separations, these results give a clean hierarchy of finite-automata quantum advantage.
The 1-way quantum finite automata and 2-way quantum finite automata are the first ever developed quantum automatons. But they suffer from many disadvantages which make them less powerful and impracticable. To remove these drawbacks there are many ways to modify and aggrandize the quantum finite automatons. Including 1-counter with 1-way QFA significantly improve its power. Likely quantum finite automata with quantum and classical states (QCFA) and 2-way quantum finite 1-counter automata (2-QF1-CA) are the quintessence of these modifications. In our paper we first discuss about 1-QFA and 2-QFA and their drawbacks. In the section IV we introduce an algorithm by implementing 1-way quantum finite k-counter automata (1-QFk-CA). Then we discuss another algorithm by implementing quantum finite 1-counter automata (QF1-CA) with multiple scanning of the input string. These algorithms improve the power of QFAs.