We propose a novel quantum computing strategy for parallel MCMC algorithms that generate multiple proposals at each step. This strategy makes parallel MCMC amenable to quantum parallelization by using the Gumbel-max trick to turn the generalized accept-reject step into a discrete optimization problem. This allows us to embed target density evaluations within a well-known extension of Grover's quantum search algorithm. Letting $P$ denote the number of proposals in a single MCMC iteration, the combined strategy reduces the number of target evaluations required from $\mathcal{O}(P)$ to $\mathcal{O}(P^{1/2})$. In the following, we review both the rudiments of quantum computing and the Gumbel-max trick in order to elucidate their combination for as wide a readership as possible.
相關內容
Particle smoothers are SMC (Sequential Monte Carlo) algorithms designed to approximate the joint distribution of the states given observations from a state-space model. We propose dSMC (de-Sequentialized Monte Carlo), a new particle smoother that is able to process $T$ observations in $\mathcal{O}(\log T)$ time on parallel architecture. This compares favourably with standard particle smoothers, the complexity of which is linear in $T$. We derive $\mathcal{L}_p$ convergence results for dSMC, with an explicit upper bound, polynomial in $T$. We then discuss how to reduce the variance of the smoothing estimates computed by dSMC by (i) designing good proposal distributions for sampling the particles at the initialization of the algorithm, as well as by (ii) using lazy resampling to increase the number of particles used in dSMC. Finally, we design a particle Gibbs sampler based on dSMC, which is able to perform parameter inference in a state-space model at a $\mathcal{O}(\log(T))$ cost on parallel hardware.
This work presents the first study of using the popular Monte Carlo Tree Search (MCTS) method combined with dedicated heuristics for solving the Weighted Vertex Coloring Problem. Starting with the basic MCTS algorithm, we gradually introduce a number of algorithmic variants where MCTS is extended by various simulation strategies including greedy and local search heuristics. We conduct experiments on well-known benchmark instances to assess the value of each studied combination. We also provide empirical evidence to shed light on the advantages and limits of each strategy.
Quantum Annealing (QA) is a computational framework where a quantum system's continuous evolution is used to find the global minimum of an objective function over an unstructured search space. It can be seen as a general metaheuristic for optimization problems, including NP-hard ones if we allow an exponentially large running time. While QA is widely studied from a heuristic point of view, little is known about theoretical guarantees on the quality of the solutions obtained in polynomial time. In this paper we use a technique borrowed from theoretical physics, the Lieb-Robinson (LR) bound, and develop new tools proving that short, constant time quantum annealing guarantees constant factor approximations ratios for some optimization problems when restricted to bounded degree graphs. Informally, on bounded degree graphs the LR bound allows us to retrieve a (relaxed) locality argument, through which the approximation ratio can be deduced by studying subgraphs of bounded radius. We illustrate our tools on problems MaxCut and Maximum Independent Set for cubic graphs, providing explicit approximation ratios and the runtimes needed to obtain them. Our results are of similar flavor to the well-known ones obtained in the different but related QAOA (quantum optimization algorithms) framework. Eventually, we discuss theoretical and experimental arguments for further improvements.
For $R\triangleq Mat_{m}(\mathbb{F})$, the ring of all the $m\times m$ matrices over the finite field $\mathbb{F}$ with $|\mathbb{F}|=q$, and the left $R$-module $A\triangleq Mat_{m,k}(\mathbb{F})$ with $m+1\leqslant k$, by deriving the minimal length of solutions of the related isometry equation, Dyshko has proved in \cite{3,4} that the minimal code length $n$ for $A^{n}$ not to satisfy the MacWilliams extension property with respect to Hamming weight is equal to $\prod_{i=1}^{m}(q^{i}+1)$. In this paper, using the M\"{o}bius functions, we derive the minimal length of nontrivial solutions of the isometry equation with respect to a finite lattice. For the finite vector space $\mathbf{H}\triangleq\prod_{i\in\Omega}\mathbb{F}^{k_{i}}$, a poset $\mathbf{P}=(\Omega,\preccurlyeq_{\mathbf{P}})$ and a map $\omega:\Omega\longrightarrow\mathbb{R}^{+}$ give rise to the $(\mathbf{P},\omega)$-weight on $\mathbf{H}$, which has been proposed by Hyun, Kim and Park in \cite{18}. For such a weight, we study the relations between the MacWilliams extension property and other properties including admitting MacWilliams identity, Fourier-reflexivity of involved partitions and Unique Decomposition Property defined for $(\mathbf{P},\omega)$. We give necessary and sufficient conditions for $\mathbf{H}$ to satisfy the MacWilliams extension property with the additional assumption that either $\mathbf{P}$ is hierarchical or $\omega$ is identically $1$, i.e., $(\mathbf{P},\omega)$-weight coincides with $\mathbf{P}$-weight, which further allow us to partly answer a conjecture proposed by Machado and Firer in \cite{22}.
Quantum Variational Circuits (QVCs) are often claimed as one of the most potent uses of both near term and long term quantum hardware. The standard approaches to optimizing these circuits rely on a classical system to compute the new parameters at every optimization step. However, this process can be extremely challenging both in terms of navigating the exponentially scaling complex Hilbert space, barren plateaus, and the noise present in all foreseeable quantum hardware. Although a variety of optimization algorithms are employed in practice, there is often a lack of theoretical or empirical motivations for this choice. To this end we empirically evaluate the potential of many common gradient and gradient free optimizers on a variety of optimization tasks. These tasks include both classical and quantum data based optimization routines. Our evaluations were conducted in both noise free and noisy simulations. The large number of problems and optimizers yields strong empirical guidance for choosing optimizers for QVCs that is currently lacking.
Controllable generation is one of the key requirements for successful adoption of deep generative models in real-world applications, but it still remains as a great challenge. In particular, the compositional ability to generate novel concept combinations is out of reach for most current models. In this work, we use energy-based models (EBMs) to handle compositional generation over a set of attributes. To make them scalable to high-resolution image generation, we introduce an EBM in the latent space of a pre-trained generative model such as StyleGAN. We propose a novel EBM formulation representing the joint distribution of data and attributes together, and we show how sampling from it is formulated as solving an ordinary differential equation (ODE). Given a pre-trained generator, all we need for controllable generation is to train an attribute classifier. Sampling with ODEs is done efficiently in the latent space and is robust to hyperparameters. Thus, our method is simple, fast to train, and efficient to sample. Experimental results show that our method outperforms the state-of-the-art in both conditional sampling and sequential editing. In compositional generation, our method excels at zero-shot generation of unseen attribute combinations. Also, by composing energy functions with logical operators, this work is the first to achieve such compositionality in generating photo-realistic images of resolution 1024x1024.
Quantum hardware and quantum-inspired algorithms are becoming increasingly popular for combinatorial optimization. However, these algorithms may require careful hyperparameter tuning for each problem instance. We use a reinforcement learning agent in conjunction with a quantum-inspired algorithm to solve the Ising energy minimization problem, which is equivalent to the Maximum Cut problem. The agent controls the algorithm by tuning one of its parameters with the goal of improving recently seen solutions. We propose a new Rescaled Ranked Reward (R3) method that enables stable single-player version of self-play training that helps the agent to escape local optima. The training on any problem instance can be accelerated by applying transfer learning from an agent trained on randomly generated problems. Our approach allows sampling high-quality solutions to the Ising problem with high probability and outperforms both baseline heuristics and a black-box hyperparameter optimization approach.
We introduce a new family of deep neural network models. Instead of specifying a discrete sequence of hidden layers, we parameterize the derivative of the hidden state using a neural network. The output of the network is computed using a black-box differential equation solver. These continuous-depth models have constant memory cost, adapt their evaluation strategy to each input, and can explicitly trade numerical precision for speed. We demonstrate these properties in continuous-depth residual networks and continuous-time latent variable models. We also construct continuous normalizing flows, a generative model that can train by maximum likelihood, without partitioning or ordering the data dimensions. For training, we show how to scalably backpropagate through any ODE solver, without access to its internal operations. This allows end-to-end training of ODEs within larger models.
We consider the exploration-exploitation trade-off in reinforcement learning and we show that an agent imbued with a risk-seeking utility function is able to explore efficiently, as measured by regret. The parameter that controls how risk-seeking the agent is can be optimized exactly, or annealed according to a schedule. We call the resulting algorithm K-learning and show that the corresponding K-values are optimistic for the expected Q-values at each state-action pair. The K-values induce a natural Boltzmann exploration policy for which the `temperature' parameter is equal to the risk-seeking parameter. This policy achieves an expected regret bound of $\tilde O(L^{3/2} \sqrt{S A T})$, where $L$ is the time horizon, $S$ is the number of states, $A$ is the number of actions, and $T$ is the total number of elapsed time-steps. This bound is only a factor of $L$ larger than the established lower bound. K-learning can be interpreted as mirror descent in the policy space, and it is similar to other well-known methods in the literature, including Q-learning, soft-Q-learning, and maximum entropy policy gradient, and is closely related to optimism and count based exploration methods. K-learning is simple to implement, as it only requires adding a bonus to the reward at each state-action and then solving a Bellman equation. We conclude with a numerical example demonstrating that K-learning is competitive with other state-of-the-art algorithms in practice.
Quantum machine learning is expected to be one of the first potential general-purpose applications of near-term quantum devices. A major recent breakthrough in classical machine learning is the notion of generative adversarial training, where the gradients of a discriminator model are used to train a separate generative model. In this work and a companion paper, we extend adversarial training to the quantum domain and show how to construct generative adversarial networks using quantum circuits. Furthermore, we also show how to compute gradients -- a key element in generative adversarial network training -- using another quantum circuit. We give an example of a simple practical circuit ansatz to parametrize quantum machine learning models and perform a simple numerical experiment to demonstrate that quantum generative adversarial networks can be trained successfully.
小貼士
登錄享
相關主題
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191