  Adiabatic quantum optimization is a procedure to solve a vast class of
optimization problems by slowly changing the Hamiltonian of a quantum system.
The evolution time necessary for the algorithm to be successful scales
inversely with the minimum energy gap encountered during the dynamics.
Unfortunately, the direct calculation of the gap is strongly limited by the
exponential growth in the dimensionality of the Hilbert space associated to the
quantum system. Although many special-purpose methods have been devised to
reduce the effective dimensionality, they are strongly limited to particular
classes of problems with evident symmetries. Moreover, little is known about
the computational power of adiabatic quantum optimizers in real-world
conditions. Here, we propose and implement a general purposes reduction method
that does not rely on any explicit symmetry and which requires, under certain
general conditions, only a polynomial amount of classical resources. Thanks to
this method, we are able to analyze the performance of "non-ideal" quantum
adiabatic optimizers to solve the well-known Grover problem, namely the search
of target entries in an unsorted database, in the presence of discrete local
defects. In this case, we show that adiabatic quantum optimization, even if
affected by random noise, is still potentially faster than any classical
algorithm.
