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

arXiv:2602.16570

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

Ankur Moitra, Andrej Risteski, Dhruv Rohatgi

Published Feb 18, 2026• 6 citations
arXivHTMLPDF

Abstract

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).

DOI
10.48550/arxiv.2602.16570

Related papers

When Coarse Scores Suffice for Diffusion Steering

Shardul Mishra

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.

•Nov 15, 2026•0 citations

Hyperparameter Optimization and Neuroevolution with Binary Quadratic Meta-heuristics and Evolution Strategies

David Von Dollen, Reuben Brasher, Florian Neukart +1 more

This study extends previous work on quantum-enhanced selection operators [Von Dollen et al.(2022)], where selection operators of evolutionary algorithms for classical black-box optimization are framed as quadratic binary optimization (QUBO) models, applied to black-box objective functions. We test our algorithms using both elitist and non-elitist strategies. First, we benchmark all heuristics over black-box, multi-modal functions. We find that for 94.4% of test cases, our method shows performance improvements with respect to fitness. Then, we similarly benchmark over the problem of hyperparameter selection for machine learning models, also a black-box optimization problem, and compare it to random search. We find that our method achieves some improvement with an average validation accuracy of 98.492% and highest ranking of 4.529412 (out of 5) when averaged across all test cases. We also apply our method towards neuroevolution, where we evolve weight spaces for small feedforward neural networks for learning tasks. In these settings, our method shows improved average reward in the reinforcement learning case and increased velocity in learning the XOR function.

IEEE Congress on Information Science and Technology (CiSt)•Dec 16, 2023•2 citations

Quadratic Advantage with Quantum Randomized Smoothing Applied to Time-Series Analysis

Nicola Franco, Marie Kempkes, Jakob Spiegelberg +1 more

As quantum machine learning continues to develop at a rapid pace, the importance of ensuring the robustness and efficiency of quantum algorithms cannot be overstated. Our research presents an analysis of quantum randomized smoothing, how data encoding and perturbation modeling approaches can be matched to achieve meaningful robustness certificates. By utilizing an innovative approach integrating Grover's algorithm, a quadratic sampling advantage over classical randomized smoothing is achieved. This strategy necessitates a basis state encoding, thus restricting the space of meaningful perturbations. We show how constrained k-distant Hamming weight perturbations are a suitable noise distribution here, and elucidate how they can be constructed on a quantum computer. The efficacy of the proposed framework is demonstrated on a time series classification task employing a Bag-of-Words pre-processing solution. The advantage of quadratic sample reduction is recovered especially in the regime with large number of samples. This may allow quantum computers to efficiently scale randomized smoothing to more complex tasks beyond the reach of classical methods.

arXiv:2407.18021•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•3 citations

Quantum Diffusion Models for Few-Shot Learning

Ruhan Wang, Ye Wang, Jing Liu +1 more

Modern quantum machine learning (QML) methods involve the variational optimization of parameterized quantum circuits on training datasets, followed by predictions on testing datasets. Most state-of-the-art QML algorithms currently lack practical advantages due to their limited learning capabilities, especially in few-shot learning tasks. In this work, we propose three new frameworks employing quantum diffusion model (QDM) as a solution for the few-shot learning: label-guided generation inference (LGGI); label-guided denoising inference (LGDI); and label-guided noise addition inference (LGNAI). Experimental results demonstrate that our proposed algorithms significantly outperform existing methods.

arXiv:2411.04217•IEEE International Conference on AI and Data Analytics (ICAD)•Jun 24, 2025•7 citations

Adversarial Markov Processes for Quantum Generative Machine Learning and Classical Optimization

Blake Anthony Wilson

