論文の概要: A Slice-Rank Drift Bound for Random Quantum \(k\)-SAT

• arxiv url: http://arxiv.org/abs/2607.23847v1
• Date: Sun, 26 Jul 2026 21:18:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-28 22:34:15.25307
• Title: A Slice-Rank Drift Bound for Random Quantum \(k\)-SAT
• Title（参考訳）: ランダム量子 \(k\)-SAT のためのスライスランクドリフト境界
• Abstract要約: 我々は、ランダム量子(k)-SATの満足度しきい値に新しい上限を証明した。 この改善は (k) の小さな値においても重要であり、順序境界(2k/k) を与える。 この証明は、ジェネリック量子飽和性の幾何学的定式化と、全満足部分空間の次元デカイ解析を組み合わせる。
• 参考スコア（独自算出の注目度）: 0.0609170287691728
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Random quantum satisfiability is a natural quantum analogue of random constraint satisfaction and a basic model for frustration-free local Hamiltonians. Despite extensive work on its satisfiable and unsatisfiable regimes, the quantitative location of the random quantum \(k\)-SAT threshold has remained poorly understood, with the best general upper bounds leaving a large gap to the known lower bounds. In this paper we prove a new upper bound on the satisfiability threshold of random quantum \(k\)-SAT. Our result improves the previously known asymptotic upper bound by a factor of order \(k\), giving a bound of order \(2^k/k\). The improvement is also significant at small values of \(k\); in particular, for random quantum \(3\)-SAT we obtain a substantially smaller explicit upper bound than the one previously available. The proof combines the geometric formulation of generic quantum satisfiability with a dimension-decay analysis of the full satisfying subspace. The key input is a multiplicative Shearer-type inequality for tensor-product subspaces, which quantifies how global dimension forces nontrivial local dimension on typical sets of qubits.
• Abstract（参考訳）: ランダム量子満足度(英: Random quantum satisfiability)は、ランダムな制約満足度の自然な量子アナログであり、フラストレーションのない局所ハミルトンの基本的なモデルである。 満足できる状態と満足できない状態に関する広範な研究にもかかわらず、ランダム量子 \(k\)-SAT しきい値の定量的な位置はよく分かっておらず、最も一般的な上界は既知の下界に大きなギャップを残している。 本稿では、ランダム量子 \(k\)-SAT の満足度しきい値に新しい上限を証明した。 我々の結果は、既知の漸近上界を次数 \(k\) の因子によって改善し、次数 \(2^k/k\) の有界を与える。 この改善は、特にランダム量子 \(3\)-SAT に対して、より小さい明示的な上界を得る。 この証明は、ジェネリック量子飽和性の幾何学的定式化と、全満足部分空間の次元デカイ解析を組み合わせる。 キーインプットはテンソル積部分空間に対する乗法的シーラー型不等式であり、これは大域次元が典型的量子ビット集合上で非自明な局所次元をいかに強制するかを定量化するものである。

関連論文リスト

• A Lower Bound Framework for Quantum Functional Estimation [13.491187998442596]
  我々は、$d$次元量子状態の関数を推定するための下界の証明のための統一的なフレームワークを開発する。 このフレームワークは、Haar-randomのモーメントエンコーディングプロセスとモーメントマッチングと最適な近似を組み合わせる。
  論文  参考訳（メタデータ） (2026-08-03T17:59:11Z)
• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  重み付き確率変数に対する新しい量子平均推定器を開発した。 尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。 凸目的関数に対して,量子射影勾配降下法を提案する。
  論文  参考訳（メタデータ） (2026-07-28T09:29:37Z)
• Multiple Quantum Hypothesis Testing: One-Shot Pairwise Bounds and Sharp Asymptotics [13.098901971644656]
  一対誤差の和で最小誤差確率の次元自由一発上限を確立する。 最小誤差確率は、任意の定数まで、トレース調和平均量によって特徴づけられることを示す。
  論文  参考訳（メタデータ） (2026-06-04T14:49:12Z)
• Hysteretic squashed entanglement in many-body quantum systems [42.085941481155295]
  多体量子系の絡み合いは空間領域に分散する。 本研究では,二つの領域間の真の量子相関を測る条件付きエンタングルメントである,ヒステリックエンタングルメント$T_sq$を提案する。 我々は、T_sq$が隣接するサブシステムと長距離サブシステムの両方で真の量子相関を検出できることを示した。
  論文  参考訳（メタデータ） (2026-03-10T17:00:49Z)
• The Cumulants Expansion Approach: The Good, The Bad and The Ugly [0.0]
  平均場近似は平均場近似として広く知られ、量子物理学を通して日常的に用いられる。 量子力学と量子情報における2つの問題、すなわち、双極子-双極子の相互作用する原子鎖の集合的放射散逸について論じる。 近似がより高い順序でより良く働くように、滑らかで収束的な振る舞いが見つかる。 後者は平均場を超えても役に立たないことが判明し、たとえ小さなシステムのサイズであっても、数値的に困難であり、部分的には非物理的解に悩まされる。
  論文  参考訳（メタデータ） (2025-11-25T09:37:31Z)
• SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions [50.20087216230159]
  統計的クエリモデルにおける非ガウス成分分析(NGCA)の複雑さについて検討する。 本研究は, NGCAの場合, モーメントマッチング条件のみにおいて, ほぼ最適SQ下限を証明した。
  論文  参考訳（メタデータ） (2024-03-07T18:49:32Z)
• Testing quantum satisfiability [0.0]
  量子k-SATはランダムな時間で解けることを示す。 まず、量子 k-SAT の充足可能なインスタンスに対して、一定数の量子ビット上のほとんどの部分プロブレムは積状態によって満足できることを示す。 次に、積状態によって満足できない量子 k-SAT のインスタンスの場合、ほとんどのサブプロブレムは積状態によって満足できないことを示す。
  論文  参考訳（メタデータ） (2023-01-25T17:02:46Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  我々は、トポロジカルデータ解析のための改良された量子アルゴリズムを解析し、最適化する。 超二次量子スピードアップは乗法誤差近似をターゲットとする場合にのみ可能であることを示す。 数百億のトフォリを持つ量子回路は、古典的に難解なインスタンスを解くことができると我々は主張する。
  論文  参考訳（メタデータ） (2022-09-27T17:56:15Z)
• Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models [15.857373057387669]
  無限大極限におけるランダム最適化問題のアンサンブル上での任意の一定レベル(層数)における濃度特性を証明した。 我々の分析は、サドル点近似の和対パス積分によって理解することができる。 一定レベルにおけるQAOAの性能は、$qge 4$のときの純$q$-spinモデルの最適性から外れ、偶数であることを示す。
  論文  参考訳（メタデータ） (2022-04-21T17:40:39Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。 我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。 任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
  論文  参考訳（メタデータ） (2022-03-30T02:02:16Z)
• Tight Exponential Analysis for Smoothing the Max-Relative Entropy and for Quantum Privacy Amplification [56.61325554836984]
  最大相対エントロピーとその滑らかなバージョンは、量子情報理論の基本的な道具である。 我々は、精製された距離に基づいて最大相対エントロピーを滑らかにする量子状態の小さな変化の崩壊の正確な指数を導出する。
  論文  参考訳（メタデータ） (2021-11-01T16:35:41Z)

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

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