A Slice-Rank Drift Bound for Random Quantum \(k\)-SAT

• URL: http://arxiv.org/abs/2607.23847v1
• Date: Sun, 26 Jul 2026 21:18:02 GMT
• Title: A Slice-Rank Drift Bound for Random Quantum \(k\)-SAT
• Abstract summary: We prove a new upper bound on the satisfiability threshold of random quantum (k)-SAT.<n>The improvement is also significant at small values of (k), giving a bound of order (2k/k)<n>The proof combines the geometric formulation of generic quantum satisfiability with a dimension-decay analysis of the full satisfying subspace.
• Score: 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.

Related papers

• A Lower Bound Framework for Quantum Functional Estimation [13.491187998442596]
  We develop a unified framework for proving lower bounds for estimating functionals of $d$-dimensional quantum states.<n>The framework combines a Haar-random moment encoding process with moment matching and best approximation.
  arXiv  Detail & Related papers  (2026-08-03T17:59:11Z)
• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  We develop a novel quantum mean estimator for heavy-tailed random variables.<n>We derive stronger lower bounds for tail index>4/3$, showing that a nontrivial dependence on a dimension is unavoidable.<n>For a convex objective function, we propose a quantum projected gradient descent method.
  arXiv  Detail & Related papers  (2026-07-28T09:29:37Z)
• Multiple Quantum Hypothesis Testing: One-Shot Pairwise Bounds and Sharp Asymptotics [13.098901971644656]
  We establish a dimension-free one-shot upper bound on the minimum probability of error in terms of the sum of pairwise errors.<n>We prove that the minimum error probability is characterized, up to universal constants, by a trace harmonic-mean quantity.
  arXiv  Detail & Related papers  (2026-06-04T14:49:12Z)
• Hysteretic squashed entanglement in many-body quantum systems [42.085941481155295]
  Entanglement in many-body quantum systems is distributed across spatial regions.<n>We propose hysteretic entanglement $T_sq$, a conditional entanglement that measures the genuine quantum correlations between two subregions.<n>We show that $T_sq$ can detect genuine quantum correlations across both adjacent and long-range subsystems.
  arXiv  Detail & Related papers  (2026-03-10T17:00:49Z)
• The Cumulants Expansion Approach: The Good, The Bad and The Ugly [0.0]
  Mean field approximation is widely known as the mean field approximation and used routinely throughout quantum physics.<n>We discuss two problems in quantum electrodynamics and quantum information, namely the collective radiative dissipation of a dipole-dipole interacting chain of atoms.<n>We find smooth, convergence behavior, where the approximation performs increasingly better with higher orders.<n>In the latter going beyond mean field turns out useless and, even for small system sizes, we are puzzled by numerically challenging and partly non-physical solutions.
  arXiv  Detail & Related papers  (2025-11-25T09:37:31Z)
• SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions [50.20087216230159]
  We study the complexity of Non-Gaussian Component Analysis (NGCA) in the Statistical Query model. We prove near-optimal SQ lower bounds for NGCA under the moment-matching condition only.
  arXiv  Detail & Related papers  (2024-03-07T18:49:32Z)
• Testing quantum satisfiability [0.0]
  We show that quantum k-SAT can be solved in randomised time.<n>We first show that for a satisfiable instance of quantum k-SAT, most subproblems on a constant number of qubits are satisfiable by a product state.<n>We then show that for an instance of quantum k-SAT which is far from satisfiable by a product state, most subproblems are unsatisfiable by a product state.
  arXiv  Detail & Related papers  (2023-01-25T17:02:46Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models [15.857373057387669]
  We prove concentration properties at any constant level (number of layers) on ensembles of random optimization problems in the infinite size limit. Our analysis can be understood via a saddle-point approximation of a sum-over-paths integral. We show that the performance of the QAOA at constant levels is bounded away from optimality for pure $q$-spin models when $qge 4$ and is even.
  arXiv  Detail & Related papers  (2022-04-21T17:40:39Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• Tight Exponential Analysis for Smoothing the Max-Relative Entropy and for Quantum Privacy Amplification [56.61325554836984]
  The max-relative entropy together with its smoothed version is a basic tool in quantum information theory. We derive the exact exponent for the decay of the small modification of the quantum state in smoothing the max-relative entropy based on purified distance.
  arXiv  Detail & Related papers  (2021-11-01T16:35:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.