Papers

Universal coding of integers (UCI) provides binary codewords for positive integers such that, for every nonincreasing source distribution $P$, the average codeword length stays within $K$ times $\max\{1,H(P)\}$. The smallest constant $K$ is called the minimum expansion factor of UCI $\mathcal{C}$, denoted $C_{\mathcal{C}}^{*}$. The optimal minimum expansion factor $C^*=\inf\{C_{\mathcal{C}}^{*}\}$ is the minimum expansion factor corresponding to the optimal UCI. The optimal minimum expansion factor is currently known to lie in the range $2\le C^*\le 2.0386$. In this paper, we construct a family of one-point plus uniform-tail distributions and prove that, for every universal code, the worst-case ratio is attained by a distribution in this family, so that the family is least favorable for the UCI problem. We further establish an inequality, called the UCI inequality, which plays the same role for UCI as the Kraft inequality does for prefix codes: for any real number $B$, it decides whether $B$ lies below or above $C^*$. Through the UCI inequality, we obtain an equivalent definition of $C^*$. By numerical computation, we determine $C^*=2.000124757036101\cdots$, the first fifteen decimal digits being certified. Once $C^*$ is known, we can theoretically construct the optimal UCI.

Iterative fine-tuning on synthetic data causes model collapse: output diversity narrows as rare patterns are progressively lost, a signature most visible as phrase-level repetition. Existing mitigations either require model log-probabilities, an external oracle, or continued access to real human data. Here we develop a new approach grounded in mathematical information theory: the non-parametric Kontoyiannis entropy rate estimator $h_k$, computed entirely from raw text via match-length statistics, with no model of any kind. We show that this is in fact a superior training-data filter on text-diversity metrics in a fully-synthetic, single-lineage fine-tuning setting. In a six-generation QLoRA collapse experiment on Llama-3.1-8B, logprob-based filtering (the most established model-access-requiring baseline) provides no significant text-diversity benefit on any metric ($p > 0.23$), whereas $h_k$-filtering yields $+42\%$ unique trigrams, $+30\%$ vocabulary, and $-19\%$ repetition (all $p < 0.001$). We validate $h_k$ as a cross-domain entropy proxy ($\beta = 0.924$, $R^2 = 0.746$) and collapse detector ($\rho = +0.454$, $p < 0.0001$) across 4~domains, 2~temperatures, 2~generator–scorer model pairs, and 1{,}520 generated documents. Our results demonstrate that information theoretic approaches to collapse mitigation are efficient, and suggest new approaches for maintaining multi-agent diversity.

Wireless digital twins (WDTs) are promising enablers for developing and evaluating AI-native radio access networks, yet constructing a high-fidelity WDT typically requires substantial manual effort to integrate heterogeneous information and infer unknown propagation-related parameters. This paper proposes Agentic WDT (AWDT), an end-to-end agentic framework for autonomous WDT construction and calibration using readily available environmental information and measurements readily obtainable from commercial smartphones. AWDT comprises three agents: EnvAgent constructs the propagation environment, OpAgent infers BS and sector configurations, and MatAgent calibrates radio material properties. The agents iteratively refine the WDT using discrepancies between LTE/NR reference signal received power (RSRP) measurements and ray-tracing predictions. Real-world experiments show that AWDT reduces the RSRP prediction MAE from 11.46 to 5.25 dB, demonstrating a substantial improvement in ray-tracing fidelity. Evaluation with an independent measurement system further demonstrates cross-device transferability with lightweight device-specific bias adaptation, highlighting the potential of agentic AI for scalable WDT construction and calibration with limited prior knowledge.

In this paper, a unmanned aerial vehicle (UAV) corridor-assisted network is proposed to study the joint sensing and communication (JCAS) coverage probability (CP) of a terrestrial (BS) equipped with a realistic three-dimensional (3D) 3GPP antenna pattern. By employing the 3D binomial point process (BPP) to model the spatial locations of the UAV-UEs, a fixed number of UAV-UEs are deployed in an aerial corridor modeled as a finite cylinder. The BS exploits radar sensing capabilities to track a known UAV-UE under a 3D beam misalignment error, which follows a multivariate normal distribution. Subsequently, under clutter and uplink communication interference, exact- form analytical expressions for JCAS CP are derived and used to analyze the performance at the terrestrial BS. The results highlight corridor-length saturation at high UAV heights and the beamwidth trade-off between interference suppression and misalignment sensitivity.

