  Discrete combinatorial optimization consists in finding the optimal
configuration that minimizes a given discrete objective function. An
interpretation of such a function as the energy of a classical system allows us
to reduce the optimization problem into the preparation of a low-temperature
thermal state of the system. Motivated by the quantum annealing method, we
present three strategies to prepare the low-temperature state that exploit
quantum mechanics in remarkable ways. We focus on implementations without
uncontrolled errors induced by the environment. This allows us to rigorously
prove a quantum advantage. The first strategy uses a classical-to-quantum
mapping, where the equilibrium properties of a classical system in $d$ spatial
dimensions can be determined from the ground state properties of a quantum
system also in $d$ spatial dimensions. We show how such a ground state can be
prepared by means of quantum annealing, including quantum adiabatic evolutions.
This mapping also allows us to unveil some fundamental relations between
simulated and quantum annealing. The second strategy builds upon the first one
and introduces a technique called spectral gap amplification to reduce the time
required to prepare the same quantum state adiabatically. If implemented on a
quantum device that exploits quantum coherence, this strategy leads to a
quadratic improvement in complexity over the well-known bound of the classical
simulated annealing method. The third strategy is not purely adiabatic;
instead, it exploits diabatic processes between the low-energy states of the
corresponding quantum system. For some problems it results in an exponential
speedup (in the oracle model) over the best classical algorithms.
