<p>Data scarcity remains a central challenge in materials discovery, where finding meaningful descriptors and tuning models for generalization is critical but inherently a discrete optimization problem prone to multiple local minima confounding the true optimal state. Classical methods often become trapped in these minima, while quantum annealing can escape them via quantum fluctuations, including tunneling, which overcome narrow energy barriers. We present a quantum-assisted machine-learning (QaML) framework that employs quantum annealing to address these combinatorial-optimization challenges through feature selection, support-vector training formulated in QUBO form for classification and regression, and a new QUBO-based neural-network pruning formulation. Recursive batching enables quantum annealing to manage large feature spaces beyond current qubit limits, while quantum-pruned networks exhibit superior generalization over classical methods, suggesting that quantum annealing preferentially samples flatter, more stable regions of the loss landscape. Applied to high-entropy alloys (HEAs), a data-limited but compositionally complex testbed, the framework integrates models for the fracture-strain classification and yield-strength regression under physics-based constraints. The framework identified and experimentally validated Al8Cr38Fe50Mn2Ti2 (at.%), a single-phase BCC alloy exhibiting a 0.2% yield strength of 568 MPa, greater than 40% compressive strain without fracture, and a critical current density in reducing acid nearly an order of magnitude lower than 304 stainless steel. These results establish QA as a practical route to overcome classical optimization limits and accelerate materials discovery.</p>