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

Lecture notes in computer science

Exact Results for Accepting Probabilities of Quantum Automata

Andris Ambainis, Arnolds Ķikusts

Published Jan 1, 2001• 3 citations
Publisher
DOI
10.1007/3-540-44683-4_13

Related papers

Exact results for accepting probabilities of quantum automata

Andris Ambainis, Arnolds Ķikusts

arXiv:quant-ph/0109136•Theoretical Computer Science•Feb 1, 2003•23 citations

Probabilities to Accept Languages by Quantum Finite Automata

Andris Ambainis, Richard Bonner, Rūsiņš Freivalds +1 more

arXiv:quant-ph/9904066•Lecture notes in computer science•Jan 1, 1999•41 citations

Regular Languages Accepted by Quantum Automata

Alberto Bertoni, Marco Carpentieri

Information and Computation•Mar 1, 2001•54 citations

Lower Bounds on the Size of Quantum Automata Accepting Unary Languages

Alberto Bertoni, Carlo Mereghetti, Beatrice Palano

Lecture notes in computer science•Jan 1, 2003•9 citations

Potential of Quantum Finite Automata with Exact Acceptance

Jozef Gruska, Daowen Qiu, Shenggen Zheng

The potential of the exact quantum information processing is an interesting, important and intriguing issue. For examples, it has been believed that quantum tools can provide significant, that is larger than polynomial, advantages in the case of exact quantum computation only, or mainly, for problems with very special structures. We will show that this is not the case. In this paper the potential of quantum finite automata producing outcomes not only with a (high) probability, but with certainty (so called exactly) is explored in the context of their uses for solving promise problems and with respect to the size of automata. It is shown that for solving particular classes [Formula: see text] of promise problems, even those without some very special structure, that succinctness of the exact quantum finite automata under consideration, with respect to the number of (basis) states, can be very small (and constant) though it grows proportional to [Formula: see text] in the case deterministic finite automata (DFAs) of the same power are used. This is here demonstrated also for the case that the component languages of the promise problems solvable by DFAs are non-regular. The method used can be applied in finding more exact quantum finite automata or quantum algorithms for other promise problems.

arXiv:1404.1689•International Journal of Foundations of Computer Science•Apr 1, 2015•29 citations

Embedding measure-once quantum finite automata in the Feynman quantum computer model

Carlo Mereghetti, Beatrice Palano, Dario Tamascelli

We present an explicit embedding of measure-once quantum finite automata (MO-QFAs) into the Feynman quantum computer model.Given an MO-QFA, we construct the corresponding Feynman machine whose register encodes both the input word and the automaton state, while a cursor evolving under a Hamiltonian implements the sequential application of the automaton transition operators.The construction relies on nested SWITCH mechanisms that select transitions according to the input symbols.We prove that, for every MO-QFA and every input word, measuring the cursor in its final position yields exactly the quantum state reached by the automaton after processing the same input.Consequently, acceptance probabilities are preserved exactly, and every language recognized by an MO-QFA with cutpoint can be recognized within the Feynman framework with the same acceptance behavior.This establishes an explicit connection between discrete-time quantum computation and continuous-time, physically motivated Hamiltonian models.

•Sep 1, 2026•0 citations
The potential of the exact quantum information processing is an interesting, important and intriguing issue. For examples, it has been believed that quantum tools can provide significant, that is larger than polynomial, advantages in the case of exact quantum computation only, or mainly, for problems with very special structures. We will show that this is not the case. In this paper the potential of quantum finite automata producing outcomes not only with a (high) probability, but with certainty (so called exactly) is explored in the context of their uses for solving promise problems and with respect to the size of automata. It is shown that for solving particular classes [Formula: see text] of promise problems, even those without some very special structure, that succinctness of the exact quantum finite automata under consideration, with respect to the number of (basis) states, can be very small (and constant) though it grows proportional to [Formula: see text] in the case deterministic finite automata (DFAs) of the same power are used. This is here demonstrated also for the case that the component languages of the promise problems solvable by DFAs are non-regular. The method used can be applied in finding more exact quantum finite automata or quantum algorithms for other promise problems.
We present an explicit embedding of measure-once quantum finite automata (MO-QFAs) into the Feynman quantum computer model.Given an MO-QFA, we construct the corresponding Feynman machine whose register encodes both the input word and the automaton state, while a cursor evolving under a Hamiltonian implements the sequential application of the automaton transition operators.The construction relies on nested SWITCH mechanisms that select transitions according to the input symbols.We prove that, for every MO-QFA and every input word, measuring the cursor in its final position yields exactly the quantum state reached by the automaton after processing the same input.Consequently, acceptance probabilities are preserved exactly, and every language recognized by an MO-QFA with cutpoint can be recognized within the Feynman framework with the same acceptance behavior.This establishes an explicit connection between discrete-time quantum computation and continuous-time, physically motivated Hamiltonian models.