論文の概要: A SAT Solver and Computer Algebra Attack on the Minimum Kochen-Specker Problem

• arxiv url: http://arxiv.org/abs/2306.13319v2
• Date: Wed, 12 Jul 2023 15:38:03 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-13 18:47:09.016890
• Title: A SAT Solver and Computer Algebra Attack on the Minimum Kochen-Specker Problem
• Title（参考訳）: 最小kochen-specker問題に対するsatソルバと計算機代数学攻撃
• Authors: Zhengyu Li, Curtis Bright, Vijay Ganesh
• Abstract要約: Kochen-Specker (KS) の定理は、予測が量子力学と一致する任意の理論は文脈的でなければならないという定理である。 最小のKSベクトル系を見つけるという問題は55年以上も頑固に開き続けている。 本稿では,SATソルバと計算機代数システム(CAS)を組み合わせた新しい手法を提案する。
• 参考スコア（独自算出の注目度）: 17.84358352233607
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: One of the foundational results in quantum mechanics is the Kochen-Specker (KS) theorem, which states that any theory whose predictions agree with quantum mechanics must be contextual, i.e., a quantum observation cannot be understood as revealing a pre-existing value. The theorem hinges on the existence of a mathematical object called a KS vector system. While many KS vector systems are known to exist, the problem of finding the minimum KS vector system has remained stubbornly open for over 55 years, despite significant attempts by leading scientists and mathematicians. In this paper, we present a new method based on a combination of a SAT solver and a computer algebra system (CAS) to address this problem. Our approach shows that a KS system must contain at least 24 vectors and is about 35,000 times more efficient compared to the previous best CAS-based computational methods. Moreover, we generate certificates that provide an independent verification of the results. The increase in efficiency derives from the fact we are able to exploit the powerful combinatorial search-with-learning capabilities of a SAT solver together with the isomorph-free exhaustive generation methods of a CAS. The quest for the minimum KS vector system is motivated by myriad applications such as simplifying experimental tests of contextuality, zero-error classical communication, dimension witnessing, and the security of certain quantum cryptographic protocols. To the best of our knowledge, this is the first application of a novel SAT+CAS system to a problem in the realm of quantum foundations, and the first verified lower bound of the minimum Kochen-Specker problem.
• Abstract（参考訳）: 量子力学における基礎的な結果の1つはkochen-specker(ks)定理であり、量子力学と一致する予測を持つ理論は文脈的、すなわち量子観測は既存の値を明らかにするものとしては理解できないと述べる。 この定理はKSベクトル系と呼ばれる数学的対象の存在に基づいている。 多くのKSベクトル系が存在することが知られているが、最小のKSベクトル系を見つけるという問題は、先進的な科学者や数学者による大きな試みにもかかわらず、55年以上も頑固に開かれている。 本稿では,SATソルバと計算機代数システム(CAS)を組み合わせた新しい手法を提案する。 提案手法では, ks システムは少なくとも 24 個のベクトルを含む必要があり, 従来の cas ベースの計算手法に比べて約 35,000 倍の効率が期待できる。 さらに,結果の独立した検証を行う証明書も生成する。 効率の向上は、SATソルバの強力な組合せ探索と学習能力と、CASの等方性のない排他的生成手法を併用できるという事実から導かれる。 最小KSベクトルシステムの探求は、文脈性の実験的なテスト、ゼロエラー古典通信、次元目撃、特定の量子暗号プロトコルのセキュリティなど、無数の応用によって動機付けられている。 我々の知る限りでは、これは量子基底の領域における問題に対する新しいSAT+CASシステムの最初の応用であり、最小コチェン=スペクター問題の最初の検証された下界である。

関連論文リスト

• Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms [65.268245109828]
  我々はカーンズのSQオラクルとヴァリアントの弱い評価オラクルからインスピレーションを得ます。 評価クエリから学習するための非条件の下限を出力する,広範かつ直感的なフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-10-26T18:23:21Z)
• Quantum Bayesian Optimization [64.58749619145908]
  本稿では,量子ガウスプロセスアップパー信頼度境界(Q-GP-UCB)アルゴリズムを提案する。 O(polylog T) は古典的設定における Omega(sqrt(T)) の左下限よりもかなり小さい。 線形核を持つQ-GP-UCBは、新しい信頼楕円体解析により、量子線形 UCB アルゴリズムよりも小さな後悔を実現する。
  論文  参考訳（メタデータ） (2023-10-09T03:10:42Z)
• A hybrid Quantum proposal to deal with 3-SAT problem [75.38606213726906]
  本稿では,3SAT問題を解くためのハイブリッド量子コンピューティング戦略について述べる。 この近似の性能は、量子コンピューティングの観点から3-SATを扱う際に、一連の代表的なシナリオで検証されている。
  論文  参考訳（メタデータ） (2023-06-07T12:19:22Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  量子性の検定は、古典的検証者が証明者が古典的でないことを(のみ)証明できるプロトコルである。 我々は、あるテンプレートに従う量子性のテストを行い、(Kalai et al., 2022)のような最近の提案を捉えた。 すなわち、同じプロトコルは、証明可能なランダム性や古典的な量子計算のデリゲートといったアプリケーションの中心にあるビルディングブロックであるqubitの認定に使用できる。
  論文  参考訳（メタデータ） (2023-03-02T14:18:17Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement [0.0]
  サビッチの定理は、NPSPACE計算はPSPACEでシミュレートできると述べている。 SQCMASPACE=NEXP のように、サビッチの定理の量子アナログが成り立たないことを示す。 SQCMASPACE を[Chailloux, Sattath, 2012] のスパース分離ハミルトン問題に組み込む方法を示す (QMA(2)-complete for 1/poly promise gap)。
  論文  参考訳（メタデータ） (2022-06-10T17:35:10Z)
• Variational quantum solutions to the Shortest Vector Problem [6.126929553818864]
  最短ベクトル問題(SVP)は、最短ベクトル問題(SVP)として知られる問題である。 この問題は量子コンピュータでも難しいと考えられており、量子後暗号において重要な役割を担っている。 本研究では,(効率のよい)ノイズ中間量子(NISQ)デバイスを用いてSVPを解く方法について検討する。
  論文  参考訳（メタデータ） (2022-02-14T14:27:38Z)
• Contextuality in composite systems: the role of entanglement in the Kochen-Specker theorem [0.0]
  Kochen-Specker (KS) の定理は、単一量子系の非古典性を明らかにする。 ベルの定理と絡み合いは、複合量子系の非古典性に関するものである。
  論文  参考訳（メタデータ） (2021-09-28T10:10:53Z)
• Simpler Proofs of Quantumness [16.12500804569801]
  量子性の証明は、量子デバイスが古典的なデバイスでは不可能な計算タスクを実行できることを示す方法である。 現在、量子性の証明を示すための3つのアプローチがある。 トラップドアの爪のない関数をベースとした量子性の2次元証明(Challenge-Response)を与える。
  論文  参考訳（メタデータ） (2020-05-11T01:31:18Z)

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

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