A Distributional Approach to Quantum Approximate Optimization Algorithms*

We describe a distributional approach to solving combinatoric optimization problems using quantum approximate optimization algorithms (QAOA). The framework of QAOA was developed for global optimization of combinatorial cost functions. However, in many problems of interest, families of solutions near the optima are needed to robustly solve problems in resource allocation, multiple target tracking, and multi-agent control. The single-point optimal allocation may be brittle to changing situations and unable to provide alternative solutions without a full ab initio re-analysis which may result in unacceptable time delay; some "slack" is desirable in practice. In our approach, we use QAOA to sample many different solutions to a combinatorial optimization problem that lie in a low energy band of the associated cost Hamiltonian. We view the repeated runs of QAOA as generating a probability mass function (PMF) on basis states, such that quantum measurement samples this PMF, and the full state is reconstructed tomographically. Central to our approach is identifying a distributional metric to optimize rather than a point estimator. Distributional metrics will be discussed as well as applications to Bayesian filtering and resource allocation problems.