論文の概要: The Power of a Single Qubit: Two-way Quantum Finite Automata and the
Word Problem
- arxiv url: http://arxiv.org/abs/2003.09879v2
- Date: Tue, 28 Apr 2020 17:18:59 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-28 11:42:33.389159
- Title: The Power of a Single Qubit: Two-way Quantum Finite Automata and the
Word Problem
- Title（参考訳）: 単一量子ビットのパワー:二方向量子有限オートマタとワード問題
- Authors: Zachary Remscrim (MIT)
- Abstract要約: 量子および古典状態を持つ2方向有限オートマトン(2QCFA)は、量子部分が非常に限定された量子計算のモデルである。
2QCFA は期待時間で $L_eq=am bm :m mathbbN$ を認識でき、a,b*:w CFA CFA は期待指数時間で parindrome$ を認識できることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The two-way finite automaton with quantum and classical states (2QCFA),
defined by Ambainis and Watrous, is a model of quantum computation whose
quantum part is extremely limited; however, as they showed, 2QCFA are
surprisingly powerful: a 2QCFA, with a single qubit, can recognize, with
bounded error, the language $L_{eq}=\{a^m b^m :m \in \mathbb{N}\}$ in expected
polynomial time and the language $L_{pal}=\{w \in \{a,b\}^*:w \text{ is a
palindrome}\}$ in expected exponential time.
We further demonstrate the power of 2QCFA by showing that they can recognize
the word problems of many groups. In particular 2QCFA, with a single qubit and
algebraic number transition amplitudes, can recognize, with bounded error, the
word problem of any finitely generated virtually abelian group in expected
polynomial time, as well as the word problems of a large class of linear groups
in expected exponential time. This latter class (properly) includes all groups
with context-free word problem. We also exhibit results for 2QCFA with any
constant number of qubits.
As a corollary, we obtain a direct improvement on the original Ambainis and
Watrous result by showing that $L_{eq}$ can be recognized by a 2QCFA with
better parameters. As a further corollary, we show that 2QCFA can recognize
certain non-context-free languages in expected polynomial time.
In a companion paper, we prove matching lower bounds, thereby showing that
the class of languages recognizable with bounded error by a 2QCFA in expected
$\mathit{subexponential}$ time is properly contained in the class of languages
recognizable with bounded error by a 2QCFA in expected $\mathit{exponential}$
time.
- Abstract（参考訳）: ambainis と watrous によって定義された2方向有限オートマトン(英語版)(2qcfa)は、量子部分が非常に制限された量子計算のモデルであるが、2qcfa は驚くほど強力である: 1 量子ビットの 2qcfa は、有界な誤差で、$l_{eq}=\{a^m b^m :m \in \mathbb{n}\}$ の多項式時間と、$l_{pal}=\{w \in \{a,b\}^*:w \text{ is a palindrome}\}$ の予想指数時間で認識することができる。
さらに, 2qcfa のパワーを, 多くのグループの単語問題を認識できることを示し, 実証する。
特に、2QCFAは、単一の量子ビットおよび代数的数遷移振幅を持ち、有界誤差により、期待多項式時間における任意の有限生成のアーベル群のワード問題と期待指数時間における大きな種類の線形群のワード問題を認識することができる。
この後者のクラスは、文脈自由語問題を持つすべてのグループを含む。
また,定数の量子ビットを持つ2QCFAの結果も示す。
コーナリーとして、より優れたパラメータを持つ2QCFAで$L_{eq}$を認識できることを示し、元のアムバイニスとワトラスの結果を直接改善する。
さらに, 2QCFAは, 期待多項式時間において, 非文脈自由言語を認識可能であることを示す。
その結果, 2qcfa が予測する$\mathit{subexponential}$ time が,$\mathit{exponential}$ が予測された$\mathit{exponential}$ time の 2qcfa で認識可能な言語のクラスに適切に含まれていることが証明された。
関連論文リスト
- Classical versus quantum queries in quantum PCPs with classical proofs [0.3004066195320147]
量子古典PCPを一般化し、古典的な証明に$q$の量子クエリを適用できるようにします。
驚くべきことに、このことは、定数量子古典量に対して逆から定数への約束のギャップを増幅できることを示している。
約束のギャップは達成できるが、我々の結果は、$mathsfQCMA$に対する定型クエリ量子古典的PCPが存在しないという強い証拠を与える。
論文 参考訳（メタデータ） (2024-11-01T18:00:56Z) - The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文 参考訳（メタデータ） (2024-02-29T01:35:46Z) - The Entangled Quantum Polynomial Hierarchy Collapses [0.0]
絡み合った量子量子階層$mathsfQEPH$が第2レベルに崩壊することを示す。
また、量子重ね合わせ(古典的確率ではない)だけがこれらの階層の計算力を増大させることを示す。
論文 参考訳（メタデータ） (2024-01-02T22:25:56Z) - A polynomial quantum computing algorithm for solving the dualization
problem [75.38606213726906]
2つの単調素関数 $f:0,1n to 0,1$ と $g:0,1n to 0,1$ が与えられたとき、双対化問題は$g$が$f$の双対かどうかを決定することである。
本稿では,双対化問題の決定版を時間内に解く量子コンピューティングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-08-28T18:12:54Z) - Quantum and classical low-degree learning via a dimension-free Remez
inequality [52.12931955662553]
ハイパーグリッド上の関数をポリトーラス上の高調波拡張に関連付ける新しい方法を示す。
巡回群 $exp(2pi i k/K)_k=1K$ の積に対して函数の上限が$f$であることを示す。
我々は最近、超キューブやキュービット上の観測可能な観測値の低次学習を、同様に効率的に行う方法として、EI22, CHP, VZ22を引用して、新しい空間に拡張した。
論文 参考訳（メタデータ） (2023-01-04T04:15:40Z) - 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) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
量子アルゴリズムの設計と回路下界の一般接続を確立する。
我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
論文 参考訳（メタデータ） (2020-12-03T14:03:20Z) - MIP*=RE [9.42581332803306]
言語のクラス MIP* は、複数の量子プロバーサを共有する絡み合いと相互作用する古典的検証器によって決定できることを示す。
我々は、フォン・ノイマン代数のコンヌの理論の難解性を提供する。
論文 参考訳（メタデータ） (2020-01-13T16:32:40Z) - Quantum Büchi Automata [4.998632546280976]
QBAが認識する$omega$-Languagesのクラスを、ほぼ確実に、厳密で非制限しきい値セマンティクスで紹介する。
QBAによって認識される$omega$-Languageの少なくとも4つの実質的に異なるクラスしか存在しないことが示されている(数えきれないほど無限である)。
従来の$omega$-LanguagesとQBAsの関係は,ポンプ補題を用いて明らかにした。
論文 参考訳（メタデータ） (2018-04-24T12:23:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。