論文の概要: Quantum SAT Problems with Finite Sets of Projectors are Complete for a Plethora of Classes

• arxiv url: http://arxiv.org/abs/2506.07244v1
• Date: Sun, 08 Jun 2025 17:59:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-10 16:33:10.728905
• Title: Quantum SAT Problems with Finite Sets of Projectors are Complete for a Plethora of Classes
• Title（参考訳）: プロジェクタの有限集合における量子SAT問題
• Authors: Ricardo Rivera Cardoso, Alex Meiburg, Daniel Nagaj,
• Abstract要約: 量子満足度(Quantum Satisfiability, QSAT)問題の新しい量子ビット不変量を示す。 まず最初に、$mathsfBQP_1$, $mathsfcoRP$, $mathsfQCMA$に対して完備なqudit QSAT問題が存在することを証明します。 次に、同じ複雑性を維持しながら、任意のQCSPを量子ビットの問題に還元できることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Previously, all known variants of the Quantum Satisfiability (QSAT) problem, i.e. deciding whether a $k$-local ($k$-body) Hamiltonian is frustration-free, could be classified as being either in $\mathsf{P}$; or complete for $\mathsf{NP}$, $\mathsf{MA}$, or $\mathsf{QMA_1}$. Here, we demonstrate new qubit variants of this problem that are complete for $\mathsf{BQP_1}$, $\mathsf{coRP}$, $\mathsf{QCMA}$, $\mathsf{PI(coRP,NP)}$, $\mathsf{PI(BQP_1,NP)}$, $\mathsf{PI(BQP_1,MA)}$, $\mathsf{SoPU(coRP,NP)}$, $\mathsf{SoPU(BQP_1,NP)}$, and $\mathsf{SoPU(BQP_1,MA)}$. Our result implies that a complete classification of quantum constraint satisfaction problems (QCSPs), analogous to Schaefer's dichotomy theorem for classical CSPs, must either include these 13 classes, or otherwise show that some are equal. Additionally, our result showcases two new types of QSAT problems that can be decided efficiently, as well as the first nontrivial $\mathsf{BQP_1}$-complete problem. We first prove there are qudit QSAT problems that are complete for $\mathsf{BQP_1}$, $\mathsf{coRP}$, and $\mathsf{QCMA}$ by re-defining elements of the circuit-to-Hamiltonian transformation. We then show that any QCSP can be reduced to a problem in qubits while maintaining the same complexity - something believed not to be possible classically. The remaining six problems are obtained by considering "sums" and "products" of the first seven QSAT problems. Before this work, the QSAT problems generated in this way resulted in complete problems for $\mathsf{PI}$ and $\mathsf{SoPU}$ classes that were trivially equal to other known classes. We thus commence the study of these new and seemingly nontrivial classes. While [Meiburg, 2021] first sought to prove completeness for the first three classes, we note that his constructions are flawed. Here, we rework them and obtain improvements on the required qudit dimensionality.
• Abstract（参考訳）: 以前は、量子満足度(QSAT)問題のすべての既知の変種、すなわち、$k$-local$k$-body)ハミルトニアンがフラストレーションなしで、$\mathsf{P}$、$\mathsf{NP}$、$\mathsf{MA}$、$\mathsf{QMA_1}$のいずれかに分類できるかどうかを判断していた。 ここでは、この問題の新しいキュービット変種を、$\mathsf{BQP_1}$, $\mathsf{coRP}$, $\mathsf{PI(coRP,NP)}$, $\mathsf{PI(BQP_1,NP)}$, $\mathsf{PI(BQP_1,NP)}$, $\mathsf{SoPU(coRP,NP)}$, $\mathsf{SoPU(BQP_1,NP)}$, $\mathsf{SoPU(BQP_1,NP)}$で完全であることを示す。 この結果は、古典的CSPに対するシェーファーの二分法定理に類似した量子制約満足度問題(QCSP)の完全な分類が、これらの13のクラスを含むか、そうでなければそれらが等しいことを示す必要があることを示唆している。 さらに、この結果から、効率よく決定できる2つの新しいQSAT問題と、最初の非自明な$\mathsf{BQP_1}$-complete問題を示す。 まず、回路-ハミルトン変換の要素を再定義することで、$\mathsf{BQP_1}$, $\mathsf{coRP}$, $\mathsf{QCMA}$に対して完備なqudit QSAT問題が存在することを証明した。 次に、任意のQCSPを、同じ複雑性を維持しながら、量子ビットの問題に還元できることを示します。 残りの6つの問題は、最初の7つのQSAT問題の "sums" と "products" を考慮することで得られる。 この方法で生成されたQSAT問題は、他の既知のクラスと自明に等しい$\mathsf{PI}$および$\mathsf{SoPU}$クラスの完全な問題を引き起こした。 したがって、これらの新しく一見非自明なクラスの研究を開始する。 マイブルク,2021]は最初,最初の3つのクラスの完全性を証明しようとしたが,その構造に欠陥があることに留意する。 ここでは、それらを再設計し、必要なキューディット次元を改善する。

関連論文リスト

• 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)
• Quantum Sabotage Complexity [0.7812210699650152]
  ここでは$mathsfQ(f_mathsfsab)$を示し、$f_mathsfsab$の量子クエリ複雑性を示す。 f$がインデックス関数であるとき、$mathsfQ(f_mathsfsab)=Theta(sqrtmathsfsab)$は、$mathsfQ(f_mathsfsab)=Theta(sqrtmathsf)の可能性を除外する。
  論文  参考訳（メタデータ） (2024-08-22T17:57:58Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds [1.3927943269211591]
  本研究は、$mathsfPH$の量子検証に基づく3つの一般化を研究する。 まず、[GSSSY22] から、崩壊定理と$mathsfQCPH$に対するカルプ・リプトンの定理を含むいくつかの開問題を解く。 我々は、$mathsfpureQPH$に対する一方の誤り低減と、これらの量子変量$mathsfPH$に関する最初の境界を示す。
  論文  参考訳（メタデータ） (2024-01-03T09:12:25Z)
• Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
  マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。 我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
  論文  参考訳（メタデータ） (2022-07-28T17:50:53Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
  我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。 情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
  論文  参考訳（メタデータ） (2020-12-17T16:43:11Z)
• 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)

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

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