In unmanned aerial vehicle (UAVs) networks, joint communication and sensing (JCAS) is emerging as a key enabler to support extended and continuous communication and sensing capabilities for sixth-generation (6G) services among UAVs operating in swarms. Within this framework, aerial corridors provide a structured environment for supporting coordinated and reliable operations. In this paper, a comprehensive frame- work is presented to investigate the JCAS coverage probability (CP) of a UAV-base station (BS) in an aerial corridor populated by UAV-user equipments (UEs). The corridor is modeled as a finite cylinder, within which a fixed number of UAV-UEs are spatially distributed according to a three-dimensional (3D) binomial point process (BPP). The UAV-BS is assumed to be equipped with a realistic 3D third generation partnership project (3GPP) antenna pattern and exploits radar sensing capabilities to track a known UAV-UE. Subsequently, the tracked UAV-UE is assumed to perform uplink communication with the UAV-BS. Accordingly, the JCAS CP at the UAV-BS is analyzed under the presence of clutter and uplink communication interference, and exact-form analytical expressions are derived. To the best of our knowledge, this is the first work to develop a stochastic geometry framework for the rigorous analysis of JCAS performance in aerial corridors, with UAV-UE locations modeled as a 3D BPP. Among several insights, results show that increasing the directivity of the UAV-BS antenna beams leads to notable JCAS performance gains, particularly for shorter UAV corridors.

Existing trajectory designs for covert communications with uncrewed aerial vehicles (UAVs) typically rely on point-mass kinematics, which overlook the inherent coupling between flight maneuvers and antenna orientation. Motivated by recent studies linking UAV acceleration to attitude, we investigate dynamics-consistent trajectory and attitude co-design for rotary-wing UAV covert communications. We consider a UAV equipped with a directional antenna transmitting confidential information to a legitimate ground receiver in the presence of a warden. The acceleration-induced reduced attitude of the UAV is explicitly modeled together with its impact on the attitude-dependent directional channel gain. To ensure covertness, we derive a per-slot constraint based on the Kullback–Leibler (KL) divergence at the warden. We then formulate a joint trajectory and attitude optimization problem to maximize the average achievable covert rate subject to covertness, motion, thrust-magnitude, attitude-smoothness, and acceleration-domain safety constraints induced by roll and pitch limits. The resulting problem is non-convex because the channel gains depend jointly on position, acceleration, and attitude. To solve it, we develop a minorization–maximization (MM)-based algorithm that constructs a concave lower bound on the transmission rate and a convex upper bound on the covert constraint at each iteration. We further extend the framework to imperfect attitude control and develop a robust design against attitude tracking errors caused by actuator limitations, sensor noise, and control delays. Numerical results demonstrate the effectiveness of the proposed dynamics-consistent design and highlight the benefit of jointly optimizing UAV trajectory and attitude for covert communications.

Task-oriented communication conveys information that is necessary for downstream tasks. For binary decision tasks, this paradigm is information-theoretically formalized by Boolean function computation (BFC) via channels, where the receiver aims to determine the value of a function unknown to the transmitter. In this paper, we devise a practical code construction for the BFC problem based on a Reed-Solomon code. For noiseless binary channels, we derive finite-blocklength worst-case error bounds. By defining a rate function that captures how supported message length scales with channel uses, we characterize the rate-reliability tradeoff for different Boolean function families. With respect to this rate function, the proposed construction achieves an asymptotic computation rate of $1/2$. We further extend this construction to noisy channels by packing multiple BFC tasks into a single block and concatenating them with a conventional channel code. The corresponding finite-blocklength guarantees are expressed in terms of effective channel uses per function evaluation. With a channel code rate $R_c$, this construction achieves an asymptotic computation rate of $R_c/2$, yielding $C/2$ when capacity-achieving channel codes are employed. Numerical results illustrate the derived bounds and demonstrate substantial performance gains over conventional transmission. As examples, the proposed scheme achieves SNR coding gains of approximately $3.4$ and $6.4$ dB at an average task error probability of $10^{-5}$ for the exact-weight and rank-test tasks, respectively.

