Automata and Quantum Computing

Abuzer Yakary{\i}lmaz; Andris Ambainis

Automata and Quantum Computing

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1507.01988 v2 pith:MAXJ5VJ7 submitted 2015-07-07 cs.FL cs.CCquant-ph

Andris Ambainis , Abuzer Yakary{i}lmaz This is my paper

classification cs.FLcs.CCquant-ph

keywords quantumautomatafinitecomputerscomplexitycomputingerrormodels

verification ladder T0 review T1 audit T2 compute T3 formal

0 comments

read the original abstract

Quantum computing is a new model of computation, based on quantum physics. Quantum computers can be exponentially faster than conventional computers for problems such as factoring. Besides full-scale quantum computers, more restricted models such as quantum versions of finite automata have been studied. In this paper, we survey various models of quantum finite automata and their properties. We also provide some open questions and new directions for researchers. Keywords: quantum finite automata, probabilistic finite automata, nondeterminism, bounded error, unbounded error, state complexity, decidability and undecidability, computational complexity

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

QIP $ \subseteq $ AM(2QCFA)
quant-ph 2025-08 conditional novelty 6.0 of 10

PSPACE, hence QIP, is contained in the class of languages verifiable by Arthur-Merlin proof systems whose verifier is a two-way automaton with a constant-size quantum memory.

Pith tools