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.
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.
Abstract Random unitaries are useful in quantum information and related fields, but hard to generate with limited resources. An approximate unitary k -design is an ensemble of unitaries with an underlying measure over which the average is close to a Haar random ensemble up to the first k moments. A particularly strong notion of approximation bounds the distance from Haar randomness in relative error. Such relative-error approximate designs are secure against queries by an adaptive adversary trying to distinguish it from a Haar ensemble. We construct relative-error approximate unitary k -design ensembles for which communication between subsystems is O (1) in the system size. These constructions use the alternating projection method to analyze overlapping Haar averages, giving a bound on the convergence speed to the full averaging with respect to the 2-norm. Using von Neumann subalgebra indices to replace system dimension, the 2-norm distance converts to relative error without introducing any additional dimension dependence. We use these constructions as the building blocks of a two-step protocol that achieves a relative-error design in O((logm+log(1/ϵ)+klogk)kpolylog(k)) O ( ( log m + log ( 1 / ϵ ) + k log k ) k polylog ( k ) ) depth, where m is the number of qudits in the complete system and ϵ ϵ the approximation error. This sublinear depth construction answers a variant of [21, Harrow and Mehraban 2023, Section 1.5, Open Question 1] and [21, Harrow and Mehraban 2023, Section 1.5, Open Question 7]. Moreover, entanglement generated by the sublinear depth scheme follows area laws on spatial lattices up to corrections logarithmic in the full system size.
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 show how to use parallelization to speed up sampling from an arbitrary distribution µ on a product space [q]n, given oracle access to counting queries: ℙX∼ µ[XS=σS] for any S⊆ [n] and σS ∈ [q]S. Our algorithm takes O(n2/3· polylog(n,q)) parallel time, to the best of our knowledge, the first sublinear in n runtime for arbitrary distributions. Our results have implications for sampling in autoregressive models. Our algorithm directly works with an equivalent oracle that answers conditional marginal queries ℙX∼ µ[Xi=σi | XS=σS], whose role is played by a trained neural network in autoregressive models. This suggests a roughly n1/3-factor speedup is possible for sampling in any-order autoregressive models. We complement our positive result by showing a lower bound of Ω(n1/3) for the runtime of any parallel sampling algorithm making at most poly(n) queries to the counting oracle, even for q=2.
The computational equivalence between approximate counting and sampling is well established for polynomial-time algorithms. The most efficient general reduction from counting to sampling is based on simulated annealing. In this approach, the counting problem is formulated as estimating the ratio Q = Z(βmax)/Z(βmin) between partition functions Z(β) = Σx∈Ω exp(βH(x)) of Gibbs distributions μβ over Ω with Hamiltonian H, given access to a sampling oracle for μβ at any β ∈ [βmin, βmax]. The sample complexity (measured by the number of oracle calls) is typically expressed in terms of q and h, which respectively bound ln Q and H. The best upper bound achieved by known annealing algorithms with relative error ε is O(qε−2 log h). However, all known algorithms attaining this near-optimal complexity are inherently sequential, or adaptive: the queried parameters β depend on previous samples.
Random unitaries are useful in quantum information and related fields but hard to generate with limited resources. An approximate unitary k-design is a measure over an ensemble of unitaries such that the average is close to a Haar (uniformly) random ensemble up to the first k moments. A strong notion of approximation bounds the distance from Haar randomness in relative error: the weighted twirl induced by an approximate design can be written as a convex combination involving that of an exact design and vice versa. The main focus of our work is on efficient constructions of approximate designs, in particular whether relative-error designs in sublinear depth are possible. We give a positive answer to this question as part of our main results: 1. Twirl-Swap-Twirl: Let A and B be systems of the same size. Consider a protocol that locally applies k-design unitaries to A^k and B^k respectively, then exchanges l qudits between each copy of A and B respectively, then again applies local k-design unitaries. This protocol yields an ε-approximate relative k-design when l = O(k log k + log(1/ε)). In particular, this bound is independent of the size of A and B as long as it is sufficiently large compared to k and 1/ε. 2. Twirl-Crosstwirl: Let A_1, … , A_P be subsystems of a multipartite system A. Consider the following protocol for k copies of A: (1) locally apply a k-design unitary to each A_p for p = 1, … , P; (2) apply a "crosstwirl" k-design unitary across a joint system combining l qudits from each A_p. Assuming each A_p’s dimension is sufficiently large compared to other parameters, one can choose l to be of the form 2 (Pk + 1) log_q k + log_q P + log_q(1/ε) + O(1) to achieve an ε-approximate relative k-design. As an intermediate step, we show that this protocol achieves a k-tensor-product-expander, in which the approximation error is in 2 → 2 norm, using communication logarithmic in k. 3. Recursive Crosstwirl: Consider an m-qudit system with connectivity given by a lattice in spatial dimension D. For every D = 1, 2, …, we give a construction of an ε-approximate relative k-design using unitaries of spatially local circuit depth O ((log m + log(1/ε) + k log k ) k polylog(k)). Moreover, across the boundaries of spatially contiguous sub-regions, unitaries used in the design ensemble require only area law communication up to corrections logarithmic in m. Hence they generate only that much entanglement on any product state input. These constructions use the alternating projection method to analyze overlapping Haar twirls, giving a bound on the convergence speed to the full twirl with respect to the 2-norm. Using von Neumann subalgebra indices to replace system dimension, the 2-norm distance converts to relative error without introducing system size. The Recursive Crosstwirl construction answers one variant of [Harrow and Mehraban, 2023, Open Problem 1], showing that with a specific, layered architecture, random circuits produce relative error k-designs in sublinear depth. Moreover, it addresses [Harrow and Mehraban, 2023, Open Problem 7], showing that structured circuits in spatial dimension D of depth << m^{1/D} may achieve approximate k-designs.
We show that the NP-Complete language 3Sat has a PCPverifier that makes two queries to a proof of almost-linear size and achieves sub-constant probability of error o(1). The verifier performs only projection tests, meaning that the answer to the first query determines at most one accepting answer to the second query.Previously, by the parallel repetition theorem, there were PCP Theorems with two-query projection tests, but only (arbitrarily small) constant error and polynomial size.There were also PCP Theorems with sub-constant error andalmost-linear size, but a constant number of queries that is larger than 2.As a corollary, we obtain a host of new results. In particular, our theorem improves many of the hardness of approximation results that are proved using the parallel repetition theorem. A partial list includes the following:(1) 3Sat cannot be efficiently approximated to withina factor of 7/8+o(1), unless P = NP. This holds even under almost-linear reductions. Previously, the best knownNP-hardness factor was 7/8+epsilon for any constant epsilonGt0, under polynomial reductions.(2) 3Lin cannot be efficiently approximated to withina factor of 1/2+o(1), unless P = NP. This holdseven under almost-linear reductions. Previously, the best known NP-hardness factor was 1/2+epsilon for any constant epsilonGt0, under polynomial reductions.(3) A PCP Theorem with amortized query complexity 1 + o(1)and amortized free bit complexity o(1). Previously, the best known amortized query complexity and free bit complexity were 1+epsilon and epsilon, respectively, for any constant epsilon Gt 0.One of the new ideas that we use is a new technique for doing the composition step in the (classical) proof of the PCP Theorem, without increasing the number of queries to the proof. We formalize this as a composition of new objects that we call Locally Decode/Reject Codes (LDRC). The notion of LDRC was implicit in several previous works, and we make it explicit in this work. We believe that the formulation of LDRCs and their construction are of independent interest.