Deterministic Construction of QFAs based on the Quantum Fingerprinting Technique

• URL: http://arxiv.org/abs/2212.14442v1
• Date: Thu, 29 Dec 2022 19:33:56 GMT
• Title: Deterministic Construction of QFAs based on the Quantum Fingerprinting Technique
• Authors: Aliya Khadieva and Mansur Ziatdinov
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: It is known that for some languages quantum finite automata are more efficient than classical counterparts. Particularly, a QFA recognizing the language $MOD_p$ has an exponential advantage over the classical finite automata. However, the construction of such QFA is probabilistic. In the current work, we propose a deterministic construction of the QFA for the language $MOD_p$. We construct a QFA for a promise problem $Palindrome_s$ and implement this QFA on the IBMQ simulator using qiskit library tools.

Related papers

• 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)
• A Practical Toolkit for Multilingual Question and Answer Generation [79.31199020420827]
  We introduce AutoQG, an online service for multilingual QAG, along with lmqg, an all-in-one Python package for model fine-tuning, generation, and evaluation. We also release QAG models in eight languages fine-tuned on a few variants of pre-trained encoder-decoder language models, which can be used online via AutoQG or locally via lmqg.
  arXiv  Detail & Related papers  (2023-05-27T08:42:37Z)
• TeD-Q: a tensor network enhanced distributed hybrid quantum machine learning framework [59.07246314484875]
  TeD-Q is an open-source software framework for quantum machine learning. It seamlessly integrates classical machine learning libraries with quantum simulators. It provides a graphical mode in which the quantum circuit and the training progress can be visualized in real-time.
  arXiv  Detail & Related papers  (2023-01-13T09:35:05Z)
• 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)
• Generative Language Models for Paragraph-Level Question Generation [79.31199020420827]
  Powerful generative models have led to recent progress in question generation (QG) It is difficult to measure advances in QG research since there are no standardized resources that allow a uniform comparison among approaches. We introduce QG-Bench, a benchmark for QG that unifies existing question answering datasets by converting them to a standard QG setting.
  arXiv  Detail & Related papers  (2022-10-08T10:24:39Z)
• ProQA: Structural Prompt-based Pre-training for Unified Question Answering [84.59636806421204]
  ProQA is a unified QA paradigm that solves various tasks through a single model. It concurrently models the knowledge generalization for all QA tasks while keeping the knowledge customization for every specific QA task. ProQA consistently boosts performance on both full data fine-tuning, few-shot learning, and zero-shot testing scenarios.
  arXiv  Detail & Related papers  (2022-05-09T04:59:26Z)
• 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)
• 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)
• Implementing Quantum Finite Automata Algorithms on Noisy Devices [0.0]
  We present improved circuit based implementations for QFA algorithms recognizing the $ MOD_p $ problem using the Qiskit framework. We run the circuits on real IBM quantum devices but due to the limitation of the real quantum devices in the NISQ era, the results are heavily affected by the noise.
  arXiv  Detail & Related papers  (2021-05-13T10:51:28Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Quantum Büchi Automata [4.998632546280976]
  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.
  arXiv  Detail & Related papers  (2018-04-24T12:23:49Z)

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.