Quantum low-density parity-check (QLDPC) codes are promising candidates for low-overhead fault-tolerant quantum computation, but their practical use requires fast, low-complexity, and reliable decoders. Belief propagation (BP) is attractive because of its local message-passing structure, yet standard flooding BP often suffers from convergence failures on QLDPC codes due to short cycles, degeneracy, and symmetric decoding trajectories. Learned sequential BP improves convergence by using a reinforcement-learning policy to choose variable-node update orders, but a single learned trajectory can still be sensitive to unfavorable local Pauli decisions. We propose a learned parallel bit-flipping sequential BP decoder with a new quaternary score combining syndrome gain, a quantized Pauli log-likelihood penalty, and Q-table lookahead at hypothetical post-flip states. Our decoder first runs learned sequential BP for a fixed number of iterations. If the syndrome is not satisfied, it constructs quaternary bit-flipping candidates, each corresponding to changing the current Pauli decision of one qubit. The selected candidates initialize independent learned sequential BP continuations from the same decoder state. Since these continuations are independent, they can be executed in parallel, so testing several candidates mainly increases parallel hardware resources rather than sequential decoding latency. Simulations on representative QLDPC codes over the depolarizing channel show that the proposed decoder improves the reliability of learned sequential BP while having a parallel low-latency structure.

We study online convex optimization with one unbiased stochastic subgradient per round and an unknown finite conditional $p$th noise moment, $1<p\le2$. For every fixed interval $I$ of length $n$ and comparator path with $\Lambda_I=1+P_I/D$, one learner achieves \[ E[Regret_I(u)]\le\min(GDn, C[GD\sqrt{n(\Lambda_I+\log^2(2T))} +\sigma Dn^{1/p}(\Lambda_I+\log^2(2T))^{(p-1)/p}]). \] The learner uses none of $G,\sigma,p,I,P_I$, and the constant is universal. Interval adaptation adds to comparator complexity, preserving the distinct mean-gradient and noise exponents. The analysis controls calibration in expectation and limits the cost of observation-scale changes. Its general theorem compares to distributions over predictably available experts with relative-entropy dependence on a nonuniform prior. A common prior favors long windows and long restart lengths. With the statistics supplied, the interval cost becomes $1+\log(T/n)$, including the optimal full-horizon static rate. A change-of-measure lower bound identifies the noise power of this logarithm for learners retaining a full-horizon optimal guarantee, under explicit conditions. Static comparisons and deterministic partitions follow from the same decisions.

Molecular neural interfaces that deliver and sense the same neurotransmitter must estimate endogenous release in the presence of their own chemical input. We study two exchanging regions with shared saturable uptake and concentration change measurements. Known delivery and exchange permit identification of apparent uptake at the driven region, but an unknown resting concentration difference leaves the source region's incremental uptake uncertain. We characterize all admissible source histories consistent with both ideal records and show how delivery and baseline information affect release classification. A dopamine-inspired example produces identical ideal concentration-change records for mean release-rate changes of -8.99 and +1.31 nanomolar per second. Stronger delivery changes whether all compatible sources imply suppression, with the true source held fixed. Under a Gaussian observation model, we bound discrimination based on chemical fluctuations. A baseline reference with an assumed standard deviation of 3.3 nanomolar reduces root-mean-square error from 10.41 to 1.21 nanomolar per second compared with an incorrect fixed baseline under exact gain calibration. Classification errors remain substantial with weak excitation, gain errors or responses near the category boundaries.

Secure aggregation lets a server recover an aggregate of client updates without observing any individual update, but conventional protocols fix the aggregate precision when clients upload. We introduce and formulate a new progressive-resolution secure-aggregation functionality in which clients upload once and successively finer resolutions of the same aggregate can later be authorized without renewed client participation. To realize this functionality, we propose progressive-resolution secure aggregation (PSA): each clipped, dithered update is represented by compatible nested-lattice digits; separately releasable layers are protected by secure aggregation and an additional aggregate pad that remains unavailable to the server until a non-colluding release controller authorizes that layer.

Large reasoning models (LRMs) have achieved substantial improvements in solving complex mathematical problems, but often produce lengthy, repetitive, or erroneous reasoning trajectories. In this work, we introduce a new interpretability framework, SLIDER, to evaluate the quality of the reasoning process. SLIDER leverages an emerging body of work from information theory called Partial Information Decomposition to disentangle the information about the final answer between two consecutive reasoning steps into non-negative components: unique information (in preceding steps or current step), redundant information, and synergistic information. Building on this decomposition, we propose the *Step-wise Repetitive Reasoning Index (Step-RRI)*, a theoretically grounded measure that assesses whether the answer-relevant information in the current step $S_i$ is predominantly redundant with the past steps $S_{<i}$, relative to its unique and synergistic contributions. To evaluate the effectiveness of Step-RRI in detecting repetitiveness, we apply SLIDER to the redundancy class of the PRMBench dataset where Step-RRI improves step-level redundancy identification accuracy by over $10$ points compared to embedding-similarity and information-gain baselines. Next, we define *Trajectory-RRI*, an aggregate measure of repetitiveness for an individual reasoning trajectory. To demonstrate its practical relevance, we show that average Trajectory-RRI strongly correlates with actual reasoning length across QwQ-32B, DeepSeek-R1-Distill-Qwen-32B, and GPT-4.1, motivating its use as a signal for improving reasoning efficiency. Finally, we introduce *Trajectory-RRI-guided data selection for fine-tuning*, demonstrating that selecting training data based on Trajectory-RRI can improve a fine-tuned model's reasoning efficiency while largely preserving its task performance.

