論文の概要: StoqMA vs. MA: the power of error reduction
- arxiv url: http://arxiv.org/abs/2010.02835v3
- Date: Mon, 19 Apr 2021 19:56:50 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-29 20:12:30.320644
- Title: StoqMA vs. MA: the power of error reduction
- Title(参考訳): StoqMA vs. MA:エラー低減の力
- Authors: Dorit Aharonov, Alex B. Grilo, Yupan Liu
- Abstract要約: StoqMAは、確率的局所ハミルトニアンの計算硬度を特徴づける。
2006年にBravyi、Bessen、TerhalがStoqMAを定義して以来、StoqMAは引き続きオープンである。
- 参考スコア(独自算出の注目度): 1.6436293069942312
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: StoqMA characterizes the computational hardness of stoquastic local
Hamiltonians, which is a family of Hamiltonians that does not suffer from the
sign problem. Although error reduction is commonplace for many complexity
classes, such as BPP, BQP, MA, QMA, etc.,this property remains open for StoqMA
since Bravyi, Bessen and Terhal defined this class in 2006. In this note, we
show that error reduction forStoqMA will imply that StoqMA = MA.
- Abstract(参考訳): StoqMAは、符号問題に悩まされないハミルトンの族である確率的局所ハミルトニアン(英語版)の計算困難さを特徴づける。
BPP, BQP, MA, QMA など多くの複雑性クラスではエラー低減が一般的であるが、2006年に Bravyi, Bessen と Terhal が定義して以来、この性質は StoqMA にとってオープンである。
本稿では,StoqMAの誤差削減がStoqMA = MAとなることを示す。
関連論文リスト
- Local Hamiltonian Problem with succinct ground state is MA-Complete [0.788657961743755]
量子系の基底エネルギーを見つけることは、凝縮物質物理学と量子化学の基本的な問題である。
この問題に対処する既存の古典的アルゴリズムは、基底状態が簡潔な古典的記述を持つと仮定することが多い。
我々は,局所ハミルトン問題と簡潔な基底状態の複雑性について検討し,それがMA-Completeであることを証明した。
論文 参考訳(メタデータ) (2023-09-18T21:08:51Z) - Graph-Based Reductions for Parametric and Weighted MDPs [3.1542695050861544]
パラメトリックマルコフ決定過程における到達性低下の複雑さについて検討する。
計算複雑性の観点では、p が q よりも悪くないかを決定することは coETR 完全である。
論文 参考訳(メタデータ) (2023-05-09T19:33:43Z) - Learning Hidden Markov Models Using Conditional Samples [72.20944611510198]
本稿では,隠れマルコフモデル(HMM)の学習における計算複雑性について述べる。
本稿では,HMMの条件分布からサンプルを問合せする対話型アクセスモデルを提案する。
具体的には、正確な条件付き確率に対するクエリアクセスが可能な設定において、HMMを学習するための効率的なアルゴリズムを得る。
論文 参考訳(メタデータ) (2023-02-28T16:53:41Z) - MA2QL: A Minimalist Approach to Fully Decentralized Multi-Agent
Reinforcement Learning [63.46052494151171]
テキストマルチエージェント代替Q-ラーニング(MA2QL)を提案し、エージェントが順番にQ-ラーニングによってQ-関数を更新する。
各エージェントが各ターンで$varepsilon$-convergenceを保証した場合、それらの合同ポリシーはナッシュ均衡に収束する。
結果は、MA2QLが最小限の変更にもかかわらず、MA2QLの有効性を検証するIQLを一貫して上回っていることを示している。
論文 参考訳(メタデータ) (2022-09-17T04:54:32Z) - Sharp-MAML: Sharpness-Aware Model-Agnostic Meta Learning [71.26635165491105]
我々はシャープ・MAMLと呼ぶシャープネスを意識したMAMLアプローチを開発した。
Sharp-MAMLとその計算効率が,既存のMAMLベースラインより優れていることを実証的に実証した。
これは、二段階学習の文脈において、シャープネスを意識した最小化に関する最初の経験的および理論的研究である。
論文 参考訳(メタデータ) (2022-06-08T16:20:11Z) - The Accuracy vs. Sampling Overhead Trade-off in Quantum Error Mitigation
Using Monte Carlo-Based Channel Inversion [84.66087478797475]
量子誤差緩和(Quantum error mitigation, QEM)は、変分量子アルゴリズムの計算誤差を低減するための有望な手法の1つである。
我々はモンテカルロサンプリングに基づく実用的なチャネル反転戦略を考察し、さらなる計算誤差を導入する。
計算誤差が誤差のない結果の動的範囲と比較して小さい場合、ゲート数の平方根でスケールすることを示す。
論文 参考訳(メタデータ) (2022-01-20T00:05:01Z) - Reinforcement Learning in Linear MDPs: Constant Regret and
Representation Selection [136.4014229319618]
線形構造を持つ有限水平マルコフ決定過程(MDPs)における後悔最小化における状態-作用値関数の表現の役割について検討する。
まず,線形報酬関数を持つ任意のMDPにおいて,一貫した後悔を実現するために,Universally spaning optimal features (UNISOFT) と呼ばれる表現に必要条件を導出する。
論文 参考訳(メタデータ) (2021-10-27T22:07:08Z) - BERTifying the Hidden Markov Model for Multi-Source Weakly Supervised
Named Entity Recognition [57.2201011783393]
条件付き隠れマルコフモデル(CHMM)
CHMMは、入力トークンのBERT埋め込みからトークン単位の遷移と放出確率を予測する。
BERTベースのNERモデルを微調整し、ラベルをCHMMで推論する。
論文 参考訳(メタデータ) (2021-05-26T21:18:48Z) - Characterizing the intersection of QMA and coQMA [1.5863809575305414]
ここでは, F(QMA$cap$coQMA) と表される QMA$cap$coQMA の機能的類似が, 複雑性クラスである TFQMA (Total Functional QMA) に等しいことを示す。
TFQMA が BQP (FBQP) の関数アナログと等しいならば、QMA$cap$coQMA = BQP となる。
論文 参考訳(メタデータ) (2021-02-05T11:17:35Z) - Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic
Approximation [4.817429789586127]
基礎となるマルコフ連鎖が可逆で幾何学的にエルゴードである場合でも、誤差列に有界なホーフディングを得ることはできない。
平均二乗誤差は、ステップサイズシーケンスの条件の下で、$O(1/n)$の最適率を達成する。
論文 参考訳(メタデータ) (2020-02-07T01:52:21Z) - Pinned QMA: The power of fixing a few qubits in proofs [0.6299766708197883]
我々は、しばしば繰り返される測定によって単一の量子ビットをピン留めすると、通勤および確率的ハミルトニアンと共に既に普遍的な量子計算結果が得られることを示した。
そこで我々は1つのクリーンな量子ビットモデルのパワーを思い起こさせるピンニングの計算能力の包括的イメージを同定する。
論文 参考訳(メタデータ) (2020-01-10T19:20:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。