Xiande Zhang

Shixuan Zeng, Xiande Zhang

Absolutely maximally entangled (AME) states and, more generally, $k$-uniform states in $(\C^q)^{\otimes n}$ are central objects in multipartite entanglement theory, with applications to quantum secret sharing, quantum masking, and quantum error correction. In the extremal case $k=\lfloor n/2\rfloor$, Scott (2004) proved a sharp nonexistence bound showing that AME states cannot exist once the number of parties $n$ exceeds a threshold of order $2q^{2}$ (with a parity dependence on $n$), where $q$ is the local dimension. Recently, Ning et al.\ studied \emph{defective} AME states (i.e., $k=\lfloor n/2\rfloor-l$ with $l>0$), gave explicit Scott-type bounds for defects $l=1,2$ and conjectured a general $(2l+2)q^{2}+o(q^{2})$ behavior. In this paper, we solve this conjecture and establish a fully explicit Scott-type upper bound for AME states with arbitrary defect $l\ge 0$, yielding Scott's bound for $l=0$ and Ning et al.'s bounds for $l=1,2$ as special cases. Equivalently, this gives nonexistence bounds for one-dimensional pure quantum error-correcting codes near the quantum Singleton regime. The proof uses a truncated MacWilliams linear-programming system and an explicit infeasibility certificate. As a direct application, we derive explicit asymptotic upper bounds on $k/n$ for fixed local dimension $q$, improving the implicit upper bounds given by Ning et al.

Zicheng Han, Yupeng Lin, Jie Ma et al.

We develop a hypergraph container method for the Boolean Satisfiability Problem (SAT) via the newly developed container results [Campos and Samotij (2024)]. This provides an explicit connection between the extent of spread of clauses and the efficiency of container-based algorithms. Informally, the more evenly the clauses are distributed, the stronger the shrinking effect of the containers, which leads to faster algorithms for SAT. To quantify the extent of spread, we use a weighted point of view, in which a clause of size $s$ receives weight $p^s$ for some $0<p\le 1$.In this way, we introduce the notion of $(λ,p)_k$-structure for SAT formulas, where $λ$ is the spread parameter and $k$ is the maximum size of clauses. By the almost-independence property of containers, we prove that for formulas with $(λ,p)_k$-structures, one can distinguish between ``unsatisfiable formulas'' and ``formulas satisfying at least a $(1-δ)$-fraction of clauses'' in sub-exponential time. This shows that sufficiently spread formulas are not worst-case instances for Gap-ETH. Moreover, we show that the speedup is directly controlled by the spread parameter $λ$, yielding faster exact algorithms for SAT formulas containing a $(λ,p)_k$-structure. This result extends previous work [Zamir (STOC 2023)] to the non-uniform case.