We systematically investigate the potentials of improving the lower bound obtained with a linear relaxation of the Quadratic Unconstrained Binary Optimization problem by integrating curvature information from an accompanying quadratic convex underestimator via gradient inequalities. On the one hand, we exemplify to which extent this hybrid approach may provide a lower bound that is strictly stronger than the maximum of the respective linear and convex quadratic minima standalone. On the other, we prove that a strict improvement is impossible for the subclass of instances obtained from the Maximum Cut problem when choosing the underestimator and relaxation in a theoretically and practically relevant way. In addition, we address how the most common linear relaxation can be strengthened with the well-known triangle inequalities using only linearization variables matching the non-zero pattern of the original cost matrix.