Solving Constrained Quadratic Binary Problems via Quantum Adiabatic Evolution

By Pooya Ronagh, Brad Woods, & Ehsan Iranmanesh

Quantum adiabatic evolution is perceived as useful for binary quadratic programming problems that are a priori unconstrained. For constrained problems, it is a common practice to relax linear equality constraints as penalty terms in the objective function. However, there has not yet been proposed a method for efficiently dealing with inequality constraints using the quantum adiabatic approach. In this paper, we give a method for solving the Lagrangian dual of a binary quadratic programming (BQP) problem in the presence of inequality constraints and employ this procedure within a branch-and-bound framework for constrained BQP (CBQP) problems.

Journal reference: Quantum Information & Computation 16(11&12): 1029-1047 (2016)

Presented at: The Fields Institute for Research in Mathematical Sciences, Quantum Optimization Workshop 2014

PDF arXiv preprint

← Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer Homology Computation of Large Point Clouds Using Quantum Annealing →

Most Recent Papers

Variationally Scheduled Quantum Simulation

Mar 22, 2020

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

Feb 18, 2020

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

Nov 8, 2019

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

Sep 17, 2019

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

Sep 11, 2019

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