Fugu-MT 論文翻訳(概要): QMA has perfect completeness

論文の概要: QMA has perfect completeness

arxiv url: http://arxiv.org/abs/2609.13032v1
Date: Fri, 11 Sep 2026 16:31:43 GMT
ステータス: 翻訳完了
システム内更新日: 2026-09-15 07:38:31.807968
Title: QMA has perfect completeness
Title（参考訳）: QMAは完全な完全性を持っている
Abstract要約: すべての量子メルリン・アーサー証明系が完全であることを示す。私たちの建設は、Hadamard、Toffoli、および$X$ゲートのみを使用します。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We prove $\mathsf{QMA} = \mathsf{QMA_1}$, i.e., every quantum Merlin-Arthur proof system can be made perfectly complete. Our construction uses only Hadamard, Toffoli, and $X$ gates, yielding a universal gate set for $\mathsf{QMA_1}$. As a consequence, quantum $3$-SAT is $\mathsf{QMA}$-complete. The construction relativizes to classical oracles, so known classical-oracle separations of $\mathsf{QMA}$ from $\mathsf{QCMA}$ extend to $\mathsf{QMA_1}$.
Abstract（参考訳）: 我々は、$\mathsf{QMA} = \mathsf{QMA_1}$、すなわち全ての量子メルリン・アーサー証明系を完全に完備化できることを示す。私たちの構成では、Hadamard、Toffoli、および$X$ Gatesのみを使用し、$\mathsf{QMA_1}$の普遍ゲートセットを生成する。その結果、量子3$-SAT は $\mathsf{QMA}$-complete となる。この構成は古典的なオラクルに関係しており、古典的なオーラクルは$\mathsf{QMA}$から$\mathsf{QCMA}$へ拡張する。

関連論文リスト

An Optimal Analysis of the Product Test [42.29010058743949]
製品テストは、純多部量子状態が特定のテンソル分解に完全に絡み合っているかどうかを決定する。基本的なプロパティテストタスクであり、多くのアプリケーションがあるにもかかわらず、製品テストの正確な(最悪のケース)受け入れ確率曲線は、まだ完全には決定されていない。複雑性理論の応用として,Harrow-Montanaro還元の1ショット音響パラメータを$mathsfQMA(k)$から$mathsfQMA(2)$に改善した。
論文参考訳（メタデータ） (2026-07-23T16:17:44Z)
Factorization through Lorentz cones [43.57338639836868]
我々は、$(mathsfC_square,mathsfC$) が LFP を持つことを示す:$mathsfC$ が対称錐、すなわちローレンツ錐の直和である。量子情報理論における問題への応用についても論じる。
論文参考訳（メタデータ） (2026-06-26T08:08:34Z)
The Complexity of Stoquastic Sparse Hamiltonians [0.30079490585515334]
確率スパースハミルトン問題(mathsfStoqSH$)が$mathsfStoqMA$であることを示す。 Stoquastic Local Hamiltonian は $mathsfStoqMA$-hard であるため、$mathsfStoqSH$ は $mathsfStoqMA$-complete となる。また、$mathsfStoqMA(2)$の分離可能なバージョンが$mathsfStoqMAであることも示します。
論文参考訳（メタデータ） (2026-05-04T17:22:02Z)
QIP $ \subseteq $ AM(2QCFA) [0.0]
我々は、$mathsfPSPACE$は、Arthur-Merlin証明システムを持つ言語のクラスである$mathsfAM (2QCFA)$のサブセットであることを示す。我々のプロトコルは、有理値量子遷移のみを使用し、二重指数期待時間で実行される。
論文参考訳（メタデータ） (2025-08-28T17:22:31Z)
Quantum SAT Problems with Finite Sets of Projectors are Complete for a Plethora of Classes [0.0]
量子満足度(Quantum Satisfiability, QSAT)問題の新しい量子ビット不変量を示す。まず最初に、$mathsfBQP_1$, $mathsfcoRP$, $mathsfQCMA$に対して完備なqudit QSAT問題が存在することを証明します。次に、同じ複雑性を維持しながら、任意のQCSPを量子ビットの問題に還元できることを示す。
論文参考訳（メタデータ） (2025-06-08T17:59:55Z)
Towards a universal gateset for $\mathsf{QMA}_1$ [0.0]
我々は、シクロトミック場 $mathbbQ(zeta_2k),zeta_2k=e2pi i/2k$, $G_2k$ のすべてのゲートセットに対して、$mathbbQ(zeta_2k),zeta_2k=e2pi i/2k$ のすべてのゲートセットが普遍であることを証明する。また、キングによって定義されたガッペド・クリッドホモロジー問題も証明する。
論文参考訳（メタデータ） (2024-11-04T23:39:27Z)
The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文参考訳（メタデータ） (2024-10-26T06:21:42Z)
Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文参考訳（メタデータ） (2024-02-06T15:39:09Z)
SQ Lower Bounds for Learning Mixtures of Linear Classifiers [43.63696593768504]
この問題に対する既知のアルゴリズムは、一様混合の特別な場合であっても、本質的には最善であることを示す。重要な技術的要素は、独立した関心を持つかもしれない球面設計の新たな構築である。
論文参考訳（メタデータ） (2023-10-18T10:56:57Z)
SQ Lower Bounds for Learning Bounded Covariance GMMs [46.289382906761304]
P= sum_i=1k w_i MathcalN(boldsymbol mu_i,mathbf Sigma_i)$ という形で、分離されたガウスの混合を $mathbbRd$ で学習することに焦点を当てる。この問題に対する統計的クエリ(SQ)アルゴリズムは、少なくともdOmega (1/epsilon)$の複雑さを必要とすることを証明している。
論文参考訳（メタデータ） (2023-06-22T17:23:36Z)
Uncertainties in Quantum Measurements: A Quantum Tomography [52.77024349608834]
量子系 $S$ に関連する可観測物は非可換代数 $mathcal A_S$ を形成する。密度行列 $rho$ は可観測物の期待値から決定できると仮定される。アーベル代数は内部自己同型を持たないので、測定装置は可観測物の平均値を決定することができる。
論文参考訳（メタデータ） (2021-12-14T16:29:53Z)
On Submodular Contextual Bandits [92.45432756301231]
作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。 Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
論文参考訳（メタデータ） (2021-12-03T21:42:33Z)
Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文参考訳（メタデータ） (2021-08-19T16:16:48Z)
StoqMA meets distribution testing [0.0]
We provide a novel connection between $mathsfStoqMA$ and distribution testing via reversible circuits。いずれの変種も$mathsfStoqMA$は、任意の無作為な乱数ビットと完全音性を持たず、$mathsfNP$に含まれることを示す。我々の結果は、$mathsfMA subseteq mathsfStoqMA subseteq mathsfSBP$ [BBT06]という階層構造を崩壊させる一歩を踏み出した。
論文参考訳（メタデータ） (2020-11-11T12:30:42Z)

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