Quantum and Classical Algorithms for Approximate Submodular Function Minimization. (arXiv:1907.05378v1 [cs.DS])

Submodular functions are set functions mapping every subset of some ground
set of size $n$ into the real numbers and satisfying the diminishing returns
property. Submodular minimization is an important field in discrete
optimization theory due to its relevance for various branches of mathematics,
computer science and economics. The currently fastest strongly polynomial
algorithm for exact minimization [LSW15] runs in time $\widetilde{O}(n^3 \cdot
\mathrm{EO} + n^4)$ where $\mathrm{EO}$ denotes the cost to evaluate the
function on any set. For functions with range $[-1,1]$, the best
$\epsilon$-additive approximation algorithm [CLSW17] runs in time
$\widetilde{O}(n^{5/3}/\epsilon^{2} \cdot \mathrm{EO})$. In this paper we
present a classical and a quantum algorithm for approximate submodular
minimization. Our classical result improves on the algorithm of [CLSW17] and
runs in time $\widetilde{O}(n^{3/2}/\epsilon^2 \cdot \mathrm{EO})$. Our quantum
algorithm is, up to our knowledge, the first attempt to use quantum computing
for submodular optimization. The algorithm runs in time
$\widetilde{O}(n^{5/4}/\epsilon^{5/2} \cdot \log(1/\epsilon) \cdot
\mathrm{EO})$. The main ingredient of the quantum result is a new method for
sampling with high probability $T$ independent elements from any discrete
probability distribution of support size $n$ in time $O(\sqrt{Tn})$. Previous
quantum algorithms for this problem were of complexity $O(T\sqrt{n})$.

Article web page: