One random output can require much less work than numerical evaluation. We study exact neural sampling, counting input probes, random bits, arithmetic, and every precision refinement. For dense tanh networks with absolute row sums at most one, weight preprocessing permits polylogarithmic expected sampling work at logarithmic depth. With zero biases, the sharp query scale is the square root of depth at every fixed first-layer rank, and also at arbitrary rank when a column envelope is bounded. The unrestricted gap between square-root and linear query cost remains open. Prefill changes attention. We construct an appendable cache index and a complete exact decoder with positive RMSNorm stabilizers. Its expected work is polynomial in model size and log T when each layer has a common affine key space of fixed rank and the context has length T. The decoder's polynomial degree grows with rank. These bounds give no useful speed prediction at the large ranks of ordinary models. A completely fixed full-rank model still has a formal polylogarithmic context bound, with potentially enormous constants. The decoder maintains finite Taylor moments, prepares precision in the background, and charges rare complete refinements by their probability. Its cost includes neural key and value creation. Without a context index, standard scaling can force linear positional search; arbitrary indexed queries face a conditional barrier in growing dimension. We also prove exact normalization factories and a matching law for an explicit additive-residual family. A checkpoint section gives the certificates and cost formulas needed to apply each positive result.
One random output can require much less work than numerical evaluation. We study exact neural sampling, counting input probes, random bits, arithmetic, and every precision refinement. For dense tanh networks with absolute row sums at most one, weight preprocessing permits polylogarithmic expected sampling work at logarithmic depth. With zero biases, the sharp query scale is the square root of depth at every fixed first-layer rank, and also at arbitrary rank when a column envelope is bounded. The unrestricted gap between square-root and linear query cost remains open. Prefill changes attention. We construct an appendable cache index and a complete exact decoder with positive RMSNorm stabilizers. Its expected work is polynomial in model size and log T when each layer has a common affine key space of fixed rank and the context has length T. The decoder's polynomial degree grows with rank. These bounds give no useful speed prediction at the large ranks of ordinary models. A completely fixed full-rank model still has a formal polylogarithmic context bound, with potentially enormous constants. The decoder maintains finite Taylor moments, prepares precision in the background, and charges rare complete refinements by their probability. Its cost includes neural key and value creation. Without a context index, standard scaling can force linear positional search; arbitrary indexed queries face a conditional barrier in growing dimension. We also prove exact normalization factories and a matching law for an explicit additive-residual family. A checkpoint section gives the certificates and cost formulas needed to apply each positive result.
We present an Ising-compatible framework for formal neural-network robustness verification under bounded input perturbations. For piecewise activations (both continuous piecewise-linear and discrete piecewise-constant), the Exact Logarithmic Piecewise Model (Log-PW) provides an exact, sound, and complete formulation with a state-optimal logarithmic encoding, reducing the binary variables per neuron from linear O(κ) to information-theoretically minimal logarithmic complexity O(⌈log2κ⌉) via logarithmic SOS2 (Log-PWL) and SOS1 (Log-PWC) constraints. For general element-wise activations, the Asymptotic Step-Envelope Model (Step-Env) leverages Log-PWC to construct sound, refinable endpoint enclosures. An exact monotonic reduction based on Jordan decomposition further extends this framework to arbitrary non-monotonic activations. We further develop a hybrid Benders solver with output-sensitive iteration bounds, leveraging a Helly-based conflict compression theory to avoid generic exponential cut explosion. In particular, for shallow networks with fixed input dimension, this establishes an unconditionally polynomial Benders iteration complexity in network size. Interval pruning, certificate transfer for pruned networks, and layerwise classical--Ising partitioning further reduce spin requirements. Experiments demonstrate exact certification fidelity for piecewise-linear networks and near-reference accuracy for non-linear activations under compact spin budgets. On MNIST benchmarks, Log-PW halves binary decision spins over One-Hot formulations, while Helly-based cuts achieve up to a 13.41× speedup and an 87.6% reduction in master queries over standard baselines.
Maximum-likelihood decoding provides an optimal decoding strategy for quantum error correction under stochastic Pauli noise. However, computing logical-class probabilities is challenging, and the leading exact tensor-network contraction requires time exponential in treewidth. In this work, we introduce a new decoding algorithm based on rank-decomposition dynamic programming (Rank DP). We express decoding partition functions with independent local fault factors as quadratic sums of powers and apply Rank DP. The resulting exact evaluator has arithmetic complexity polynomial in the input size and exponential in the Tanner graph's rank-width with respect to the fault partition, including decomposition construction. After Gaussian elimination, it gives polynomial-time decoding for punctured quantum Reed-Muller codes and a Steane-concatenated family with growing distance under independent single-qubit Pauli noise. Standard contraction of the corresponding tensor networks requires superpolynomial time. A nonnegative realization gives relative floating-point error bounds under explicit arithmetic assumptions. Numerical experiments demonstrate runtime advantages over the tested tensor-network implementations on selected code-capacity and circuit-level instances, with full likelihood evaluation for Reed-Muller codes up to 1,023 qubits. We further use these likelihoods to learn circuit noise parameters from syndromes, evaluate rare postselection probabilities, and quantify decoder optimality gaps. Our work opens new avenues for exploiting algebraic structure in quantum decoding and noise characterization.
Softmax self-attention costs O(T^2) in the sequence length T because the exponential kernel has no finite-dimensional feature map, so linear-time variants approximate it. We observe that Born-rule attention, whose weights are quantum-measurement probabilities a_kj ∝ |<Q_k, K_j>|^2 over complex queries and keys, is an exact finite kernel with the rank-one density-matrix feature map ρ_x = x x†, since |<Q_k, K_j>|^2 = tr(ρ_Qk ρ_Kj). As the complex degree-two case of polynomial-kernel linear attention it admits an exact O(T d^2) causal recurrence and constant-state decoding (d^2 (d_v + 1) reals per head, with d_v the real value width, independent of T), and it keeps rotary positions exactly. For GPT-2's head geometry (64 real channels paired into d = 32 complex) the feature dimension is d^2 = 1024. Measured on an A100, compiled constant-state decoding runs from 6.4 MB per layer at 0.12 ms per token at any length, against a 3.2 GB FlashAttention-2 cache at 2.26 ms per token at 1M tokens; unfused prefill overtakes FlashAttention-2 between 64k and 128k tokens (11x at 1M), and a fused form (Triton feature lift plus a chunkwise linear-attention kernel) between 16k and 32k (4x at 128k), reaching training parity at 64k. The linear and quadratic forms are two implementations of one operator; whether that operator matches softmax is a separate modeling question, answered here only at small scale: the p = 1 operator bolted into a real-valued GPT trails softmax by 0.12 nats at context 1k and 0.77 at 16k (attention dilution; a decay kept exactly in the d^2 state restores the 0.12 gap at 16k, and p = 2 sharpening with decay recovers 74% of the 1k gap), whereas inside a fully complex residual stream it matches softmax at 1k and keeps a quarter of the real-stream gap at 4k; gated linear attention beats both there. At 128k context on PG-19 the variable that matters is forgetting: plain Born dilutes, Born with a fixed decay carried in its state is 0.32 nats ahead of softmax and within 0.04 of gated linear attention, which stays 1.8x faster. Streamed with their constant state over the PG-19 test partition in 5M-byte windows, two 4M-complex-parameter byte models of the source framework score 1.66 (linear Born with decay) and 1.70 (gated) bits per byte, where a 350M-parameter hierarchical Mamba–Transformer stack built for that window reports 2.45. Preprint, October 2026. Also submitted to arXiv (identifier to be added on announcement). Code: the CNet framework, https://github.com/crasmarum/CNet .
We turn cumulative population-average conditional KL error into hard computational guarantees for parallel sampling. For a target distribution on [V]n, let Δ be the expected cumulative conditional KL over a uniformly random reveal order. Under Δ ≤ ε2/32, we obtain total variation error at most ε with two complementary resource guarantees. Binary blocked recursive speculative rejection sampling uses O(√(n(1 + log V)) log3(2n)/ε) rounds and O(n log(2n)/ε) full-vector queries. Shallow trees use Oh(n1/2 + 1/(2h) polylog(n, V, 1/ε)) rounds and O(n(h + 1)/ε) queries for fixed h ≥ 2. Both guarantees hold on every run for fixed, strictly positive conditional interfaces, including incompatible answers. Complete execution histories capture the cost of discarded trials; residual-KL control yields the sharper precision dependence. Online truncation enforces both budgets. An algorithm-specific Ω(nΔ) expected-depth construction exposes the cost of direct single-root execution. We identify the precision regimes relative to sequential and prefetch baselines, and illustrate the budget-error relation with exact finite-state calculations. This preprint includes the complete proof appendices and summaries of the archived computational checks. Executable verification files are not included in this record.
Sampling problems give some of the clearest conditional separations between quantum and classical computation. In Fermion Sampling, passive linear optics acts on a non-Gaussian magic input. Globally Haar-random transformations give anticoncentration and high-precision average-case hardness, but require linear depth and quadratically many gates. A natural open question is whether linear depth is necessary?
We show that logarithmic depth suffices for both guarantees in the same ensemble. For fresh uniform matchings with independent Haar two-mode gates, the collision reaches the passive-Haar scale at a sharp threshold of logn/log(9/4)≈0.855log2n layers, with an explicit limiting transition profile and a matching lower bound from two-particle correlations. The mechanism is input-dependent: the magic input suppresses the extensive weight of the slowest relaxation mode, leaving the next to set the scale. An occupation-basis input retains large collision even under full Haar randomness.
At a larger logarithmic depth, we prove, in the real-RAM model, average-case #P-hardness of estimating output probabilities to additive error 2−O(nlog2n) on any fixed fraction of instances above 3/4. We construct hard instances in four native layers, embed them in typical schedules, and interpolate along Cayley paths using a rational linear-program decoder. A finite 192-gate alphabet preserves the collision law exactly. Both guarantees use logarithmic native fermionic depth between arbitrary mode pairs and O(nlogn) gates, replacing the global-Haar construction's quadratic budget. The accuracy proved is finer than the 1/N scale, where N=(n/2n), required by sampling-to-counting; hardness of sampling within constant total-variation distance remains open.
We propose a general framework for the estimation of observables with generative neural samplers focusing on modern deep generative neural networks that provide an exact sampling probability. In this framework, we present asymptotically unbiased estimators for generic observables, including those that explicitly depend on the partition function such as free energy or entropy, and derive corresponding variance estimators. We demonstrate their practical applicability by numerical experiments for the two-dimensional Ising model which highlight the superiority over existing methods. Our approach greatly enhances the applicability of generative neural samplers to real-world physical systems.