State complexity of one-way quantum finite automata together with classical states

• URL: http://arxiv.org/abs/2112.03746v2
• Date: Wed, 8 Dec 2021 04:17:40 GMT
• Title: State complexity of one-way quantum finite automata together with classical states
• Authors: Ligang Xiao and Daowen Qiu
• Abstract summary: One-way quantum finite automata together with classical states (1QFAC) proposed in [Journal of Computer and System Sciences 81(2) 359-375] As a quantum-classical hybrid model, 1QFAC recognize all regular languages. It was shown that the state complexity of 1QFAC for some languages is essentially superior to that of DFA and other 1QFA.
• Score: 2.3097706741644686
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: One-way quantum finite automata together with classical states (1QFAC) proposed in [Journal of Computer and System Sciences 81(2) (2015) 359--375] is a new one-way quantum finite automata (1QFA) model that integrates quantum finite automata (QFA) and deterministic finite automata (DFA). This model uses classical states to control the evolution and measurement of quantum states. As a quantum-classical hybrid model, 1QFAC recognize all regular languages. It was shown that the state complexity of 1QFAC for some languages is essentially superior to that of DFA and other 1QFA. In this paper, our goal is to clarify state complexity problems for 1QFAC. We obtain the following results: (1) We optimize the bound given by Qiu et al. that characterizes the relationship between quantum basis state number and classical state number of 1QFAC as well as the state number of its corresponding minimal DFA for recognizing any given regular language. (2) We give an upper bound showing that how many classical states are needed if the quantum basis states of 1QFAC are reduced without changing its recognition ability. (3) We give a lower bound of the classical state number of 1QFAC for recognizing any given regular language, and the lower bound is exact if the given language is finite. (4) We show that 1QFAC are exponentially more succinct than DFA and probabilistic finite automata (PFA) for recognizing some regular languages that can not be recognized by measure-once 1QFA (MO-1QFA), measure-many 1QFA (MM-1QFA) or multi-letter 1QFA. (5) We reveal essential relationships between 1QFAC, MO-1QFA and multi-letter 1QFA, and induce a result regarding a quantitative relationship between the state number of multi-letter 1QFA and DFA.

Related papers

• Toward Separating QMA from QCMA with a Classical Oracle [10.699704508276174]
  QMA is the class of languages that can be decided by an efficient quantum verifier given a quantum witness, whereas QCMA is the class of such languages where the efficient quantum verifier only is given a classical witness. A challenging fundamental goal in quantum query complexity is to find a classical oracle separation for these classes.
  arXiv  Detail & Related papers  (2024-11-04T00:18:06Z)
• A Framework for Quantum Finite-State Languages with Density Mapping [3.1133049660590615]
  A quantum finite-state automaton (QFA) is a theoretical model designed to simulate the evolution of a quantum system with finite memory. We present a framework that provides a simple and intuitive way to build QFAs and maximize the simulation accuracy.
  arXiv  Detail & Related papers  (2024-07-03T03:06:37Z)
• Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms [65.268245109828]
  We take inspiration from Kearns' SQ oracle and Valiant's weak evaluation oracle. We introduce an extensive yet intuitive framework that yields unconditional lower bounds for learning from evaluation queries.
  arXiv  Detail & Related papers  (2023-10-26T18:23:21Z)
• Quantum Merlin-Arthur proof systems for synthesizing quantum states [0.0]
  We investigate a state synthesizing counterpart of the class NP-synthesizing. We establish that the family of UQMA witnesses, considered as one of the most natural candidates, is in stateQMA. We demonstrate that stateQCMA achieves perfect completeness.
  arXiv  Detail & Related papers  (2023-03-03T12:14:07Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more. Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
  arXiv  Detail & Related papers  (2023-03-02T14:18:17Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Quantum Semantic Communications for Resource-Efficient Quantum Networking [52.3355619190963]
  This letter proposes a novel quantum semantic communications (QSC) framework exploiting advancements in quantum machine learning and quantum semantic representations. The proposed framework achieves approximately 50-75% reduction in quantum communication resources needed, while achieving a higher quantum semantic fidelity.
  arXiv  Detail & Related papers  (2022-05-05T03:49:19Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• Learning Quantum Finite Automata with Queries [2.28438857884398]
  Quantum finite automata (QFA) are simple models of quantum computers with finite memory. We propose a learning algorithm for measure-once one-way QFA (MO-1QFA) with query complexity of time. We also propose a learning algorithm for measure-many one-way QFA (MM-1QFA) with query complexity of time.
  arXiv  Detail & Related papers  (2021-11-28T03:26:47Z)
• On the properties of the asymptotic incompatibility measure in multiparameter quantum estimation [62.997667081978825]
  Incompatibility (AI) is a measure which quantifies the difference between the Holevo and the SLD scalar bounds. We show that the maximum amount of AI is attainable only for quantum statistical models characterized by a purity larger than $mu_sf min = 1/(d-1)$.
  arXiv  Detail & Related papers  (2021-07-28T15:16:37Z)
• Cost-efficient QFA Algorithm for Quantum Computers [0.0]
  We present a modified Moore-Crutchfield quantum finite automaton (MCQFA) algorithm for the language $mathttMOD_p$. We obtain shorter quantum programs using fewer basis gates compared to the implementation of the original algorithm given in the literature.
  arXiv  Detail & Related papers  (2021-07-05T20:41:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.