Sipser and Spielman constructed LDPC codes from either bipartite spectral expanders or one-sided lossless expanders. In higher dimensions, spectral expansion similarly played a central role in the constructions of asymptotically good classical LTCs and qLDPC codes by Dinur, Evra, Livne, Lubotzky, and Mozes and by Panteleev and Kalachev. Alternatively, Lin and Hsieh constructed classical LTCs and qLDPC codes from two-dimensional lossless cubical complexes. In this work we develop the higher-dimensional lossless approach. We do not construct the required high-dimensional lossless cubical complexes; rather, we investigate what their existence would imply. We associate with a high-dimensional cubical complex a level chain complex, whose chain groups are supported on the level sets of the Boolean cube rather than on its cells. Our main technical contribution is a clean local-to-global theorem for this structure: suitable one-dimensional lossless expansion in the directional graphs implies small-set coboundary expansion of the global level complex. As a consequence, sufficiently imbalanced, two-sided lossless four-dimensional cubical complexes give rise to asymptotically good quantum locally testable codes. We expect the local-to-global principle developed here to have further applications.

Next-generation large language models (LLMs) are expanding from the cloud to ubiquitous edge devices. However, edge devices typically either lack the memory to store increasingly large LLM weights or, even with enough memory, spend unaffordable energy on loading the weights. This raises our question: can an edge device run an LLM without storing or loading its weights, but receive them over the air and consume them on the fly? Inspired by wireless broadcasting, we present AIR-LLM, an LLM inference architecture for edge devices, which is composed of: (i) a central radio (e.g., 5G base stations) that broadcasts the LLM weights into the air, and (ii) the edge user that receives the weights and completes the general matrix-vector multiplication (GEMV) of LLM inference directly in the radio frequency (RF) domain using RF mixers. To further shorten the airtime, AIR-LLM exploits MIMO spatial multiplexing and proposes an energy-efficient precoder-postcoder pair on the edge to calibrate its own wireless channel. Since the central radio stays user-unaware, AIR-LLM is user-scalable so that one broadcast serves unlimited users within its coverage. We implement AIR-LLM on the NVIDIA Sionna ray-traced channels of two real-world urban scenes and the profiling of a real RF mixer. With a WikiText-2 perplexity degradation of 4.0% on LLaMA-3.1-8B, AIR-LLM saves the energy by 157.7x/40.4x against the FP16 and weight-only quantization baselines; with 20 users, its airtime is 104.1x/26.0x shorter, respectively.

Parity superselection forbids direct measurement of odd Majorana observables. We learn time-independent, parity-covariant, $k$-mode-local Lindbladians on $m$ modes using even preparations and measurements with uninterrupted short-time evolution. Internal markers turn odd probes into even observables, and pair measurements among three separated markers calibrate their dynamical contributions. Signed Fierz inversion recovers canonical coefficients, while semidefinite fitting yields a valid generator. For finite-range models on known bounded-degree graphs with suitable marker access and a supplied weighted-strength bound $\bar\alpha$, entrywise error $\varepsilon$ is achieved using $\widetilde{\mathcal{O}}(\bar\alpha^2\varepsilon^{-2}\log(m/\delta))$ samples, without external modes or known nonzero coefficient locations. Recovery to diamond-norm error $\varepsilon$ costs an additional factor $m^2$, matching lower bounds for short-time experiments on fresh systems up to logarithmic and fixed geometric factors. Without a supplied graph, one idle ancillary mode per system mode and potentially nonlocal pair operations give total absolute coefficient error at most $\varepsilon$ per mode using $\widetilde{\mathcal{O}}_k(\bar\alpha^2\mathsf d^2m^{\lfloor k/2\rfloor}\varepsilon^{-2}\log(m/\delta))$ samples, under a supplied approximate coefficient-degree bound $\mathsf d$ and controlled weak-coefficient tails. All guarantees hold with probability at least $1-\delta$. For geometric models, fixed-support even observables can be predicted with logarithmic system-size sample complexity at fixed time and accuracy. We also give finite-volume and exponential-tail extensions.

