論文の概要: Complexity of Satisfiability in Kochen-Specker Partial Boolean Algebras
- arxiv url: http://arxiv.org/abs/2602.24164v1
- Date: Fri, 27 Feb 2026 16:43:13 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-02 19:48:24.520315
- Title: Complexity of Satisfiability in Kochen-Specker Partial Boolean Algebras
- Title（参考訳）: Kochen-Specker部分ブール代数における満足度の複雑さ
- Authors: Anuj Dawar, Nihil Shah,
- Abstract要約: 非変数部分ブール代数のクラスに対する満足度問題はNP完全であることを示す。
また、すべてのヒルベルト空間とすべての有限次元ヒルベルト空間のクラスに対する満足性問題は決定不能であることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Kochen-Specker no-go theorem established that hidden-variable theories in quantum mechanics necessarily admit contextuality. This theorem is formally stated in terms of the partial Boolean algebra structure of projectors on a Hilbert space. Each partial Boolean algebra provides a semantics for interpreting propositional logic. In this paper, we examine the complexity of propositional satisfiablity for various classes of partial Boolean algebras. We first show that the satisfiability problem for the class of non-trivial partial Boolean algebras is NP-complete. Next, we consider the satisfiability problem for the class of partial Boolean algebras arising from projectors on finite dimensional Hilbert spaces. For real Hilbert spaces of dimension greater 2 and any complex Hilbert spaces of dimension greater than 3, we demonstrate that the satisfiablity problem is complete for the existential theory of the reals. Interestingly, the proofs of these results make use of Kochen-Specker sets as gadgets. As a corollary, we conclude that deciding quantum homomorphism in these fixed dimensions are also complete for the existential theory of the reals. Finally, we show that the satisfiability problems for the class of all Hilbert spaces and all finite-dimensional Hilbert spaces is undecidable.
- Abstract（参考訳）: Kochen-Specker no-go定理は、量子力学における隠れ変数理論は必ずしも文脈性を認めることを証明した。
この定理は、ヒルベルト空間上の射影体の部分ブール代数構造の観点から正式に述べられている。
各部分ブール代数は命題論理を解釈するための意味論を提供する。
本稿では,部分ブール代数の様々なクラスに対する命題満足度の複雑性について検討する。
まず、非自明な部分ブール代数のクラスに対する満足度問題はNP完全であることを示す。
次に、有限次元ヒルベルト空間上のプロジェクターから生じる部分ブール代数のクラスに対する満足度問題を考察する。
次元が 2 より大きい実ヒルベルト空間と次元が 3 より大きい任意の複素ヒルベルト空間に対して、実数の存在理論に対して満足度問題は完備であることを示す。
興味深いことに、これらの結果の証明はKochen-Specker集合をガジェットとして利用している。
結論として、これらの固定次元における量子準同型を決定することは、実数の存在理論に対しても完備である。
最後に、すべてのヒルベルト空間とすべての有限次元ヒルベルト空間のクラスに対する満足性問題は決定不能であることを示す。
関連論文リスト
- Finite-dimensional Lie algebras in bosonic quantum dynamics: The single-mode case [0.0]
単モードおよび自己相互作用ボゾン系の量子力学において生じる有限次元リー代数の数学的性質を研究、分類、探索する。
論文 参考訳（メタデータ） (2025-11-10T10:46:22Z) - Real Quantum Mechanics in a Kahler Space [0.0]
複素ヒルベルト空間で定式化された標準量子力学は、実カフラー空間において等価な再構成を許容することを示す。
このフレームワークは、重要な利点を提供しながら、量子力学の本質的な特徴をすべて保存する。
論文 参考訳（メタデータ） (2025-04-23T16:01:25Z) - Towards entropic uncertainty relations for non-regular Hilbert spaces [44.99833362998488]
エントロピック不確実性関係 (EUR) はヒルベルト空間とその双対に固有の不等式から生じる。
特異ヒルベルト空間の文脈におけるこれらの EUR の解析は未解決である。
論文 参考訳（メタデータ） (2025-03-24T23:41:50Z) - Beyond trace class -- Tensor products of Hilbert spaces and operator ideals in quantum physics [0.0]
バナッハ作用素のイデアルは量子物理学と量子情報理論の基礎と哲学に潜んでいる。
我々はヒルベルト空間 $Hotimes (K otimes L)$ と $(H otimes K) otimes L$ (Theorem 3.8) の間の正準同型を確立し、トレースクラス作用素の役割を再考する。
ヒルベルト・シュミット作用素のクラスの有効性や、2つの複素空間$H otimes K$ (Proposition 3.4) のテンソル積の暗黙のバナッハ作用素の理想表現など、いくつかの応用が特定されている。
論文 参考訳（メタデータ） (2023-08-08T23:37:02Z) - The Schmidt rank for the commuting operator framework [58.720142291102135]
シュミットランク(Schmidt rank)は、純粋な二部状態の絡み合い次元の尺度である。
我々はSchmidtランクを通勤演算子フレームワークに一般化する。
バイパーティイト状態を分析し、シュミットランクをいくつかの例で計算する。
論文 参考訳（メタデータ） (2023-07-21T14:37:33Z) - Connecting classical finite exchangeability to quantum theory [45.76759085727843]
交換性は確率論と統計学の基本的な概念である。
観測順序が重要でない状況のモデル化を可能にする。
両定理が有限交換可能な列に対して成り立たないことはよく知られている。
論文 参考訳（メタデータ） (2023-06-06T17:15:19Z) - Continuous percolation in a Hilbert space for a large system of qubits [58.720142291102135]
パーコレーション遷移は無限クラスターの出現によって定義される。
ヒルベルト空間の指数的に増加する次元性は、有限サイズの超球面による被覆を非効率にすることを示す。
コンパクトな距離空間におけるパーコレーション遷移への我々のアプローチは、他の文脈での厳密な処理に有用である。
論文 参考訳（メタデータ） (2022-10-15T13:53:21Z) - Positive maps and entanglement in real Hilbert spaces [5.926203312586108]
実数体上の全行列代数に作用する正の写像を研究する。
実写像が正の複素化を受け入れるために必要な十分条件を提供する。
元の PPT-二乗予想が実写像に対して異なる予想であることを示す。
論文 参考訳（メタデータ） (2022-07-06T08:25:55Z) - Axioms for the category of Hilbert spaces [0.0]
我々は、圏がヒルベルト空間の間の連続線型函数と同値であることを保証する公理を提供する。
これは、フォン・ノイマン、マッキー、ヤウチ、ピロン、アブラムスキー、コーケなどの再構成プログラムで提起された量子理論の数学的基礎に関する問題に対処する。
論文 参考訳（メタデータ） (2021-09-15T16:41:23Z) - Entanglement and Complexity of Purification in (1+1)-dimensional free
Conformal Field Theories [55.53519491066413]
拡大されたヒルベルト空間では、場の量子論の混合状態を部分的トレースとしてエンコードする純粋な状態が見つかる。
自由ボゾン場とイジング共形場の理論の真空中の2つの間隔でこれらの量を分析する。
論文 参考訳（メタデータ） (2020-09-24T18:00:13Z) - A refinement of Reznick's Positivstellensatz with applications to
quantum information theory [72.8349503901712]
ヒルベルトの17番目の問題において、アルティンはいくつかの変数の任意の正定値が2つの平方和の商として書けることを示した。
レズニックはアルティンの結果の分母は常に変数の平方ノルムの$N$-次パワーとして選択できることを示した。
論文 参考訳（メタデータ） (2019-09-04T11:46:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。