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
β 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
Γβ is through
β and we are tasked with choosing the optimal
β under some problem constraints. For example, in the second chapter of my dissertation, we optimally solve for
β 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
β.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+nlogn) 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
β. Instead,
β can be adversarially chosen for us and we want to infer its value. For example, in Chapter 3, we infer the value of
β 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
β 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
β 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
β 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.