Promise problems solved by quantum and classical finite automata

DOI10.1016/J.TCS.2016.12.025zbMATH Open1359.68181arXiv1411.3870OpenAlexW2964031227MaRDI QIDQ511009FDOQ511009

Jozef Gruska, Shenggen Zheng, Lvzhou Li, Daowen Qiu

Publication date: 14 February 2017

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

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.

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)

Cites Work

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

Cited In (10)

• Superiority of exact quantum automata for promise problems
• Modeling of RNA secondary structures using two-way quantum finite automata
• Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice
• Unary probabilistic and quantum automata on promise problems
• Three Attacks on the Mediated Semi‐Quantum Key Distribution without Invoking Quantum Measurement
• Finite automata capturing winning sequences for all possible variants of the \(PQ\) penny flip game
• On the power of two-way multihead quantum finite automata
• Classical and Quantum Counter Automata on Promise Problems
• Title not available (Why is that?)
• 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)