Adversarial Markov Processes for Quantum Generative Machine Learning and Classical Optimization
Blake Anthony Wilson
Abstract
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.