論文の概要: A SAT Solver and Computer Algebra Attack on the Minimum Kochen-Specker
Problem
- arxiv url: http://arxiv.org/abs/2306.13319v4
- Date: Mon, 18 Sep 2023 15:19:35 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-19 23:17:55.961653
- 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要約: 3次元の最小KSベクトル系を見つけるという問題は、55年以上も頑固に開き続けている。
我々のアプローチは、3次元のKS系が少なくとも24個のベクトルを含む必要があることを示している。
ここでは、KS問題の下位境界が 41.6 TiB である最初のコンピュータ検証証明証明書を、23 の順に提示する。
- 参考スコア（独自算出の注目度）: 16.513903417371413
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: One of the fundamental results in quantum foundations 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, the problem of finding the minimum KS vector system in three dimensions
has remained stubbornly open for over 55 years. In this paper, we present a new
method based on a combination of a Boolean satisfiability (SAT) solver and a
computer algebra system (CAS) to address this problem. Our approach shows that
a KS system in three dimensions must contain at least 24 vectors. Our SAT+CAS
method is over 35,000 times faster at deriving the previously known lower bound
of 22 vectors than the prior CAS-based searches. More importantly, we provide
the first computer-verifiable proof certificate of a lower bound in the KS
problem with a proof size of 41.6 TiB in order 23. The increase in efficiency
is due to the fact we are able to exploit the powerful combinatorial
search-with-learning capabilities of SAT solvers, together with the CAS-based
isomorph-free exhaustive method of orderly generation of graphs. To the best of
our knowledge, our work is the first application of a SAT+CAS method to a
problem in the realm of quantum foundations and the first lower bound in the
minimum Kochen-Specker problem with a computer-verifiable proof certificate.
- Abstract（参考訳）: 量子基礎の基本的な結果の1つがkochen-specker(ks)定理であり、量子力学と一致する予測を持つ理論は文脈的、すなわち量子観測は既存の値を明らかにするものとしては理解できないと述べる。
この定理はKSベクトル系と呼ばれる数学的対象の存在に基づいている。
多くのKSベクトル系が知られているが、最小のKSベクトル系を3次元で見つけるという問題は55年以上も頑固に開き続けている。
本稿では,この問題を解決するために,ブール充足可能性 (SAT) と計算機代数システム (CAS) を組み合わせた新しい手法を提案する。
本手法は,3次元のks系が少なくとも24ベクトルを含む必要があることを示す。
SAT+CAS法は従来のCAS検索よりも22ベクトルの既知下界の導出において35,000倍高速である。
より重要なことは、KS問題の低い境界のコンピュータで検証可能な最初の証明証明書を、23で41.6 TiBの証明サイズで提供することである。
この効率の向上は、SATソルバの強力な組合せ探索学習能力と、CASをベースとしたグラフを秩序に生成するイソモルフィックフリーの徹底的な方法を利用することができるという事実による。
我々の研究は、量子基礎の領域における問題に対する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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。