Pith. sign in

REVIEW 26 references

Random quantum k-SAT becomes unsatisfiable by density about 2^k/k, not merely 2^k.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-30 10:37 UTC pith:ZLWA5QSD

load-bearing objection Solid factor-k improvement on the random QSAT UNSAT bound via a clean slice-rank drift argument; the load-bearing lemma checks out on a careful read.

arxiv 2607.23847 v1 pith:ZLWA5QSD submitted 2026-07-26 quant-ph math-phmath.COmath.MPmath.PR

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

Jean Bernoulli Ravelomanana This is my paper
classification quant-ph math-phmath.COmath.MPmath.PR
keywords random quantum k-SATfrustration-free Hamiltonianssatisfiability thresholdslice rankdimension drifttensor-product subspacesquantum Lovász local lemma
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Random quantum k-SAT asks when a random collection of local rank-one projectors on n qubits still leaves a common zero-energy state. Prior rigorous upper bounds only forced unsatisfiability at densities of order 2^k, while lower bounds already guaranteed satisfiability up to order 2^k/k^2, leaving a large gap. This paper closes most of that gap from above: it proves that once the density exceeds a explicit integral α⋆(k) that behaves like 2^k/k for large k, the satisfying subspace is empty with high probability. For three-local constraints the new number is about 1.947, cutting the previous explicit upper bound of 3.594 nearly in half. The argument tracks how the dimension of the full satisfying space decays under successive random constraints, rather than hunting special local obstructions or restricting to product states.

Core claim

In the random generic quantum k-SAT model, the unsatisfiability threshold satisfies α_unsat(k) ≤ α⋆(k), where α⋆(k) is the integral from 0 to 1 of ds over log₂(1/(1−2^{−ks})). Consequently α⋆(k) ∼ 2^k/k as k → ∞, and for k = 3 one obtains the concrete bound α_unsat(3) ≤ α⋆(3) ≈ 1.947.

What carries the argument

The multiplicative slice-rank inequality: for every nonzero subspace W of (ℂ²)^⊗m the product of its one-qubit generic contraction ranks is at least (dim W)^{m−1}. This forces a typical random k-set to remove a definite logarithmic fraction of dimension, which integrates into the drift bound defining α⋆(k).

Load-bearing premise

The whole bound rests on one deterministic claim: any high-dimensional subspace of many qubits must have large generic contraction rank on most single qubits, proved by an induction that splits the space into two slices and adds their ranks.

What would settle it

Either exhibit a family of subspaces that violate the multiplicative slice-rank inequality, or produce (analytically or by large-n numerics) random quantum 3-SAT instances that remain satisfiable at densities strictly above 1.947.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • If a sharp threshold exists, it lies between order 2^k/k² and order 2^k/k.
  • For quantum 3-SAT the critical density, if it exists, is at most 1.947 rather than 3.594.
  • Above the product-satisfiability threshold the same drift still kills the full (possibly entangled) satisfying space by density ∼2^k/k.
  • The dimension-drift method supplies a quantitative tool for rate estimates on random code-like subspaces cut out by sparse local checks.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Closing the remaining factor-of-k gap between 2^k/k² and 2^k/k will likely need a sharper local-rank inequality or a matching construction that keeps positive dimension past α⋆(k).
  • The same contraction-rank drift may give nontrivial upper bounds on the rate of random quantum LDPC code spaces under sparse parity checks.
  • If numerical work continues to suggest that product and full thresholds coincide at k=3, the new 1.947 ceiling becomes a concrete target for locating that common transition.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Circularity Check

0 steps flagged

No significant circularity: α⋆(k) is an explicit integral of a proved drift lower bound, not a fit or self-referential definition.

full rationale

The derivation is self-contained pure mathematics. Lemma 2 (multiplicative slice-rank inequality) is proved by induction with an elementary scalar check; Corollaries 3–4 convert it into a local-rank shadow bound; Section 5.1 obtains the logarithmic drift ET XT(W) ≥ log2(1/(1−2−ks)) by Jensen on the convex decreasing map g; α⋆(k) is then defined as the continuum integral of the reciprocal of that drift and is integrated by a truncated stopped-martingale / Azuma argument. Prior upper bounds (Bravyi–Moore–Russell) and the quantum LLL lower bound appear only in comparison statements (Corollary 2) and are not inputs to the proof. The single self-citation to the author’s PRODSAT work is background and non-load-bearing. Nothing is fitted to data, and no uniqueness theorem or ansatz is imported to force the result. Residual risk is ordinary line-by-line verification risk, not circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 1 invented entities

