| | |
| | |
Stat |
Members: 3645 Articles: 2'504'928 Articles rated: 2609
25 April 2024 |
|
| | | |
|
Article overview
| |
|
Nonuniform Families of Polynomial-Size Quantum Finite Automata and Quantum Logarithmic-Space Computation with Polynomial-Size Advice | Tomoyuki Yamakami
; | Date: |
5 Jul 2019 | Abstract: | The state complexity of a finite(-state) automaton intuitively measures the
size of the description of the automaton. Sakoda and Sipser [STOC 1972, pp.
275-286] were concerned with nonuniform families of finite automata and they
discussed the behaviors of nonuniform complexity classes defined by families of
such finite automata having polynomial-size state complexity. In a similar
fashion, we introduce nonuniform state complexity classes using families of
quantum finite automata. Our primarily concern is one-way quantum finite
automata empowered by garbage tapes. We show inclusion and separation
relationships among nonuniform state complexity classes of various one-way
finite automata, including deterministic, nondeterministic, probabilistic, and
quantum finite automata of polynomial size. For two-way quantum finite automata
equipped with garbage tapes, we discover a close relationship between the
nonuniform state complexity of such a polynomial-size quantum finite automata
family and the parameterized complexity class induced by quantum
logarithmic-space computation assisted by polynomial-size advice. | Source: | arXiv, 1907.2916 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |