LB and QLB constant-factor equivalence for posets

Conjecture on LB and QLB equivalence · arXiv:1902.06473

arXiv Informal low confidence— first stated 2019-02-18

Authors: Jean Cardinal, Gwenaël Joret, Jérémie Roland

Status open medium confidence

The conjecture posits that the classical lower bound LB(P) = n(ln n - H(P)) and the quantum lower bound QLB(P) = n(H_n - QH(P)) for sorting under partial information are within a constant factor of each other for all posets P, where H(P) is the entropy and QH(P) is its averaged variant. The source paper (arXiv:1902.06473) itself proves the conjecture for a wide class of posets (including series-parallel posets), improving on Yao's 2004 result, but the full conjecture for arbitrary posets remains open. No follow-up paper resolving the full conjecture was found in searches covering the period 2019–2026.

Reviewer notes. The paper itself establishes QLB(P) >= c * LB(P) for series-parallel posets (and more generally for a wide class of posets), which is a partial result toward the full conjecture. The conjecture that LB(P) and QLB(P) are within a constant factor for ALL posets appears to remain open. The PDF source was not machine-readable for full text extraction; the conjecture statement in the input is noted as partially corrupted. No follow-up paper settling the full conjecture was found in four targeted web searches.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. The two lower bounds $\mathrm{LB}(P)$ and $\mathrm{QLB}(P)$ are within a constant factor of each other for all posets $P$.

Context

In the Conclusion, the authors present a table comparing the classical quantity $\mathrm{LB}(P) = n(\ln n - H(P))$ and the quantum quantity $\mathrm{QLB}(P) = n(H_n - QH(P))$, where $H(P) = \min_{z \in C(P)} h(z)$ is the entropy and $QH(P) = \mathbb{E}_{z \in C(P)}[h(z)]$ is its averaged variant. The authors state their findings support a conjecture relating these two bounds, but the remainder of the statement is corrupted in the PDF source.

Notes. PDF source — the statement is truncated after 'QLB(P)' and replaced with garbled content (a list of arXiv IDs). The statement above is inferred from context; the exact formulation cannot be verified.

Source paper

Information-theoretic lower bounds for quantum sorting
Jean Cardinal, Gwenaël Joret, Jérémie Roland · 2019-02-18
https://arxiv.org/abs/1902.06473 PDF source