My dissertation focuses on the analysis and development of algorithms for problems involving adversarial Markov processes (AMPs), including applications in hybrid quantum-classical generative machine learning, semiconductor authentication, and optimization.Markov processes are random processes whose state $\z_t \in S$ evolves to a future state $\z_{t + 1} \in S$ by sampling an adversarial distribution $p_\beta(\z_{t+1} \vert \z_t)$ that depends only on the current state $\z_t$ and a control parameter $\beta$ which is determined a priori. AMPs are an aggregated marginalization $q_\beta(\z_f) = \int_{\z_0} \Gamma_\beta(\z_f \vert \z_0)p(\z_0)$ of the Markov process $\Gamma_\beta = \sum_{\z_{f-1}}p_\beta(\z_{f} \vert \z_{f-1})...\sum_{\z_{1}}p_\beta(\z_{1} \vert \z_{0})$ coupled to a prior $p(\z_0)$. What makes the AMP adversarial is that our only control of $\Gamma_\beta$ is through $\beta$ and we are tasked with choosing the optimal $\beta$ under some problem constraints. For example, in the second chapter of my dissertation, we optimally solve for $\beta$ in three package delivery AMPs where a dispatcher must construct a package delivery plan that maximizes the expected reward for a robot delivering packages across multiple epochs.Each package has an associated reward for delivery and a probabilistic risk of failure given by some adversary in the environment. %Our goal is to maximize the expected reward by choosing the optimal package delivery plan, i.e., AMP control parameter $\beta$.We demonstrate how to use the structure of these AMPs to compute the optimal package delivery plan with the largest expected reward across both a finite and infinite number of epochs in $O(K + n\log n)$ time and $O(n)$ time, respectively, where $K$ is the number of epochs and $n$ is the number of packages. However, not all AMP problems are based on choosing the optimal $\beta$. Instead, $\beta$ can be adversarially chosen for us and we want to infer its value. For example, in Chapter 3, we infer the value of $\beta$ for a package authentication problem involving a mixed AMP where a manufacturer and a customer have to authenticate a semiconductor device using a physical unclonable function (PUF) based on the relative positions and radii of nanoparticles embedded on the packaging of a semiconductor device. Because the PUF's state space is intractable to infer $\beta$ explicitly, existing solutions used Hausdorff-inspired heuristics which work well for small perturbations in the nanoparticle positions.However, we show that under more difficult transformations, the Hausdorff heuristics can be reliably spoofed.To counteract this, we leverage a machine learning discriminator called RAPTOR to infer $\beta$ using attention networks.RAPTOR outperforms the Hausdorff, Procrustes, and average Hausdorff distance metrics, achieving a $40.6\%$, $37.3\%$, and $6.4\%$ total accuracy increase, respectively. In both Chapters 2 and 3, the AMPs are considered {\it adversaries} which we overcome using some algorithm.However, in Chapters 4 and 5, we demonstrate new learning techniques that use AMPs as a {\it resource} for generative machine learning. More specifically, the AMP parameter vector $\beta$ acts as an inverse temperature and/or energy function parameter for optimization and sampling using the AMPs.Specifically in Chapter 4, we demonstrate a quantum machine learning framework for mapping continuous-space inverse design problems into surrogate quadratic unconstrained binary optimization (QUBO) problems by employing a binary variational autoencoder (bVAE).Using the D-Wave Advantage hybrid sampler and simulated annealing as samplers, we demonstrate that by repeatedly sampling and retraining a surrogate QUBO (bVAE-QUBO), the samples generated by sampling and decoding the QUBO exhibit figures of merit exceeding those of its training set.Additionally, we demonstrate that the bVAE-QUBO framework is several times faster than previous methods with, at worst, a 1\% loss in quality. Building off of the latent optimization techniques from Chapter 4, in Chapter 5 we use an adversarial quantum autoencoder model (AQAM) to directly sample a Boltzmann distribution over neutral atoms using a quantum-enhanced Markov Chain Monte Carlo algorithm. We define the AMP loss function using an adversarial autoencoder approach and reparameterization trick which uses the AMP as a resource for training. Using 12-atom quantum simulations, we demonstrate that AQAM achieves a lower Renyi divergence with the ideal Boltzmann distribution and a larger spectral gap when compared to classical AMPs, thereby demonstrating a comparative advantage with AQAM over classical machine learning models.

•Jan 1, 2024•0 citations

Discrete generative diffusion models without stochastic differential equations: A tensor network approach

Luke Causer, Grant M. Rotskoff, Juan P. Garrahan

