  Quantum algorithms are getting extremely popular due to their potential to
significantly outperform classical algorithms. Yet, applying quantum algorithms
to optimization problems meets challenges related to the efficiency of quantum
algorithms training, the shape of their cost landscape, the accuracy of their
output, and their ability to scale to large-size problems. Here, we present an
approximate gradient-based quantum algorithm for hardware-efficient circuits
with amplitude encoding. We show how simple linear constraints can be directly
incorporated into the circuit without additional modification of the objective
function with penalty terms. We employ numerical simulations to test it on
MaxCut problems with complete weighted graphs with thousands of nodes and run
the algorithm on a superconducting quantum processor. We find that for
unconstrained MaxCut problems with more than 1000 nodes, the hybrid approach
combining our algorithm with a classical solver called CPLEX can find a better
solution than CPLEX alone. This demonstrates that hybrid optimization is one of
the leading use cases for modern quantum devices.
