Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

When Coarse Scores Suffice for Diffusion Steering

Shardul Mishra

Published Nov 15, 2026• 0 citations
Publisher

Abstract

Recent work on quadratic diffusion steering raised two questions: whether negative quadratic rewards admit sampling algorithms polynomial in the numerical magnitude of the reward, and how imperfect score access changes their tractability. We answer the first and characterise the second at two ends of the score-precision range. For bounded priors and fixed-rank symmetric quadratic rewards, sufficiently precise isotropic diffusion scores permit sampling in time polynomial in the numerical parameters, including the reward magnitude. This is a pseudopolynomial guarantee, not a bound polynomial in binary encoding length. At fixed absolute score tolerance, however, rank-one negative quadratic rewards exhibit a distinct, unconditional information-access barrier: in dimension m+1, the worst-case query complexity at constant Wasserstein accuracy has exponential order exp(Θ(m log(1+λ/m))), up to polynomial factors. The lower bound holds even for smooth priors with known marginals and reward normaliser. Matching upper-exponent constructions use rare-event likelihood-ratio control and Gaussian auxiliary sampling. Known low-dimensional nuisance geometry permits polynomial-query sampling for fixed auxiliary dimension, while noise cutoffs and prior-average denoising error can conceal reward-relevant rare modes. These results distinguish numerical score precision from access to the information needed for reliable posterior steering.

DOI
10.5281/zenodo.24259283

Related papers

Steering diffusion models with quadratic rewards: a fine-grained analysis

Ankur Moitra, Andrej Risteski, Dhruv Rohatgi

Inference-time algorithms are an emerging paradigm in which pre-trained models are used as subroutines to solve downstream tasks. Such algorithms have been proposed for tasks ranging from inverse problems and guided image generation to reasoning. However, the methods currently deployed in practice are heuristics with a variety of failure modes -- and we have very little understanding of when these heuristics can be efficiently improved. In this paper, we consider the task of sampling from a reward-tilted diffusion model -- that is, sampling from $p^{\star}(x) \propto p(x) \exp(r(x))$ -- given a reward function $r$ and pre-trained diffusion oracle for $p$. We provide a fine-grained analysis of the computational tractability of this task for quadratic rewards $r(x) = x^\top A x + b^\top x$. We show that linear-reward tilts are always efficiently sampleable -- a simple result that seems to have gone unnoticed in the literature. We use this as a building block, along with a conceptually new ingredient -- the Hubbard-Stratonovich transform -- to provide an efficient algorithm for sampling from low-rank positive-definite quadratic tilts, i.e. $r(x) = x^\top A x$ where $A$ is positive-definite and of rank $O(1)$. For negative-definite tilts, i.e. $r(x) = - x^\top A x$ where $A$ is positive-definite, we prove that the problem is intractable even if $A$ is of rank 1 (albeit with exponentially-large entries).

arXiv:2602.16570•Feb 18, 2026•6 citations

The query complexity of sampling from strongly log-concave distributions in one dimension

Sinho Chewi, Patrik Gerber, Chen Lü +2 more

We establish the first tight lower bound of $Ω(\log\logκ)$ on the query complexity of sampling from the class of strongly log-concave and log-smooth distributions with condition number $κ$ in one dimension. Whereas existing guarantees for MCMC-based algorithms scale polynomially in $κ$, we introduce a novel algorithm based on rejection sampling that closes this doubly exponential gap.

arXiv:2105.14163•May 29, 2021•5 citations

Exact Sampling from Neural Networks: Depth, Attention, and Decoding

Samuel Mausberg

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.

•Oct 8, 2026•0 citations

The Tractability Landscape of Sampling with Inexact Scores

Anming Gu, Kevin Tian, Hubert Yang +1 more

We provide a simple and tight characterization of the types of inexact score oracle access that permit sampling with vanishing total variation bias, for a standard, well-behaved target family. Our main result shows that any weaker error than the sub-Gaussian assumption used by [YW26] rules out the tractability of unbiased sampling. This strengthens the conclusion of [CCSW26] to be algorithm-agnostic, and to hold for a wider range of error assumptions.

arXiv:2607.19004•Jul 21, 2026•0 citations

Source-Prior Engineering for Bayesian Optical Sensing in Time-Reversed Young Interferometry

Jianming Wen