As an alternative to the standard geometric analyses, we give an exact, information-theoretic analysis of stochastic gradient descent (SGD) and its variants. We show that a preconditioned SGD step is the posterior-mean update of a Gaussian Bayes model, and that its one-step regret splits into an intrinsic-time cost and a change in comparator information. The split extends to an identity for the objective itself. Convex convergence, strict-saddle-point escape, the link between flatness and generalization, the standard learning-rate schedules, adaptive optimizers, and the noisy, momentum, heavy-tailed, and gradient-free variants of SGD each correspond to a term or a special case of this identity. We measure its terms on synthetic and real training runs. On real networks it attributes the slack of classical convergence bounds to the terms their derivations drop and separates optimizers that reach the same training loss. That separation follows the number and consistency of their steps. Its relation to which of them generalizes better differs between networks. For gradient-free SGD the identity determines how a curvature preconditioner should enter the update. The sharpness-based generalization certificate it yields, with a data-independent isotropic prior, is vacuous at network scale unless the curvature spectrum is nearly flat across all parameters.

We determine the optimal success probability for transmitting a fixed number of classical messages through a finite number of uses of the quantum erasure channel, assisted by noiseless classical feedback and without initial shared entanglement. For an input dimension $d$, an erasure probability $p$, a blocklength $n$, and $M$ equiprobable messages, the optimal success probability is equal to $E[\min\{1,d^K/M\}]$, where $K$ is binomial with parameters $n$ and $1-p$. The converse allows arbitrary adaptive quantum encoders, quantum memories, and receiver instruments. Its main ingredient is an elementary dimension bound for noiseless quantum communication with classical feedback, proved by fixing the classical controls without conditioning the sender's state on the observed transcript. A classical protocol that transmits the base-$d$ digits of an integer representing the message, repeating each digit until the receiver acknowledges its reception or the prescribed blocklength is reached, attains the bound for every integer $M$. We also establish a relative-majorization property of erasure-channel outputs and exactly evaluate a hypothesis-testing converse, recovering the same numerical bound without feedback. That converse need not be achievable without feedback: four uses of the qubit erasure channel and four messages give a strict gap. A product-state code employing tetrahedral qubit states nevertheless outperforms every classical binary erasure code with these parameters. We give an explicit message-size formula and show that the bounded-remainder normal approximation and the average-success strong-converse exponent are unchanged without feedback. We also determine the feedback-assisted error exponent below capacity, prove that it agrees with the no-feedback exponent above a critical rate, and give no-feedback bounds at lower rates.

While constellation shaping improves spectral efficiency, its application to quadrature phase-shift keying (QPSK) remains limited. We address this limitation by incorporating a short shaping code into low-density parity-check (LDPC)-coded QPSK systems. Specifically, a subset of LDPC codeword bits is used as shaping bits and mapped by the shaping code to a sparse codeword that enables probabilistic shaping by controlling non-equiprobable selection between lower- and higherenergy QPSK constellations. Because zeros dominate the sparse codeword, lower-energy constellation points are transmitted more frequently, yielding a Gaussian-like symbol distribution. By exploiting the channel-code protection of the shaping bits, we develop receiver algorithms that refine shaping-bit log-likelihood ratios (LLRs) using LDPC decoder feedback. Joint optimization of the shaping codebook, bit-to-symbol mapping and constellations enables the proposed shaping scheme to achieve gains of up to 0.6 and 0.53 dB over 5G New Radio (NR) LDPC-coded QPSK and QAM-16, respectively.

Model quantization reduces the numerical precision of neural network weights and activations to lower storage and computational costs. Model inversion attacks recover or reconstruct sensitive training data or inference inputs from model outputs or intermediate features, so quantization may also alter their effectiveness. However, two questions remain unresolved: How does model quantization affect model inversion? How do data characteristics influence this relationship? To address the first, we bound quantization-induced changes in mutual information between inputs and a categorical variable defined by prediction probabilities, distinguishing informational effects from attack optimization obstacles. To address the second, we identify data-dependent changes in feature distributions and inversion outcomes, with pronounced quantization sensitivity differences at 4 bits. These insights guide a privacy-aware post-training quantization method that improves inversion resistance while recovering utility. It uses a Fisher-type task-sensitivity proxy for budget-aware bit allocation, calibrates activation ranges, and jointly optimizes weight and activation scales and weight-rounding decisions with task-recovery and geometry-retention objectives and scale and rounding regularization. Experiments cover multiple metrics, neural network architectures, and face, palmprint, and iris recognition tasks. On ResNet-50, Palm at 4 bits reduces RL-MIA's strict success from 54% to 26%, while accuracy decreases from 99.01% to 96.55% relative to FP32. Our method also supports output-level defenses: adding Stealthy Shield Defense (SSD, epsilon = 0.1) to Iris at 4.5 bits reduces BREP-MI's strict success from 63.33% to 37.33%, while accuracy decreases from 92.8% to 87.6% relative to quantization alone.

