Back to search

University of British Columbia

Models and characterizations of 1-way quantum finite automata

Abstract

dc:description

In the past year two different models of quantum finite automata have been proposed. The first model, introduced by Moore and Crutchfield[MC98], makes one measurement on its state at the end of its computation and is called a measure-once quantum finite automata. The second model, introduced by Kondacs and Watrous[KW97], makes a measurement of its state after every transition and is called a measure-many quantum finite automata. In this thesis we investigate the characteristics of the two models. We characterize measure-once quantum finite automata when they are restricted to acceptance with bounded error, and we show that, when they are not so restricted, they can solve the word problem over the free group. We show that they can be simulated by probabilistic finite automata, which implies that they are no more powerful than probabilistic finite automata. We also describe an algorithm that determines if two automata are equivalent. We show that the class of languages accepted by measure-many quantum finite automata is closed under quotient, complement, and inverse homomorphisms. We prove a necessary condition for a language to be accepted by a measure-many automaton with bounded error and we show that certain sets, including piecewise testable sets, can be accepted with bounded error by this automata.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
1998

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Brodsky, Alexander

Rights

dc:rights
Statement dc:rights
  • For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/8895

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Brodsky, Alexander. Models and characterizations of 1-way quantum finite automata. master's thesis, University of British Columbia, 1998. http://hdl.handle.net/2429/8895