Promise problems solved by quantum and classical finite automata

DOI10.1016/J.TCS.2016.12.025MaRDI QIDQ511009zbMATH OpenOpenAlexFDO

Authors Shenggen Zheng, Lvzhou Li, Jozef Gruska, Daowen Qiu

Publication date 14 February 2017

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.3870

zbMATH Keywords

finite automataquantum computingquantum finite automatarecognizabilitysolvabilitypromise problems

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Quantum algorithms and complexity in the theory of computing (68Q12)

Abstract: The concept of promise problems was introduced and started to be systematically explored by Even, Selman, Yacobi, Goldreich, and other scholars. It has been argued that promise problems should be seen as partial decision problems and as such that they are more fundamental than decision problems and formal languages that used to be considered as the basic ones for complexity theory. The main purpose of this paper is to explore the promise problems accepted by classical, quantum and also semi-quantum finite automata. More specifically, we first introduce two acceptance modes of promise problems, recognizability and solvability, and explore their basic properties. Afterwards, we show several results concerning descriptional complexity on promise problems. In particular, we prove: (1) there is a promise problem that can be recognized exactly by measure-once one-way quantum finite automata (MO-1QFA), but no deterministic finite automata (DFA) can recognize it; (2) there is a promise problem that can be solved with error probability $epsilonleq1/3$ by one-way finite automaton with quantum and classical states (1QCFA), but no one-way probability finite automaton (PFA) can solve it with error probability $epsilonleq1/3$; and especially, (3) there are promise problems $A(p)$ with prime $p$ that can be solved {em with any error probability} by MO-1QFA with only two quantum basis states, but they can not be solved exactly by any MO-1QFA with two quantum basis states; in contrast, the minimal PFA solving $A(p)$ with any error probability (usually smaller than $1/2$) has $p$ states. Finally, we mention a number of problems related to promise for further study.

Recommendations

• scientific article; zbMATH DE number 6515829
• Complexity of promise problems on classical and quantum automata
• Superiority of exact quantum automata for promise problems
• Classical automata on promise problems

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• scientific article; zbMATH DE number 3371972 (Why is no real title available?)
• A lower bound for probabilistic algorithms for finite state machines
• Algebra-coalgebra duality in Brzozowski's minimization algorithm
• Characterization of sequential quantum machines
• Characterizations of one-way general quantum finite automata
• Characterizations of quantum automata
• Classical automata on promise problems
• Complexity of promise problems on classical and quantum automata
• Determining the equivalence for one-way quantum finite automata
• Encyclopedia of Complexity and Systems Science
• Exponentially more concise quantum recognition of non-RMM regular languages
• Finite state verifiers I
• From quantum query complexity to state complexity
• GOLOMB RULERS AND DIFFERENCE SETS FOR SUCCINCT QUANTUM AUTOMATA
• Hierarchy and equivalence of multi-letter quantum finite automata
• Implications of quantum automata for contextuality
• Improved constructions of mixed state quantum automata
• Improved constructions of quantum automata
• Multi-letter quantum finite automata: decidability of the equivalence and minimization of states
• On hybrid models of quantum finite automata
• On the Power of Quantum Computation
• On the complexity of minimizing probabilistic and quantum automata
• On the state complexity of semi-quantum finite automata
• One-way finite automata with quantum and classical states
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Potential of quantum finite automata with exact acceptance
• Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
• Quantum automata and quantum grammars
• Quantum finite automata
• Small size quantum automata recognizing some regular languages
• Some formal tools for analyzing quantum automata.
• State succinctness of two-way finite automata with quantum and classical states
• Succinctness of two-way probabilistic and quantum finite automata
• Superiority of exact quantum automata for promise problems
• The complexity of promise problems with applications to public-key cryptography
• Two-way finite automata with quantum and classical states.

Cited in

(12)

• Modeling of RNA secondary structures using two-way quantum finite automata
• Finite automata capturing winning sequences for all possible variants of the \(PQ\) penny flip game
• Three Attacks on the Mediated Semi‐Quantum Key Distribution without Invoking Quantum Measurement
• scientific article; zbMATH DE number 6515829 (Why is no real title available?)
• Superiority of exact quantum automata for promise problems
• Implications of quantum automata for contextuality
• Classical automata on promise problems
• A promiseBQP-complete string rewriting problem
• On the power of two-way multihead quantum finite automata
• Complexity of promise problems on classical and quantum automata
• Potential of quantum finite automata with exact acceptance
• On coverings of products of uninitialized sequential quantum machines

This page was built for publication: Promise problems solved by quantum and classical finite automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q511009)