論文の概要: A SAT Solver and Computer Algebra Attack on the Minimum Kochen-Specker Problem
- arxiv url: http://arxiv.org/abs/2306.13319v7
- Date: Tue, 9 Apr 2024 20:44:22 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-11 19:35:32.030688
- Title: A SAT Solver and Computer Algebra Attack on the Minimum Kochen-Specker Problem
- Title（参考訳）: 最小コッチェンスペクトル問題に対するSATソルバーとコンピュータ代数攻撃
- Authors: Zhengyu Li, Curtis Bright, Vijay Ganesh,
- Abstract要約: 本稿では,ブール充足可能性解法と計算機代数システムを組み合わせた検証可能な新しい証明生成法を提案する。
提案手法は、3次元のKS系が少なくとも24個のベクトルを含む必要があることを示す。
また, KS問題に対して, 順序23の40.3 TiBの低い値のコンピュータ検証証明を初めて提供した。
- 参考スコア（独自算出の注目度）: 14.693394941317843
- License: http://creativecommons.org/licenses/by/4.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 (3D) has remained stubbornly open for over 55 years. To address the minimum KS problem, we present a new verifiable proof-producing method based on a combination of a Boolean satisfiability (SAT) solver and a computer algebra system (CAS) that uses an isomorph-free orderly generation technique that is very effective in pruning away large parts of the search space. Our method shows that a KS system in 3D must contain at least 24 vectors. We show that our sequential and parallel Cube-and-Conquer (CnC) SAT+CAS methods are significantly faster than SAT-only, CAS-only, and a prior CAS-based method of Uijlen and Westerbaan. Further, while our parallel pipeline is somewhat slower than the parallel CnC version of the recently introduced Satisfiability Modulo Theories (SMS) method, this is in part due to the overhead of proof generation. Finally, we provide the first computer-verifiable proof certificate of a lower bound to the KS problem with a size of 40.3 TiB in order 23.
- Abstract（参考訳）: 量子基盤の基本的な結果の1つは、Kochen-Specker (KS) の定理であり、この定理は、予測が量子力学と一致する理論は文脈的でなければならない、すなわち、量子観測は既存の値を明らかにするものとしては理解できない、と述べている。
この定理はKSベクトル系と呼ばれる数学的対象の存在に基づいている。
多くのKSベクトル系が知られているが、3次元の最小KSベクトル系(3D)を見つけるという問題は55年以上も頑固に開き続けている。
最小KS問題に対処するため,探索空間の大部分を抽出するのに非常に有効な等方性のない順序生成技術を用いて,ブール充足可能性 (SAT) と計算機代数システム (CAS) を組み合わせた検証可能な新しい証明生成手法を提案する。
提案手法は、3次元のKS系が少なくとも24個のベクトルを含む必要があることを示す。
逐次かつ並列なCube-and-Conquer (CnC) SAT+CAS法は,SAT法,CAS法,Uijlen法,Westerbaan法よりも大幅に高速であることを示す。
さらに、我々の並列パイプラインは、最近導入されたSatisfiability Modulo Theories (SMS) メソッドの並列CnCバージョンよりもやや遅いが、これは部分的には証明生成のオーバーヘッドのためである。
最後に,KS問題に対する下位境界が 40.3 TiB である最初のコンピュータ検証証明証明書を順序23で提供する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。