Quantum algorithms for hedging and the learning of Ising models

Abstract

A paradigmatic algorithm for online learning is the Hedge algorithm by Freund and Schapire. An allocation into different strategies is chosen for multiple rounds and each round incurs corresponding losses for each strategy. The algorithm obtains a favorable guarantee for the total losses even in an adversarial situation. This work presents quantum algorithms for such online learning in an oracular setting. For T time steps and N strategies, we exhibit run times of about Opoly(T)N for estimating the losses and for betting on individual strategies by sampling. In addition, we discuss a quantum analog of the Sparsitron, a machine learning algorithm based on the Hedge algorithm. The quantum algorithm inherits the provable learning guarantees from the classical algorithm and exhibits polynomial speedups. The speedups may find relevance in finance, for example, for hedging risks, and machine learning, for example, for learning generalized linear models or Ising models.

Publication
Physical Review A
Xin Wang
Xin Wang
Associate Professor

The main focus of my research is to better understand the limits of information processing with quantum systems and the power of quantum artificial intelligence.