The central claim is a pure existence/probability theorem in the standard random generic quantum k-SAT model. It rests on ordinary multilinear algebra, generic rank over Zariski-open sets, and concentration (Azuma–Hoeffding), plus the community’s definition of the random generic ensemble. No parameters are fitted to data; the truncation level C is sent to infinity. No new physical entities are postulated.

axioms (5)
  • domain assumption Random generic quantum k-SAT ensemble: independent uniform k-supports (or simple hypergraph) with covectors absolutely continuous w.r.t. Lebesgue; satisfiability iff common kernel nonzero (Laumann et al. model).
    Fixed in Sec. 2.1; all high-probability statements are relative to this ensemble. Standard in the cited QSAT literature.
  • standard math Generic rank equals maximal rank almost surely: rank C_T(φ_T)=r_T(W) outside a proper algebraic set of covectors.
    Lemma 1; elementary Zariski/measure argument used to equate dimension drop with contraction rank.
  • standard math Azuma–Hoeffding concentration for bounded martingale-difference sequences.
    Invoked in Prop. 1 (Sec. 5.2) to show each drift stage succeeds w.h.p.
  • standard math Multiplicative Minkowski / concavity of the geometric mean: (∏(x_i+y_i))^{1/m} ≥ (∏x_i)^{1/m}+(∏y_i)^{1/m} for x_i,y_i≥0.
    Used inside the induction step of Lemma 2 (Sec. 4.1) to pass from r_i(W)≥r_i(A)+r_i(B) to a product lower bound.
  • domain assumption Constraints are rank-one local projectors (standard rank-one QSAT); higher-rank projectors are excluded.
    Stated in Sec. 2.1; the contraction-rank calculus is built for rank-one updates.
invented entities (1)
  • Multiplicative slice-rank inequality for subspaces (and the associated α⋆(k) drift integral) no independent evidence
    purpose: Deterministic engine that forces typical k-local contraction ranks to be large whenever global dimension is large, yielding the continuum UNSAT density α⋆(k).
    Not a physical particle/force, but a new mathematical inequality postulated-and-proved in the paper; independent_evidence is the internal proof plus the Loomis–Whitney analogy, not an external experiment.

pith-pipeline@v1.2.0-grok45-kimik3 · 19132 in / 3588 out tokens · 94798 ms · 2026-07-30T10:37:29.454096+00:00 · methodology

0 comments
read the original 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.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

