Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: A quantum algorithm to count weighted ground states of classical spin
  Hamiltonians   Ground state counting plays an important role in several applications in
science and engineering, from estimating residual entropy in physical systems,
to bounding engineering reliability and solving combinatorial counting
problems. While quantum algorithms such as adiabatic quantum optimization (AQO)
and quantum approximate optimization (QAOA) can minimize Hamiltonians, they are
inadequate for counting ground states. We modify AQO and QAOA to count the
ground states of arbitrary classical spin Hamiltonians, including counting
ground states with arbitrary nonnegative weights attached to them. As a
concrete example, we show how our method can be used to count the weighted
fraction of edge covers on graphs, with user-specified confidence on the
relative error of the weighted count, in the asymptotic limit of large graphs.
We find the asymptotic computational time complexity of our algorithms, via
analytical predictions for AQO and numerical calculations for QAOA, and compare
with the classical optimal Monte Carlo algorithm (OMCS), as well as a modified
Grover's algorithm. We show that for large problem instances with small weights
on the ground states, AQO does not have a quantum speedup over OMCS for a fixed
error and confidence, but QAOA has a sub-quadratic speedup on a broad class of
numerically simulated problems. Our work is an important step in approaching
general ground-state counting problems beyond those that can be solved with
Grover's algorithm. It offers algorithms that can employ noisy
intermediate-scale quantum devices for solving ground state counting problems
on small instances, which can help in identifying more problem classes with
quantum speedups.

26
The categories of this paper are: bayes-an
24
The categories of this paper are: dg-ga
30
The categories of this paper are: q-alg
11
The categories of this paper are: hep-lat
23
The categories of this paper are: solv-int
36
The categories of this paper are: cmp-lg
6
The categories of this paper are: astro-ph
25
The categories of this paper are: patt-sol
14
The categories of this paper are: math-ph
32
The categories of this paper are: atom-ph
1
The categories of this paper are: cs
27
The categories of this paper are: comp-gas
4
The categories of this paper are: cond-mat
0
The categories of this paper are: hep-ph
17
The categories of this paper are: q-fin
2
The categories of this paper are: math