A Quantum Version of the Multiplicative Weights Algorithm

Abstract

One of the biggest research questions that has been asked in online learning with experts is how to make decisions per round to attain sufficiently small regret and minimize loss in hindsight. The multiplicative weights (MW) algorithm in particular has been one of the most general yet simple meta-algorithms applicable to many disciplines that involve online settings for decision-making, and it has a regret bound of \(\mathcal{O}(\sqrt{T \log N})\) over a time period of \(T\) iterations with \(N\) experts. Furthermore, there are several variants of MW that have important uses, such as in the online learning setting for optimizable experts. Assuming that no parallelization is afforded by computer implementation or architecture, all of these algorithms have a tight runtime bound of \(\mathcal{O}(N)\) per iteration. However, this tightness is under the premise that computations are being performed on a classical computer. But on a quantum computer, better runtime bounds could possibly be attainable. Therefore, we examine the computational power of quantum algorithms in online learning and ask the following question:

Given the theoretical capabilities of a quantum computer, is it possible to hypothetically implement the MW algorithm and its variants in runtime better than \(\mathcal{O}(N)\) per iteration?

In this paper, we primarily utilize a property known as quantum superposition, which allows a quantum state to represent a combination of all possible computational basis states, to approach the question above. We conclude that there exists a quantum analog of the mixed multiplicative weight algorithm that has a regret bound equivalent in expectation to the classical bound up to a constant multiplicative factor with high probability in runtime \(\mathcal{O}(\sqrt{N})\) per round and space complexity \(\mathcal{O}(\log_2 N)\). This improvement shows promise of similar results in other machine learning algorithms, although it is important to understand the tradeoff between these speedups and assumptions made in the quantum space.