論文の概要: Quantum Büchi Automata

• arxiv url: http://arxiv.org/abs/1804.08982v2
• Date: Fri, 26 Jul 2024 13:51:28 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-29 18:55:44.327071
• Title: Quantum Büchi Automata
• Title（参考訳）: 量子ビューチオートマタ
• Authors: Qisheng Wang, Mingsheng Ying,
• Abstract要約: QBAが認識する$omega$-Languagesのクラスを、ほぼ確実に、厳密で非制限しきい値セマンティクスで紹介する。 QBAによって認識される$omega$-Languageの少なくとも4つの実質的に異なるクラスしか存在しないことが示されている(数えきれないほど無限である)。 従来の$omega$-LanguagesとQBAsの関係は,ポンプ補題を用いて明らかにした。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: 量子有限オートマトン(QFA)は文献で広く研究されている。 本稿では,QFAを拡張した量子系の長期挙動をモデル化するために,無限語上の量子B\「内オートマトン」(QBA)を定義し,体系的に研究する。 QBAが認識する$\omega$-Languagesのクラスを、ほぼ確実に、厳密で非制限しきい値意味論で紹介する。 いくつかのポンプ補題とQBAの閉鎖特性が証明された。 QBAの意思決定問題について検討した。 特に、QBAによって認識される$\omega$-Languageの少なくとも4つの実質的に異なるクラスが存在する(数えきれないほど無限である)。 従来の$\omega$-LanguagesとQBAの関係は,ポンプ補題を用いて明らかにした。 QBAによって認識される$\omega$- languageも、ほぼ確実なセマンティクスの下で見つけることができ、$\omega$-context-freeではない。

関連論文リスト

• Oracle Separations for the Quantum-Classical Polynomial Hierarchy [0.0]
  量子古典的階層 QCPH について検討する。これは、交互古典的量子化器の定数数で解ける言語のクラスである。 我々は、量子アルゴリズムに新しい切り換え補題を与えるが、これは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2024-10-24T18:12:03Z)
• CountCrypt: Quantum Cryptography between QCMA and PP [7.408475650692233]
  我々は、BQP = QCMAであるが量子計算古典通信鍵交換、QCCCコミットメント、および2ラウンドの量子鍵分布が存在する量子オラクルを構築する。 また、QCCC鍵交換、QCCCコミットメント、および2ラウンドの量子鍵分布が、すべて片道パズルの構築に利用できることを示す。
  論文  参考訳（メタデータ） (2024-10-18T18:04:27Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms [65.268245109828]
  我々はカーンズのSQオラクルとヴァリアントの弱い評価オラクルからインスピレーションを得ます。 評価クエリから学習するための非条件の下限を出力する,広範かつ直感的なフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-10-26T18:23:21Z)
• Deterministic Construction of QFAs based on the Quantum Fingerprinting Technique [0.0]
  言語を$MOD_p$と認識する量子有限オートマトンは、古典的有限オートマトンに対して指数関数的な優位性を持つ。 我々は、約束問題$Palindrome_s$に対してQFAを構築し、IBMQシミュレータ上でこのQFAを実装した。
  論文  参考訳（メタデータ） (2022-12-29T19:33:56Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• Cost-efficient QFA Algorithm for Quantum Computers [0.0]
  修正されたムーア・クラッチフィールド量子有限オートマトン (MCQFA) アルゴリズムを言語 $mathttMOD_p$ に対して提案する。 文献で与えられた元のアルゴリズムの実装と比較して,基底ゲートが少なくて短い量子プログラムが得られる。
  論文  参考訳（メタデータ） (2021-07-05T20:41:18Z)
• Quantum double aspects of surface code models [77.34726150561087]
  基礎となる量子double $D(G)$対称性を持つ正方格子上でのフォールトトレラント量子コンピューティングの北エフモデルを再検討する。 有限次元ホップ代数$H$に基づいて、我々の構成がどのように$D(H)$モデルに一般化するかを示す。
  論文  参考訳（メタデータ） (2021-06-25T17:03:38Z)
• Quantum Differentially Private Sparse Regression Learning [132.1981461292324]
  我々は、スパース回帰問題を解くために、効率的な量子微分プライベート(QDP)ラッソ推定器を考案する。 最後に、QDP Lasso はプライバシー保証付きで $tildeO(N-2/3)$ に近い最適ユーティリティを実現していることを示す。
  論文  参考訳（メタデータ） (2020-07-23T10:50:42Z)
• The Power of a Single Qubit: Two-way Quantum Finite Automata and the Word Problem [0.0]
  量子および古典状態を持つ2方向有限オートマトン(2QCFA)は、量子部分が非常に限定された量子計算のモデルである。 2QCFA は期待時間で $L_eq=am bm :m mathbbN$ を認識でき、a,b*:w CFA CFA は期待指数時間で parindrome$ を認識できることを示す。
  論文  参考訳（メタデータ） (2020-03-22T12:46:37Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。