Low-depth syndrome extraction for Calderbank-Shor-Steane (CSS) quantum low-density parity-check codes can be formulated as a proper ordered edge-coloring problem subject to quantum parity constraints. A proper edge-coloring of the CSS Tanner graph ensures that each data or ancilla qubit participates in at most one two-qubit gate per layer, but does not guarantee a valid interleaving of the X- and Z-check measurements as for every overlapping X/Z check pair, the number of shared data qubits on which the X interaction precedes the Z interaction must be even. The minimum number of colors in a proper ordered edge-coloring satisfying the quantum parity constraints equals the minimum two-qubit depth when each stabilizer check is measured with a single ancilla. We introduce local automorphism-aware syndrome compilation (LocalASC), which reduces the constraint system to edge-orbit variables under a subgroup of the Tanner graph automorphisms and lifts each feasible orbit assignment to the full graph. Although the $6$-layer degree lower bound is unattainable for the published weight-$6$ IBM bivariate bicycle codes, we show that this is not universal among two-block CSS codes. Among code instances for which the maximum check weight equals the maximum Tanner graph degree, LocalASC finds depth-optimal syndrome-extraction schedules for several two-block CSS codes with odd component weights, including instances with unequal odd weights. We also obtain lower-bound-saturating syndrome-extraction schedules for several quantum Tanner codes satisfying the same degree condition. To obtain the subgroups used by LocalASC without computing the full automorphism group of the Tanner graph, we construct translation subgroups for two-block group-algebra CSS codes over abelian groups. For quantum Tanner codes, we give conditions under which square-complex symmetries extend to Tanner graph automorphisms.

In classical coding theory, the quest for explicit codes achieving list decoding capacity has been an important driving force. While random codes are easily shown to achieve capacity, an explicit construction was only discovered decades later in the seminal work [Guruswami and Rudra, STOC 2006]. In quantum coding theory, it is highly desirable that a code family be LDPC. While good quantum codes were known for decades, obtaining the additional LDPC property was elusive. In fact, only very recently that good quantum LDPC codes were discovered in a breakthrough work [Panteleev and Kalachev, STOC 2022]. In this context, a natural question is to ask for an explicit family of quantum codes achieving list decoding capacity while also possessing the important LDPC property. In this work, we provide (to the best of our knowledge) the first explicit constructions of quantum LDPC codes achieving list decoding capacity, namely, with a list decoding radius approaching the quantum Singleton bound with constant list sizes. Furthermore, we provide near-linear time (in the block-length) list decoding algorithms approaching capacity. Our explicit code construction are based on expander graphs via the quantum analogue of Alon-Edmonds-Luby (AEL) amplification [Bergamaschi, Golowich and Gunn, STOC 2024], and this enables the important LDPC property. Our efficient list decoding algorithms are obtained by generalizing the classical expander-based weak-regularity list decoding algorithms [Srivastava and Tulsiani, FOCS 2025] [Jeronimo and Singh, 2025] to suitable instantiations of quantum AEL.

In algorithmic statistics a string x is explained by a finite set containing it, and Kolmogorov's structure function records the smallest such model at each level of complexity. Strong models, those computable from the data by a total algorithm, are essentially the cells of simple partitions, so a partition of {0,1}^n can be read as a hypothesis and the cell containing x as the model it assigns. We develop algorithmic statistics over symmetric partitions, the orbit partitions of groups acting on strings. The Galois connection between subgroups and partitions gives each ambient group G a lattice of symmetric partitions with canonical certificates, joins and meets. A set is a cell of a symmetric partition exactly when its setwise stabiliser in G acts transitively on it, so the resulting structure function is Kolmogorov's restricted to these G-homogeneous sets. With a symmetric sophistication, it measures which part of the regularity of x is symmetric. Under the full symmetric group, cells recover all models and cells of cheap partitions recover exactly the strong models, so normal and strange strings are characterised by symmetry. For GL(n,2) the homogeneous sets are the linearly homogeneous ones, whose XOR dependencies look the same from every point. The GL structure function of a nonzero x lies in a band between C(x) - alpha and n - alpha, and both edges are attained: some stochastic normal strings have simple structure invisible to linear symmetry, with sophistication near 0 but GL-sophistication near C(x). We coordinatise permutation groups by a Burnside ring element (type) and a permutation (placement). In these coordinates a linear hypothesis is determined by its type up to n^2 bits, and any space of symmetry hypotheses small enough to search is small enough to miss simple structure. This sets up learned search over orbit models, the subject of later papers in the series.