26 extracted references · 7 linked inside Pith

  1. [1]

    Bravyi,Efficient algorithm for a quantum analogue of 2-SAT, arXiv:quant-ph/0602108, 2006

    S. Bravyi,Efficient algorithm for a quantum analogue of 2-SAT, arXiv:quant-ph/0602108, 2006

    Pith/arXiv arXiv 2006

  2. [2]

    C. R. Laumann, R. Moessner, A. Scardicchio, and S. L. Sondhi,Phase transitions and random quantum satisfiability, Quantum Information & Computation10(2010), no. 1–2, 0001–0015; arXiv:0903.1904

    Pith/arXiv arXiv 2010

  3. [3]

    C. R. Laumann, A. M. L¨ auchli, R. Moessner, A. Scardicchio, and S. L. Sondhi,Product, generic, and random generic quantum satisfiability, Physical Review A81(2010), 062345; arXiv:0910.2058

    Pith/arXiv arXiv 2010

  4. [4]

    Bravyi, C

    S. Bravyi, C. Moore, and A. Russell,Bounds on the quantum satisfiability threshold, in Proceedings of Innovations in Computer Science (ICS), 2010, pp. 482–489; arXiv:0907.1297. 19

    Pith/arXiv arXiv 2010

  5. [5]

    Ambainis, J

    A. Ambainis, J. Kempe, and O. Sattath,A quantum Lov´ asz local lemma, Journal of the ACM59(2012), no. 5, Article 24

    2012

  6. [6]

    Sattath, S

    O. Sattath, S. C. Morampudi, C. R. Laumann, and R. Moessner,When a local Hamiltonian must be frustration-free, Proceedings of the National Academy of Sciences113(2016), no. 23, 6433–6437; arXiv:1509.07766

    Pith/arXiv arXiv 2016

  7. [7]

    K. He, Q. Li, X. Sun, and J. Zhang,Quantum Lov´ asz local lemma: Shearer’s bound is tight, inProceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC), 2019, pp. 461–472; arXiv:1804.07055

    Pith/arXiv arXiv 2019

  8. [8]

    S. C. Morampudi, B. Hsu, S. L. Sondhi, R. Moessner, and C. R. Laumann,Clustering in Hilbert space of a quantum optimization problem, Physical Review A96(2017), 042303; arXiv:1704.00238

    Pith/arXiv arXiv 2017

  9. [9]

    L. H. Loomis and H. Whitney,An inequality related to the isoperimetric inequality, Bulletin of the American Mathematical Society55(1949), no. 10, 961–962

    1949

  10. [10]

    M´ ezard and A

    M. M´ ezard and A. Montanari,Information, Physics, and Computation, Oxford University Press, Oxford, 2009

    2009

  11. [11]

    Friedgut, Sharp thresholds of graph properties, and the k-SAT problem,Journal of the American Mathematical Society12(1999), no

    E. Friedgut, Sharp thresholds of graph properties, and the k-SAT problem,Journal of the American Mathematical Society12(1999), no. 4, 1017–1054

    1999

  12. [12]

    Achlioptas and Y

    D. Achlioptas and Y. Peres, The threshold for random k-SAT is 2k log 2 −O (k),Journal of the American Mathematical Society17(2004), no. 4, 947–973

    2004

  13. [13]

    J. Ding, A. Sly and N. Sun, Proof of the satisfiability conjecture for large k,Annals of Mathematics196(2022), no. 1, 1–388

    2022

  14. [14]

    Achlioptas and C

    D. Achlioptas and C. Moore, Random k-SAT: two moments suffice to cross a sharp threshold, SIAM Journal on Computing36(2006), no. 3, 740–762

    2006

  15. [15]

    M´ ezard, G

    M. M´ ezard, G. Parisi and R. Zecchina, Analytic and algorithmic solution of random satisfiability problems,Science297(2002), no. 5582, 812–815

    2002

  16. [16]

    Mertens, M

    S. Mertens, M. M´ ezard and R. Zecchina, Threshold values of random K-SAT from the cavity method,Random Structures & Algorithms28(2006), no. 3, 340–373

    2006

  17. [17]

    Krzakala, A

    F. Krzakala, A. Montanari, F. Ricci-Tersenghi, G. Semerjian and L. Zdeborov´ a, Gibbs states and the set of solutions of random constraint satisfaction problems,Proceedings of the National Academy of Sciences104(2007), no. 25, 10318–10323

    2007

  18. [18]

    Achlioptas and A

    D. Achlioptas and A. Coja-Oghlan, Algorithmic barriers from phase transitions, inPro- ceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, pp. 793–802

    2008

  19. [19]

    Gosset and D

    D. Gosset and D. Nagaj, Quantum 3-SAT is QMA1-complete,SIAM Journal on Computing 45(2016), no. 3, 1080–1128

    2016

  20. [20]

    J. Lee, N. Macris, J. B. Ravelomanana and P. Vantalon, The PRODSAT phase of random quantum satisfiability, arXiv:2404.18447, 2024

    arXiv 2024

  21. [22]

    Monasson, R

    R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman and L. Troyansky, Determining computational complexity from characte 20

  22. [23]

    Kirkpatrick and B

    S. Kirkpatrick and B. Selman, Critical behavior in the satisfiability of random Boolean expressions,Science264(1994), no. 5163, 1297–1301

    1994

  23. [24]

    Monasson, R

    R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman and L. Troyansky, Determining computational complexity from characteristic phase transitions,Nature400(1999), 133– 137

    1999

  24. [25]

    Knill and R

    E. Knill and R. Laflamme, Theory of quantum error-correcting codes,Physical Review A 55(1997), 900–911

    1997

  25. [26]

    Tillich and G

    J.-P. Tillich and G. Zemor, Quantum LDPC codes with positive rate and minimum distance proportional to √n,IEEE Transactions on Information Theory60(2014), no. 2, 1193–1202

    2014

  26. [27]

    Panteleev and G

    P. Panteleev and G. Kalachev, Asymptotically good quantum and locally testable classical LDPC codes, inProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, pp. 375–388. Jean Bernoulli Ravelomanana Email address:rjeanbernoulli@gmail.com 21

    2022