論文の概要: State complexity of one-way quantum finite automata together with
classical states
- arxiv url: http://arxiv.org/abs/2112.03746v2
- Date: Wed, 8 Dec 2021 04:17:40 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-05 07:50:48.676481
- Title: State complexity of one-way quantum finite automata together with
classical states
- Title（参考訳）: 古典状態と一方向量子有限オートマトンの状態複雑性
- Authors: Ligang Xiao and Daowen Qiu
- Abstract要約: 1方向量子有限オートマトンと古典状態(1QFAC) [Journal of Computer and System Sciences 81(2)359-375]
量子古典ハイブリッドモデルとして、1QFACはすべての正規言語を認識する。
いくつかの言語における1QFACの複雑性は、DFAや他の1QFAよりも本質的に優れていることが示されている。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: 一方向量子有限オートマトン (1QFAC) と古典状態 (Journal of Computer and System Sciences 81(2) (2015) 359--375] は、量子有限オートマトン (QFA) と決定論的有限オートマトン (DFA) を統合した新しい一方向量子有限オートマトン (1QFA) モデルである。
このモデルは古典状態を用いて量子状態の進化と測定を制御する。
量子古典ハイブリッドモデルとして、1QFACはすべての正規言語を認識する。
いくつかの言語における1QFACの複雑性は、DFAや他の1QFAよりも本質的に優れていることが示されている。
本稿では,1QFACにおける状態複雑性問題を明らかにすることを目的とする。
1) 量子基底状態数と1QFACの古典状態数の関係を特徴付けるQiuらによって与えられる境界を最適化し, 対応する最小DFAの状態数を用いて任意の正規言語を認識する。
2) 1QFAC の量子基底状態が認識能力を変化させることなく低減された場合,古典状態がいくつ必要かを示す上限を与える。
(3) 任意の正規言語を認識するための古典的状態数 1QFAC の下位境界を与え、その下限は与えられた言語が有限であれば正確である。
4) 1QFACはDFAや確率的有限オートマトン(PFA)よりも指数関数的に簡潔で,測度1QFA(MO-1QFA)、測度1QFA(MM-1QFA)、マルチレター1QFA(MM-1QFA)では認識できない正規言語を認識する。
(5) 1QFAC, MO-1QFAとマルチレター1QFAの関係を明らかにするとともに, マルチレター1QFAの状態数とDFAの量的関係を導出する。
関連論文リスト
- Toward Separating QMA from QCMA with a Classical Oracle [10.699704508276174]
QMAは効率的な量子検証器によって決定できる言語のクラスであり、QCMAは効率的な量子検証器が古典的な証人しか与えられない言語のクラスである。
量子クエリ複雑性における挑戦的な基本的なゴールは、これらのクラスに対する古典的なオラクル分離を見つけることである。
論文 参考訳（メタデータ） (2024-11-04T00:18:06Z) - A Framework for Quantum Finite-State Languages with Density Mapping [3.1133049660590615]
量子有限状態オートマトン(Quantum finite-state Automaticon, QFA)は、有限メモリを持つ量子系の進化をシミュレートする理論モデルである。
本稿では,QFAを構築し,シミュレーション精度を最大化するための,シンプルで直感的な方法を提供するフレームワークを提案する。
論文 参考訳（メタデータ） (2024-07-03T03:06:37Z) - Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms [65.268245109828]
我々はカーンズのSQオラクルとヴァリアントの弱い評価オラクルからインスピレーションを得ます。
評価クエリから学習するための非条件の下限を出力する,広範かつ直感的なフレームワークを提案する。
論文 参考訳（メタデータ） (2023-10-26T18:23:21Z) - Quantum Merlin-Arthur proof systems for synthesizing quantum states [0.0]
クラスNP合成における状態合成法について検討した。
我々は、最も自然な候補者の1つであるUQMA目撃者の家族が国家QMAであることを確認した。
状態QCMAが完全性を達成することを実証する。
論文 参考訳（メタデータ） (2023-03-03T12:14:07Z) - Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
量子性の検定は、古典的検証者が証明者が古典的でないことを(のみ)証明できるプロトコルである。
我々は、あるテンプレートに従う量子性のテストを行い、(Kalai et al., 2022)のような最近の提案を捉えた。
すなわち、同じプロトコルは、証明可能なランダム性や古典的な量子計算のデリゲートといったアプリケーションの中心にあるビルディングブロックであるqubitの認定に使用できる。
論文 参考訳（メタデータ） (2023-03-02T14:18:17Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Quantum Semantic Communications for Resource-Efficient Quantum Networking [52.3355619190963]
本稿では、量子機械学習と量子意味表現の進歩を活かした新しい量子意味通信(QSC)フレームワークを提案する。
提案手法は,高い量子セマンティック忠実度を達成しつつ,必要な量子通信資源の約50～75%の削減を実現する。
論文 参考訳（メタデータ） (2022-05-05T03:49:19Z) - Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。
我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。
任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
論文 参考訳（メタデータ） (2022-03-30T02:02:16Z) - Learning Quantum Finite Automata with Queries [2.28438857884398]
量子有限オートマトン (QFA) は有限メモリを持つ量子コンピュータの単純なモデルである。
本稿では,クエリの複雑度を考慮した測度オンス片道QFA(MO-1QFA)の学習アルゴリズムを提案する。
また,一方向一方向QFA(MM-1QFA)を問合せの複雑度で学習するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-11-28T03:26:47Z) - On the properties of the asymptotic incompatibility measure in
multiparameter quantum estimation [62.997667081978825]
Incompatibility (AI) は、ホレヴォとSLDスカラー境界の差を定量化する尺度である。
最大AI量は、$mu_sf min = 1/(d-1)$より大きい純度で特徴づけられる量子統計モデルに対してのみ達成可能であることを示す。
論文 参考訳（メタデータ） (2021-07-28T15:16:37Z) - Cost-efficient QFA Algorithm for Quantum Computers [0.0]
修正されたムーア・クラッチフィールド量子有限オートマトン (MCQFA) アルゴリズムを言語 $mathttMOD_p$ に対して提案する。
文献で与えられた元のアルゴリズムの実装と比較して,基底ゲートが少なくて短い量子プログラムが得られる。
論文 参考訳（メタデータ） (2021-07-05T20:41:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。