本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：工作論文
- 編號：工作論文 #332
- 日期：2026-03-18
摘要
量子 k-SAT 是確定是否存在垂直於一組向量的 n 量子位元狀態的問題，每個向量都位於 k 個量子位元的希爾伯特空間。同样，问题是确定特定类型的局部哈密顿量是否具有零能量的基态。我们考虑具有 n 个变量和 m = αn 子句的随机量子 k-SAT 公式，并询问在 α 的值是多少时这些公式不再可满足。我们证明随机量子 3-SAT 的阈值最多为 3.594。为了进行比较，来自统计物理学的令人信服的论据表明，经典的 3-SAT 阈值是 αc ≈ 4.267。对于较大的 k，我们表明量子阈值是一个比经典阈值更小的常数因子。我們的邊界透過確定某些小工具的令人滿意的子空間的通用等級來運作，然後使用微分方程技術來分析將超圖劃分為這些小工具的集合的各種演算法。