Learning Quantum Finite Automata with Queries

• URL: http://arxiv.org/abs/2111.14041v2
• Date: Sun, 12 Nov 2023 16:11:12 GMT
• Title: Learning Quantum Finite Automata with Queries
• Authors: Daowen Qiu
• Abstract summary: 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.
• Score: 2.28438857884398
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: {\it Learning finite automata} (termed as {\it model learning}) has become an important field in machine learning and has been useful realistic applications. Quantum finite automata (QFA) are simple models of quantum computers with finite memory. Due to their simplicity, QFA have well physical realizability, but one-way QFA still have essential advantages over classical finite automata with regard to state complexity (two-way QFA are more powerful than classical finite automata in computation ability as well). As a different problem in {\it quantum learning theory} and {\it quantum machine learning}, in this paper, our purpose is to initiate the study of {\it learning QFA with queries} (naturally it may be termed as {\it quantum model learning}), and the main results are regarding learning two basic one-way QFA: (1) We propose a learning algorithm for measure-once one-way QFA (MO-1QFA) with query complexity of polynomial time; (2) We propose a learning algorithm for measure-many one-way QFA (MM-1QFA) with query complexity of polynomial-time, as well.

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)
• 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)
• Foundations of Quantum Federated Learning Over Classical and Quantum Networks [59.121263013213756]
  Quantum federated learning (QFL) is a novel framework that integrates the advantages of classical federated learning (FL) with the computational power of quantum technologies. QFL can be deployed over both classical and quantum communication networks.
  arXiv  Detail & Related papers  (2023-10-23T02:56:00Z)
• Implications of Deep Circuits in Improving Quality of Quantum Question Answering [0.0]
  We have performed question classification on questions from two classes of SelQA (Selection-based Question Answering) dataset. We also use these classification results with our own rule-based QA system and observe significant performance improvement.
  arXiv  Detail & Related papers  (2023-05-12T10:52:13Z)
• Quantum Imitation Learning [74.15588381240795]
  We propose quantum imitation learning (QIL) with a hope to utilize quantum advantage to speed up IL. We develop two QIL algorithms, quantum behavioural cloning (Q-BC) and quantum generative adversarial imitation learning (Q-GAIL) Experiment results demonstrate that both Q-BC and Q-GAIL can achieve comparable performance compared to classical counterparts.
  arXiv  Detail & Related papers  (2023-04-04T12:47:35Z)
• 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)
• 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)
• A didactic approach to quantum machine learning with a single qubit [68.8204255655161]
  We focus on the case of learning with a single qubit, using data re-uploading techniques. We implement the different proposed formulations in toy and real-world datasets using the qiskit quantum computing SDK.
  arXiv  Detail & Related papers  (2022-11-23T18:25:32Z)
• Recent Advances for Quantum Neural Networks in Generative Learning [98.88205308106778]
  Quantum generative learning models (QGLMs) may surpass their classical counterparts. We review the current progress of QGLMs from the perspective of machine learning. We discuss the potential applications of QGLMs in both conventional machine learning tasks and quantum physics.
  arXiv  Detail & Related papers  (2022-06-07T07:32:57Z)
• State complexity of one-way quantum finite automata together with classical states [2.3097706741644686]
  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.
  arXiv  Detail & Related papers  (2021-12-07T15:00:18Z)
• 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.