Lower bounds on minimization problems are essential for convergence of both branching-based and iterative solution methods for optimization problems. They are also required for evaluating the quality of feasible solutions by providing conservative optimality gaps. We provide an analytical lower bound for a class of quadratic optimization problems with binary decision variables. In contrast to traditional lower bounds typically obtained from solving relaxed optimization models, our lower bound is analytical and does not require a numerical solution of any mathematical optimization model. This especially provides value for instances of our optimization model that are computationally difficult to even generate, before being handed to a solver for a numerical solution. Further, we propose a greedy heuristic to determine a feasible solution that, in turn, allows us to evaluate the quality of this lower bound. Numerical results for instances that previously could not be generated in over five hours demonstrate an optimality gap of under 11% in less than a minute using our bounds.