Time-reversed Young (TRY) interferometry reconstructs interference from a fixed detector by reading out a programmable source-label distribution. This work formulates the architecture as a source-coded Bayesian response sensor. For a perturbation parameter θ, the detected source-label histogram is a posterior distribution determined by a programmed source prior, an optical likelihood for a fixed-detector click, and an evidence factor equal to the click probability. The key point is not the Bayesian identity itself, but its physical implementation: in TRY the prior is imposed before propagation and can therefore reshape the response ensemble actually sampled by the detector. The normalized posterior is shown to respond through a centered likelihood score, and the detected-event Fisher information is the posterior variance of this score. This identifies posterior-weighted score contrast, rather than local response magnitude alone, as the relevant sensing resource. The framework separates posterior-shape information from evidence information, giving a resource-aware way to judge near-null response enhancement. It also yields practical design rules: a two-label source code converts a weak perturbation into a fixed-detector label imbalance, while the multiparameter score covariance provides a route to nuisance rejection and gives a minimal-label rank condition for sensing multiple perturbations. A passive double-slit implementation with weak one-slit phase and loss perturbations is proposed, requiring only fixed-detector source scans before and after calibrated perturbations. Practical tolerances associated with source-programming error, drift, background, imperfect coherence, and polarization mismatch are analyzed, and extensions to multi-aperture and integrated photonic systems are formulated. The results position TRY as a source-programmable Bayesian sensing architecture complementary to conventional detector-plane Young interferometry.

Sensors•Jul 23, 2026•3 citations

Breaking the Multiplicative Overhead in Quantum Entropy Estimation

Junxiang Huang, Chenyang Li, Lu-Fan Zhang +2 more

The von Neumann, Tsallis, and Rényi entropies are fundamental measures of quantum information. A common estimation strategy multiplies the worst-case costs of spectral transformation and statistical readout, leaving gaps to query lower bounds. We reduce this overhead with multi-level algorithms that use local normalization and precision allocation, while variable-time estimation accounts for the probability of reaching expensive spectral tests. With controlled purified access and its inverse, we obtain bounds for additive error $\varepsilon$, rank upper bound $R$, and fixed order $α$. Tsallis entropy estimation has near-optimal rank-independent query complexity $\widetilde O(\varepsilon^{-1/(α-1)})$ for $1<α<2$, when the allowed dimension and rank accommodate the lower-bound instances, and $\widetilde O(1/\varepsilon)$ for $α\ge2$, where $\widetilde O$ suppresses logarithmic factors. The first saves a factor $1/\varepsilon$; the second extends known integer-order scaling to noninteger orders. We also improve the von Neumann entropy bound from $\widetilde O(R/\varepsilon^2)$ to $\widetilde O(R/\varepsilon)$ and obtain $\widetilde O(R/\varepsilon)$ for noninteger Rényi orders $1<α<3$, with further bounds at other orders. Our functional-estimation theorem replaces the global product by a sum of local costs weighted by function magnitudes and spectral masses. We further estimate fixed logarithmic moments and entropy variance using $\widetilde O(R/\varepsilon)$ queries, providing efficient access to fluctuation parameters that enter finite-blocklength quantum compression and pure-state entanglement conversion. More broadly, our framework extends beyond entropy to a broad class of density-matrix functionals, offering a systematic approach toward optimal query complexity in quantum spectral estimation.

