A Subgradient Approach for Constrained Binary Optimization via Quantum Adiabatic Evolution
By Sahar Karimi & Pooya Ronagh
An earlier work proposes a method for solving the Lagrangian dual of a constrained binary quadratic programming problem via quantum adiabatic evolution using an outer approximation method. This should be an efficient prescription for solving the Lagrangian dual problem in the presence of an ideally noise-free quantum adiabatic system. However, current implementations of quantum annealing systems demand methods that are efficient at handling possible sources of noise. In this paper, we consider a subgradient method for finding an optimal primal-dual pair for the Lagrangian dual of a constrained binary polynomial programming problem. We then study the quadratic stable set (QSS) problem as a case study. We see that this method applied to the QSS problem can be viewed as an instance-dependent penalty-term approach that avoids large penalty coefficients. Finally, we report our experimental results of using the D-Wave 2X quantum annealer and conclude that our approach helps this quantum processor to succeed more often in solving these problems compared to the usual penalty-term approaches.
Presented at: Canadian Operational Research Society (CORS) 58th Annual Conference 2016
Most Recent Papers
Variationally Scheduled Quantum Simulation
By Shunji Matsuura, Samantha Buck, Valentin Senicourt, & Arman Zaribafiyan Eigenstate preparation is ubiquitous in quantum computing, and a standard approach for generating the lowest-energy states of a given system is by employing adiabatic state preparation...
Scaling Up Electronic Structure Calculations on Quantum Computers: The Frozen Natural Orbital Based Method of Increments
By Prakash Verma, Lee Huntington, Marc Coons, Yukio Kawashima, Takeshi Yamazaki, & Arman Zaribafiyan Quantum computing is a new computing paradigm that holds great promise for the efficient simulation of quantum mechanical systems. However, the hardware envelope...
Effects of Setting the Temperatures in the Parallel Tempering Monte Carlo Algorithm
By Ignacio Rozada, Maliheh Aramon, Jonathan Machta, & Helmut G. Katzgraber Parallel tempering Monte Carlo has proven to be an efficient method in optimization and sampling applications. Having an optimized temperature set enhances the efficiency of the algorithm...
Adiabatic Quantum Kitchen Sinks for Learning Kernels Using Randomized Features
By Moslem Noori, Seyed Shakib Vedaie, Inderpreet Singh, Daniel Crawford, Jaspreet S. Oberoi, Barry C. Sanders, & Ehsan Zahedinejad Quantum information processing is likely to have far-reaching impact in the field of artificial intelligence. While the race to build...
A Quantum Annealing-Based Approach to Extreme Clustering
By Tim Jaschek, Marko Bucyk, & Jaspreet S. Oberoi Clustering, or grouping, dataset elements based on similarity can be used not only to classify a dataset into a few categories, but also to approximate it by a relatively large number of representative elements. In...