Multiplicative weights update method

Cambridge University Press eBooks, pp. 299–304

Abstract

This chapter covers the multiplicative weights update method, a quantum algorithmic primitive for certain continuous optimization problems. This method is a framework for classical algorithms, but it can be made quantum by incorporating the quantum algorithmic primitive of Gibbs sampling and amplitude amplification. The framework can be applied to solve linear programs and related convex problems, or generalized to handle matrix-valued weights and used to solve semidefinite programs.

Authors 4

1. Sam McArdle
   Affiliation as printed

   AWS Center for Quantum Computing

2. Connor T. Hann
   Affiliation as printed

   AWS Center for Quantum Computing

3. Aleksander Kubica

   Yale University

   Affiliation as printed

   Yale University

4. Fernando G. S. L. Brandão
   Affiliation as printed

   AWS Center for Quantum Computing