quant-pharXiv:2609.40179•Oct 1, 2026•0 citations
Recent work on quadratic diffusion steering raised two questions: whether negative quadratic rewards admit sampling algorithms polynomial in the numerical magnitude of the reward, and how imperfect score access changes their tractability. We answer the first and characterise the second at two ends of the score-precision range. For bounded priors and fixed-rank symmetric quadratic rewards, sufficiently precise isotropic diffusion scores permit sampling in time polynomial in the numerical parameters, including the reward magnitude. This is a pseudopolynomial guarantee, not a bound polynomial in binary encoding length. At fixed absolute score tolerance, however, rank-one negative quadratic rewards exhibit a distinct, unconditional information-access barrier: in dimension m+1, the worst-case query complexity at constant Wasserstein accuracy has exponential order exp(Θ(m log(1+λ/m))), up to polynomial factors. The lower bound holds even for smooth priors with known marginals and reward normaliser. Matching upper-exponent constructions use rare-event likelihood-ratio control and Gaussian auxiliary sampling. Known low-dimensional nuisance geometry permits polynomial-query sampling for fixed auxiliary dimension, while noise cutoffs and prior-average denoising error can conceal reward-relevant rare modes. These results distinguish numerical score precision from access to the information needed for reliable posterior steering.
Inference-time algorithms are an emerging paradigm in which pre-trained models are used as subroutines to solve downstream tasks. Such algorithms have been proposed for tasks ranging from inverse problems and guided image generation to reasoning. However, the methods currently deployed in practice are heuristics with a variety of failure modes -- and we have very little understanding of when these heuristics can be efficiently improved. In this paper, we consider the task of sampling from a reward-tilted diffusion model -- that is, sampling from p⋆(x)∝p(x)exp⁡(r(x))p^{\star}(x) \propto p(x) \exp(r(x))p⋆(x)∝p(x)exp(r(x)) -- given a reward function rrr and pre-trained diffusion oracle for ppp. We provide a fine-grained analysis of the computational tractability of this task for quadratic rewards r(x)=x⊤Ax+b⊤xr(x) = x^\top A x + b^\top xr(x)=x⊤Ax+b⊤x. We show that linear-reward tilts are always efficiently sampleable -- a simple result that seems to have gone unnoticed in the literature. We use this as a building block, along with a conceptually new ingredient -- the Hubbard-Stratonovich transform -- to provide an efficient algorithm for sampling from low-rank positive-definite quadratic tilts, i.e. r(x)=x⊤Axr(x) = x^\top A xr(x)=x⊤Ax where AAA is positive-definite and of rank O(1)O(1)O(1). For negative-definite tilts, i.e. r(x)=−x⊤Axr(x) = - x^\top A xr(x)=−x⊤Ax where AAA is positive-definite, we prove that the problem is intractable even if AAA is of rank 1 (albeit with exponentially-large entries).
We establish the first tight lower bound of Ω(log⁡log⁡κ)Ω(\log\logκ)Ω(loglogκ) on the query complexity of sampling from the class of strongly log-concave and log-smooth distributions with condition number κκκ in one dimension. Whereas existing guarantees for MCMC-based algorithms scale polynomially in κκκ, we introduce a novel algorithm based on rejection sampling that closes this doubly exponential gap.
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.
Time-reversed Young (TRY) interferometry reconstructs interference from a fixed detector by reading out a programmable source-label distribution. This work formulates the architecture as a source-coded Bayesian response sensor. For a perturbation parameter θ, the detected source-label histogram is a posterior distribution determined by a programmed source prior, an optical likelihood for a fixed-detector click, and an evidence factor equal to the click probability. The key point is not the Bayesian identity itself, but its physical implementation: in TRY the prior is imposed before propagation and can therefore reshape the response ensemble actually sampled by the detector. The normalized posterior is shown to respond through a centered likelihood score, and the detected-event Fisher information is the posterior variance of this score. This identifies posterior-weighted score contrast, rather than local response magnitude alone, as the relevant sensing resource. The framework separates posterior-shape information from evidence information, giving a resource-aware way to judge near-null response enhancement. It also yields practical design rules: a two-label source code converts a weak perturbation into a fixed-detector label imbalance, while the multiparameter score covariance provides a route to nuisance rejection and gives a minimal-label rank condition for sensing multiple perturbations. A passive double-slit implementation with weak one-slit phase and loss perturbations is proposed, requiring only fixed-detector source scans before and after calibrated perturbations. Practical tolerances associated with source-programming error, drift, background, imperfect coherence, and polarization mismatch are analyzed, and extensions to multi-aperture and integrated photonic systems are formulated. The results position TRY as a source-programmable Bayesian sensing architecture complementary to conventional detector-plane Young interferometry.
The von Neumann, Tsallis, and Rényi entropies are fundamental measures of quantum information. A common estimation strategy multiplies the worst-case costs of spectral transformation and statistical readout, leaving gaps to query lower bounds. We reduce this overhead with multi-level algorithms that use local normalization and precision allocation, while variable-time estimation accounts for the probability of reaching expensive spectral tests. With controlled purified access and its inverse, we obtain bounds for additive error ε\varepsilonε, rank upper bound RRR, and fixed order ααα. Tsallis entropy estimation has near-optimal rank-independent query complexity O~(ε−1/(α−1))\widetilde O(\varepsilon^{-1/(α-1)})O(ε−1/(α−1)) for 1<α<21<α<21<α<2, when the allowed dimension and rank accommodate the lower-bound instances, and O~(1/ε)\widetilde O(1/\varepsilon)O(1/ε) for α≥2α\ge2α≥2, where O~\widetilde OO suppresses logarithmic factors. The first saves a factor 1/ε1/\varepsilon1/ε; the second extends known integer-order scaling to noninteger orders. We also improve the von Neumann entropy bound from O~(R/ε2)\widetilde O(R/\varepsilon^2)O(R/ε2) to O~(R/ε)\widetilde O(R/\varepsilon)O(R/ε) and obtain O~(R/ε)\widetilde O(R/\varepsilon)O(R/ε) for noninteger Rényi orders 1<α<31<α<31<α<3, with further bounds at other orders. Our functional-estimation theorem replaces the global product by a sum of local costs weighted by function magnitudes and spectral masses. We further estimate fixed logarithmic moments and entropy variance using O~(R/ε)\widetilde O(R/\varepsilon)O(R/ε) queries, providing efficient access to fluctuation parameters that enter finite-blocklength quantum compression and pure-state entanglement conversion. More broadly, our framework extends beyond entropy to a broad class of density-matrix functionals, offering a systematic approach toward optimal query complexity in quantum spectral estimation.