Diffusion models (DMs) are a class of generative machine learning methods that sample a target distribution by transforming samples of a trivial (often Gaussian) distribution using a learned stochastic differential equation. In standard DMs, this is done by learning a "score function" that reverses the effect of adding diffusive noise to the distribution of interest. Here we consider the generalisation of DMs to lattice systems with discrete degrees of freedom, and where noise is added via Markov chain jump dynamics. We show how to use tensor networks (TNs) to efficiently define and sample such "discrete diffusion models" (DDMs) without explicitly having to solve a stochastic differential equation. We show the following: (i) by parametrising the data and evolution operators as TNs, the denoising dynamics can be represented exactly; (ii) the auto-regressive nature of TNs allows to generate samples efficiently and without bias; (iii) for sampling Boltzmann-like distributions, TNs allow to construct an efficient learning scheme that integrates well with Monte Carlo. We illustrate this approach to study the equilibrium of two models with non-trivial thermodynamics, the d=1 constrained Fredkin chain and the d=2 Ising model.

arXiv:2407.11133•Physical review. E•Feb 7, 2025•8 citations
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).
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.
This study extends previous work on quantum-enhanced selection operators [Von Dollen et al.(2022)], where selection operators of evolutionary algorithms for classical black-box optimization are framed as quadratic binary optimization (QUBO) models, applied to black-box objective functions. We test our algorithms using both elitist and non-elitist strategies. First, we benchmark all heuristics over black-box, multi-modal functions. We find that for 94.4% of test cases, our method shows performance improvements with respect to fitness. Then, we similarly benchmark over the problem of hyperparameter selection for machine learning models, also a black-box optimization problem, and compare it to random search. We find that our method achieves some improvement with an average validation accuracy of 98.492% and highest ranking of 4.529412 (out of 5) when averaged across all test cases. We also apply our method towards neuroevolution, where we evolve weight spaces for small feedforward neural networks for learning tasks. In these settings, our method shows improved average reward in the reinforcement learning case and increased velocity in learning the XOR function.
As quantum machine learning continues to develop at a rapid pace, the importance of ensuring the robustness and efficiency of quantum algorithms cannot be overstated. Our research presents an analysis of quantum randomized smoothing, how data encoding and perturbation modeling approaches can be matched to achieve meaningful robustness certificates. By utilizing an innovative approach integrating Grover's algorithm, a quadratic sampling advantage over classical randomized smoothing is achieved. This strategy necessitates a basis state encoding, thus restricting the space of meaningful perturbations. We show how constrained k-distant Hamming weight perturbations are a suitable noise distribution here, and elucidate how they can be constructed on a quantum computer. The efficacy of the proposed framework is demonstrated on a time series classification task employing a Bag-of-Words pre-processing solution. The advantage of quadratic sample reduction is recovered especially in the regime with large number of samples. This may allow quantum computers to efficiently scale randomized smoothing to more complex tasks beyond the reach of classical methods.
Modern quantum machine learning (QML) methods involve the variational optimization of parameterized quantum circuits on training datasets, followed by predictions on testing datasets. Most state-of-the-art QML algorithms currently lack practical advantages due to their limited learning capabilities, especially in few-shot learning tasks. In this work, we propose three new frameworks employing quantum diffusion model (QDM) as a solution for the few-shot learning: label-guided generation inference (LGGI); label-guided denoising inference (LGDI); and label-guided noise addition inference (LGNAI). Experimental results demonstrate that our proposed algorithms significantly outperform existing methods.
My dissertation focuses on the analysis and development of algorithms for problems involving adversarial Markov processes (AMPs), including applications in hybrid quantum-classical generative machine learning, semiconductor authentication, and optimization.Markov processes are random processes whose state $\z_t \in S$ evolves to a future state $\z_{t + 1} \in S$ by sampling an adversarial distribution $p_\beta(\z_{t+1} \vert \z_t)$ that depends only on the current state $\z_t$ and a control parameter β\betaβ which is determined a priori. AMPs are an aggregated marginalization $q_\beta(\z_f) = \int_{\z_0} \Gamma_\beta(\z_f \vert \z_0)p(\z_0)$ of the Markov process $\Gamma_\beta = \sum_{\z_{f-1}}p_\beta(\z_{f} \vert \z_{f-1})...\sum_{\z_{1}}p_\beta(\z_{1} \vert \z_{0})$ coupled to a prior $p(\z_0)$. What makes the AMP adversarial is that our only control of Γβ\Gamma_\betaΓβ​ is through β\betaβ and we are tasked with choosing the optimal β\betaβ under some problem constraints. For example, in the second chapter of my dissertation, we optimally solve for β\betaβ in three package delivery AMPs where a dispatcher must construct a package delivery plan that maximizes the expected reward for a robot delivering packages across multiple epochs.Each package has an associated reward for delivery and a probabilistic risk of failure given by some adversary in the environment. %Our goal is to maximize the expected reward by choosing the optimal package delivery plan, i.e., AMP control parameter β\betaβ.We demonstrate how to use the structure of these AMPs to compute the optimal package delivery plan with the largest expected reward across both a finite and infinite number of epochs in O(K+nlog⁡n)O(K + n\log n)O(K+nlogn) time and O(n)O(n)O(n) time, respectively, where KKK is the number of epochs and nnn is the number of packages. However, not all AMP problems are based on choosing the optimal β\betaβ. Instead, β\betaβ can be adversarially chosen for us and we want to infer its value. For example, in Chapter 3, we infer the value of β\betaβ for a package authentication problem involving a mixed AMP where a manufacturer and a customer have to authenticate a semiconductor device using a physical unclonable function (PUF) based on the relative positions and radii of nanoparticles embedded on the packaging of a semiconductor device. Because the PUF's state space is intractable to infer β\betaβ explicitly, existing solutions used Hausdorff-inspired heuristics which work well for small perturbations in the nanoparticle positions.However, we show that under more difficult transformations, the Hausdorff heuristics can be reliably spoofed.To counteract this, we leverage a machine learning discriminator called RAPTOR to infer β\betaβ using attention networks.RAPTOR outperforms the Hausdorff, Procrustes, and average Hausdorff distance metrics, achieving a 40.6%40.6\%40.6%, 37.3%37.3\%37.3%, and 6.4%6.4\%6.4% total accuracy increase, respectively. In both Chapters 2 and 3, the AMPs are considered {\it adversaries} which we overcome using some algorithm.However, in Chapters 4 and 5, we demonstrate new learning techniques that use AMPs as a {\it resource} for generative machine learning. More specifically, the AMP parameter vector β\betaβ acts as an inverse temperature and/or energy function parameter for optimization and sampling using the AMPs.Specifically in Chapter 4, we demonstrate a quantum machine learning framework for mapping continuous-space inverse design problems into surrogate quadratic unconstrained binary optimization (QUBO) problems by employing a binary variational autoencoder (bVAE).Using the D-Wave Advantage hybrid sampler and simulated annealing as samplers, we demonstrate that by repeatedly sampling and retraining a surrogate QUBO (bVAE-QUBO), the samples generated by sampling and decoding the QUBO exhibit figures of merit exceeding those of its training set.Additionally, we demonstrate that the bVAE-QUBO framework is several times faster than previous methods with, at worst, a 1\% loss in quality. Building off of the latent optimization techniques from Chapter 4, in Chapter 5 we use an adversarial quantum autoencoder model (AQAM) to directly sample a Boltzmann distribution over neutral atoms using a quantum-enhanced Markov Chain Monte Carlo algorithm. We define the AMP loss function using an adversarial autoencoder approach and reparameterization trick which uses the AMP as a resource for training. Using 12-atom quantum simulations, we demonstrate that AQAM achieves a lower Renyi divergence with the ideal Boltzmann distribution and a larger spectral gap when compared to classical AMPs, thereby demonstrating a comparative advantage with AQAM over classical machine learning models.
Diffusion models (DMs) are a class of generative machine learning methods that sample a target distribution by transforming samples of a trivial (often Gaussian) distribution using a learned stochastic differential equation. In standard DMs, this is done by learning a "score function" that reverses the effect of adding diffusive noise to the distribution of interest. Here we consider the generalisation of DMs to lattice systems with discrete degrees of freedom, and where noise is added via Markov chain jump dynamics. We show how to use tensor networks (TNs) to efficiently define and sample such "discrete diffusion models" (DDMs) without explicitly having to solve a stochastic differential equation. We show the following: (i) by parametrising the data and evolution operators as TNs, the denoising dynamics can be represented exactly; (ii) the auto-regressive nature of TNs allows to generate samples efficiently and without bias; (iii) for sampling Boltzmann-like distributions, TNs allow to construct an efficient learning scheme that integrates well with Monte Carlo. We illustrate this approach to study the equilibrium of two models with non-trivial thermodynamics, the d=1 constrained Fredkin chain and the d=2 Ising model.