Methods, systems, and apparatus for solving cost optimization problems. In one aspect, a method includes receiving data representing a bill of materials (BOM) optimization problem, the BOM optimization problem comprising a task of determining a BOM recommendation that satisfies one or more constraints, wherein each constraint comprises one or more constraint variables and a constraint constant; generating, based on the data representing the BOM optimization problem, a quadratic unconstrained binary optimization (QUBO) formulation, wherein the QUBO formulation comprises i) for each constraint variable in the one or more constraints, a binary representation of the constraint variable and ii) a first parameter that depends on a difference between a respective constraint constant and the binary representations of the constraint variables; and obtaining data representing a solution to the BOM optimization problem from a quantum computing resource.