Protocols for quantum state tomography can be characterized either by their sample complexity or by the tomographic rate function that governs the large deviation behaviour of error estimates. We establish a framework for the analysis of covariant protocols which allows us to compare these measures. First, we derive the rate functions for several protocols, including random purification-based protocols and the sample-optimal protocol of Haah et al. These rate functions are expressed in terms of a new family of divergences which includes the reverse sandwiched Rényi divergence and Keyl's annealed quantum relative entropy as special cases. We show that these rate functions obey a strict ordering, even though the sample complexity of each protocol is order optimal. We consider a different version of sample complexity based on Wasserstein distance rather than trace distance, and show that the ordering of the rate functions implies analogous strict inequalities for the Wasserstein-type sample complexity. Thus the tomographic rate function is a more fine-grained indicator of the performance of a tomography protocol than the usual sample complexity.

Quantum list recovery (QLR) and quantum list decoding (QLD) seek short lists of logically distinct Pauli corrections consistent with a syndrome and prescribed error constraints. For CSS codes, two issues arise: treating the \(X\)- and \(Z\)-sectors separately can multiply their output list sizes, while distinct classical candidates can collapse after stabilizer quotienting. We study combinatorial upper and lower bounds for balanced folded quantum Reed–Solomon (FQRS) codes and balanced random CSS codes, both studied by Bergamaschi, Golowich, and Gunn (STOC 24). Let \(R\in(0,1)\) be the quantum rate and \(R_1=(1+R)/2\) the common component rate. As the radius \(\rho=(1-R)/2-\gamma\) approaches the quantum Singleton bound, we have, deterministically for FQRS codes and w.h.p. for balanced random CSS codes, \[ L^\star_{\rm QLR} = \ell^{\Theta(R_1/\gamma)}, \qquad L^\star_{\rm QLD} = \Theta\!\left(\frac{1-R}{\gamma}\right) \qquad (\gamma\downarrow0). \] The asymptotically exact QLD radius tradeoff is \[ \rho_L^\star = \frac{L}{L+1}\frac{1-R}{2}. \] These conclusions extend to the average-radius setting. For achievability, building on the work of Brakensiek, Chen, Dhar, and Zhang (STOC 2026), we establish a pairing lemma for joint \(X/Z\) candidate lists that preserves the one-sector coefficient and avoids a product loss in list size. For the QLD converse, we prove a quantum generalized Singleton bound based on the classical projection-and-patching argument with stabilizer distinctness. For the QLR lower bounds, we adapt the folded Reed–Solomon construction of Chen and Zhang (STOC 2025) so that the candidates remain stabilizer distinct. For random CSS codes, we show classical bad lists survive the stabilizer quotient with high probability.

Constructing explicit codes matching the parameters of random codes has been a central and largely elusive question in coding theory. The quantum setting is even more challenging since it is highly desirable that the quantum code be an LDPC code. Local coordinate-wise linear (LCL) [Levi, Mosheiff, and Shagrithaya, FOCS 2025] witnesses provide a unifying language for many coding-theoretic properties, from distance to list decoding and list recovery. In particular, it provides a framework to study properties of random linear codes, which achieve optimal parameters for many properties of linear codes. For CSS quantum codes, however, a local witness has two distinct ranks: its physical rank before quotienting by stabilizers and its logical rank after quotienting. We develop a quantum version of the LCL framework for nested spaces $S \subseteq C$, in which local constraints are imposed on physical representatives while independence is measured in the logical quotient $C/S$. The resulting theory gives a threshold theorem for random CSS codes, and as a consequence shows that the per-sector rate threshold is equal to the classical rate threshold. We also define a quantum analogue of subspace design [Guruswami and Xing, STOC 2013] and show that they can be described in a natural manner within the quantum-LCL framework. Finally, we give explicit constructions for arbitrary folded quantum-LCL properties, in a manner similar to the LCL derandomization of [Jeronimo and Shagrithaya, STOC 2026]. As a consequence, we obtain the first explicit constructions of quantum list-decodable codes and list-recoverable codes that have optimal list sizes, in addition to explicit quantum subspace design codes. We note that all our explicit constructions are qLDPC codes, an important property for quantum error-correcting codes.

