The Multiplicative Weights Method in Quantum Computing

Abstract

The multiplicative weights method is a meta-algorithm: a general template for a large variety of algorithms. Algorithms with this structure have been independently developed across many fields. We explore the usage of the multiplicative weights method in machine learning, linear programs and semidefinite programs, as well as how these algorithms can be improved upon using quantum computers. In machine learning, the multiplicative weights method is used for boosting algorithms, which can create a strong learner through repeated calls of a weak learner. Linear programs can be approximately solved by first converting them to zero-sum games and then running two simultaneous instances of the multiplicative weights method. We developed an algorithm for solving semidefinite programs with a similar approach, but it is outperformed by existing algorithms.