Related papers: Quantum Büchi Automata

Quantum Büchi Automata

URL: http://arxiv.org/abs/1804.08982v2
Date: Fri, 26 Jul 2024 13:51:28 GMT
Title: Quantum Büchi Automata
Authors: Qisheng Wang, Mingsheng Ying,
Abstract summary: We introduce the classes of $omega$-languages recognized by QBAs in probable, almost sure, strict and non-strict threshold semantics. We show that there are surprisingly only at most four substantially different classes of $omega$-languages recognized by QBAs (out of uncountably infinite) The relationship between classical $omega$-languages and QBAs is clarified using our pumping lemmas.
Score: 4.998632546280976
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Quantum finite automata (QFAs) have been extensively studied in the literature. In this paper, we define and systematically study quantum B\"uchi automata (QBAs) over infinite words to model the long-term behavior of quantum systems, which extend QFAs. We introduce the classes of $\omega$-languages recognized by QBAs in probable, almost sure, strict and non-strict threshold semantics. Several pumping lemmas and closure properties for QBAs are proved. Some decision problems for QBAs are investigated. In particular, we show that there are surprisingly only at most four substantially different classes of $\omega$-languages recognized by QBAs (out of uncountably infinite). The relationship between classical $\omega$-languages and QBAs is clarified using our pumping lemmas. We also find an $\omega$-language recognized by QBAs under the almost sure semantics, which is not $\omega$-context-free.

Related papers

Oracle Separations for the Quantum-Classical Polynomial Hierarchy [0.0]
We study the quantum-classical hierarchy, QCPH, which is the class of languages solvable by a constant number of alternating classical quantifiers. We give a new switching lemma for quantum algorithms which may be of independent interest.
arXiv Detail & Related papers (2024-10-24T18:12:03Z)
CountCrypt: Quantum Cryptography between QCMA and PP [7.408475650692233]
We construct a quantum oracle relative to which BQP = QCMA but quantum-computation-classical-communication key exchange, QCCC commitments, and two-round quantum key distribution exist. We also show that QCCC key exchange, QCCC commitments, and two-round quantum key distribution can all be used to build one-way puzzles.
arXiv Detail & Related papers (2024-10-18T18:04:27Z)
The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
arXiv Detail & Related papers (2024-02-29T01:35:46Z)
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)
Deterministic Construction of QFAs based on the Quantum Fingerprinting Technique [0.0]
A quantum finite automata recognizing the language $MOD_p$ has an exponential advantage over the classical finite automata. We construct a QFA for a promise problem $Palindrome_s$ and implement this QFA on the IBMQ simulator.
arXiv Detail & Related papers (2022-12-29T19:33:56Z)
Quantum Depth in the Random Oracle Model [57.663890114335736]
We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
arXiv Detail & Related papers (2022-10-12T17:54:02Z)
Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
arXiv Detail & Related papers (2022-04-22T12:37:56Z)
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)
Quantum double aspects of surface code models [77.34726150561087]
We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry. We show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$.
arXiv Detail & Related papers (2021-06-25T17:03:38Z)
Quantum Differentially Private Sparse Regression Learning [132.1981461292324]
We devise an efficient quantum differentially private (QDP) Lasso estimator to solve sparse regression tasks. Last, we exhibit that the QDP Lasso attains a near-optimal utility bound $tildeO(N-2/3)$ with privacy guarantees.
arXiv Detail & Related papers (2020-07-23T10:50:42Z)
The Power of a Single Qubit: Two-way Quantum Finite Automata and the Word Problem [0.0]
Two-way finite automaton with quantum and classical states (2QCFA) is a model of quantum computation whose quantum part is extremely limited. We show that 2QCFA can recognize the language $L_eq=am bm :m mathbbN$ in expected time and the language $L_pal=w in a,b*:w CFA CFA is a palindrome$ in expected exponential time.
arXiv Detail & Related papers (2020-03-22T12:46:37Z)

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