Towards Exponential Quantum Improvements in Solving Cardinality-Constrained Binary Optimization

Cardinality-constrained binary optimization is a fundamental computational primitive with broad applications in machine learning, finance, and scientific computing. In this work, we introduce a Grover-based quantum algorithm that exploits the structure of the fixed-cardinality feasible subspace under a natural promise on solution existence. For quadratic objectives, our approach achieves {O}left\(sqrt{frac{binom{n}{k}}{M}}right\) Grover rotations for any fixed cardinality k and degeneracy of the optima M, yielding an exponential reduction in the number of Grover iterations compared with unstructured search over \{0,1\}ⁿ. Building on this result, we develop a hybrid classical--quantum framework based on the alternating direction method of multipliers (ADMM) algorithm. The proposed framework is guaranteed to output an ε-approximate solution with a consistency tolerance ε+ δ using at most {O}left\(sqrt{binom{n}{k}}frac{n⁶k^3/2 }{ sqrt{M}ε² δ}right\) queries to a quadratic oracle, together with {O}left\(frac{n⁶k^3/2}{ε²δ}right\) classical overhead. Overall, our method suggests a practical use of quantum resources and demonstrates an exponential improvements over existing Grover-based approaches in certain parameter regimes, thereby paving the way toward quantum advantage in constrained binary optimization.