RECORD
1-way quantum finite automata: strengths, weaknesses and generalizations
Quantum Physics · Submitted 25 Feb 1998
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim Namely, we construct a 1-way QFA which is exponentially smaller than any equivalent classical (even randomized) finite automaton.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
We study 1-way quantum finite automata (QFAs). First, we compare them with their classical counterparts. We show that, if an automaton is required to give the correct answer with a large probability (over 0.98), then the power of 1-way QFAs is equal to the power of 1-way reversible automata. However, quantum automata giving the correct answer with smaller probabilities are more powerful than reversible automata. Second, we show that 1-way QFAs can be very space-efficient. Namely, we construct a 1-way QFA which is exponentially smaller than any equivalent classical (even randomized) finite automaton. This construction may be useful for design of other space-efficient quantum algorithms. Third, we consider several generalizations of 1-way QFAs. Here, our goal is to find a model which is more powerful than 1-way QFAs keeping the quantum part as simple as possible.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We study 1-way quantum finite automata (QFAs). | contribution 0.65 | 0.57 | 0.02 | asserted 0.54 |
| s1 | First, we compare them with their classical counterparts. | contribution 0.72 | 0.82 | 0.02 | unclear 0.50 |
| s2 | We show that, if an automaton is required to give the correct answer with a large probability (over 0.98), then the power of 1-way QFAs is equal to the power of 1-way reversible automata. | result 1.00 | 0.92 | 0.29 | asserted 1.00 |
| s3 | However, quantum automata giving the correct answer with smaller probabilities are more powerful than reversible automata. | result 1.00 | 0.88 | 0.19 | asserted 1.00 |
| s4 | Second, we show that 1-way QFAs can be very space-efficient. | result 0.76 | 0.82 | 0.12 | asserted 0.86 |
| s5 | Namely, we construct a 1-way QFA which is exponentially smaller than any equivalent classical (even randomized) finite automaton. | result 0.84 | 0.96 | 0.21 | asserted 1.00 |
| s6 | This construction may be useful for design of other space-efficient quantum algorithms. | interpretation 0.79 | 0.30 | 0.05 | hedged possibility 1.00 |
| s7 | Third, we consider several generalizations of 1-way QFAs. | contribution 0.98 | 0.88 | 0.03 | asserted 0.78 |
| s8 | Here, our goal is to find a model which is more powerful than 1-way QFAs keeping the quantum part as simple as possible. | contribution 0.65 | 0.54 | 0.05 | asserted 0.62 |
What was examined, and what was not
- arXiv listing abstract v3
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
We study 1-way quantum finite automata (QFAs). First, we compare them with their classical counterparts. We show that, if an automaton is required to give the correct answer with a large probability (over 0.98), then the power of 1-way QFAs is equal to the power of 1-way reversible automata. However, quantum automata giving the correct answer with smaller probabilities are more powerful than reversible automata. Second, we show that 1-way QFAs can be very space-efficient. Namely, we construct a 1-way QFA which is exponentially smaller than any equivalent classical (even randomized) finite automaton. This construction may be useful for design of other space-efficient quantum algorithms. Third, we consider several generalizations of 1-way QFAs. Here, our goal is to find a model which is more powerful than 1-way QFAs keeping the quantum part as simple as possible.
Human review
References
How the literature uses it
8 arXiv papers cite this in 13 sentences
Papers citing it · 10 sentences without a confident label
Uses its method or tool 1 paper
-
The algorithm takes $X_1$ and obtains a value of the function $v_1=EQ(X_1)$ using quantum fingerprinting method presented in [ref] , [ref] .
Quantum Online Algorithms with Respect to Space Complexity · Polylogarithmic Space Complexity Separation between Quantum and Deterministic Online Algorithms with Polylogarithmic Mem · 1.00
Cites it as background 2 papers
-
The main reason for the investigation of restricted models of quantum computers was proposed by Ambainis and Freivalds in 1998 [ref] .
Algorithms for Quantum Branching Programs Based on Fingerprinting · Introduction · 0.89
-
This naturally leads to the restricted variants of a quantum computer – the idea first proposed by Ambainis and Freivalds in 1998 [ref] .
On Computational Power of Quantum Read-Once Branching Programs · Introduction · 0.80
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.