  Constrained combinatorial optimization problems, which are ubiquitous in
industry, can be solved by quantum algorithms such as quantum annealing (QA)
and the quantum approximate optimization algorithm (QAOA). In these quantum
algorithms, constraints are typically implemented with quadratic penalty
functions. This penalty method can introduce large energy scales and make
interaction graphs much more dense. These effects can result in worse
performance of quantum optimization, particularly on near-term devices that
have sparse hardware graphs and other physical limitations. In this work, we
consider linear Ising penalty functions, which are applied with local fields in
the Ising model, as an alternative method for implementing constraints that
makes more efficient use of physical resources. We study the behaviour of the
penalty method in the context of quantum optimization for customer data science
problems. Our theoretical analysis and numerical simulations of QA and the QAOA
indicate that this penalty method can lead to better performance in quantum
optimization than the quadratic method. However, the linear Ising penalty
method is not suitable for all problems as it cannot always exactly implement
the desired constraint. In cases where the linear method is not successful in
implementing all constraints, we propose that schemes involving both quadratic
and linear Ising penalties can be effective.