We develop a submodular framework for the von Neumann entropy of discrete quantum convolutions, providing a noncommutative counterpart to the direct side of entropic additive combinatorics. We first introduce globally weighted quantum convolutions, which form compatible families indexed by admissible subsets of a fixed collection of inputs. Our main theorem reveals a polymatroidal geometry underlying their entropy growth: relative to any fixed admissible input block, the entropy gains admit a normalized, monotone, submodular extension to all subsets of the remaining inputs. The theorem yields convolutional strong subadditivity, quantum Ruzsa triangle inequality, and quantum entropic Plünnecke–Ruzsa inequalities for arbitrary input states. For repeated inputs, it gives sharp comparisons of entropy growth across admissible scales; in particular, the quantum doubling constant controls all higher admissible convolution entropies with optimal exponents. Together, these results bring submodular methods from additive combinatorics into the quantum setting and provide a systematic route to broad families of convolutional entropy inequalities.

We develop a mixing time method for estimating the sample complexity of quantum state discrimination. We start with considering the minimum-error discrimination of geometrically uniform pure state ensembles, and prove that its sample complexity has a tight estimate given by a quantum homogeneous mixing time [George et al., 2026] and a quantum version of the generalized Dobrushin coefficient [Wolfer, 2020]. This quantum mixing time further reduces to a classical one when the generating group $G$ forms a Gelfand pair with the stabilizer subgroup $H$ of the generator state. In this case the generalized Dobrushin coefficient can be fully expressed by representation-theoretic quantities of the commutative Hecke algebra $\operatorname{End}_G(\mathbb C[G/H])$. In particular, this method reduces the sample complexity estimation of learning quantum coupon collector states [Arunachalam et al., 2020] and learning phase states to classical mixing time problems. We apply this framework to answer the open problems of learning degree-$d$ phase states over $\mathbb F_q$ in [Alrabiah et al., 2026] and generalized Boolean phase states over $\mathbb Z_q$ [Arunachalam et al., 2023]. The framework also applies to hypergraph state ensembles, giving estimates expressed fully in terms of hypergraph data and recovering estimates for graph state ensembles in [Montanaro and Shao, 2022]. Finally, we extend the discussion to arbitrary mixed state ensembles with uniform priors, prove a sandwiched bound for minimum-error discrimination sample complexity by a quantum weakly mixing time, and provide a tight estimate for the minimax discrimination sample complexity from [D'Ariano et al., 2005] by a Dobrushin-type coefficient. We also discuss the method of strengthened data processing inequality [Gao and Rouzé, 2022] and give an upper bound in terms of a strengthened data processing inequality constant.

We present a universal entanglement distillation protocol that asymptotically achieves the distillable entanglement of any unknown bipartite state in a fixed finite dimension. That is, its ebit yield attains every rate below the optimum that would be available if the state were known, with vanishing trace-distance error. Our approach combines tomography by local operations and classical communication with an adaptive distillation routine, using a local robustness lemma to control finite-sample estimation errors. We also characterize worst-case distillation from a family of states: the optimal uniform rate is the minimum distillable entanglement on the family's closure. These results show that ignorance of the state need not incur an asymptotic rate penalty.

The bosonic quantum entropy power inequality bounds the entropy of a beam-splitter output in terms of the input entropies. We determine its complete equality class among independent inputs of finite mean photon number: for any number of modes and any transmissivity strictly between zero and one, equality in either the linear or the exponential form holds if and only if the inputs are Gaussian with the same covariance matrix, allowing arbitrary displacements. The main step shows that equality for one output forces the two outputs to be independent: a thermal auxiliary converts equality into preservation of mutual information by a fixed noisy channel, and a two-outcome instrument shows that preservation of mutual information requires a product state with the reference. The quantum Darmois–Skitovich theorem then gives Gaussianity, while a central-limit argument reduces exponential equality to linear equality.

Routing unknown quantum information across distributed communication networks requires autonomous, measurement-free mechanisms to prevent wave-function collapse. Szegedy quantum walks provide a mechanism for spatial state transport. The conventional walks on unweighted graphs suffer from severe back-reflection, spatial dispersion, and channel crosstalk. In this paper, we introduce a deterministic topological quantum routing architecture based on coined Szegedy quantum walks on edge-duplicated signed graphs. By treating edge signs as localized phase shifts within a balanced coin reflection, we enforce an exact zero back-scattering condition across routing nodes. We demonstrate deterministic Perfect State Transfer (PST) with unit fidelity at exact arrival times across fundamental archetypes, including the signed dumbbell switch $D_{2m,0,2n}$ and scalable glued binary trees. Furthermore, we analyse routing performance under realistic open-system amplitude and phase damping noise channels.