Towards Exponential Quantum Improvements in Solving Cardinality-Constrained Binary Optimization

Abstract

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{\left(\genfrac{}{}{0ex}{}{n}{k}\right)}{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{\}}^n$. 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 $ϵ+\delta$ using at most $O\left(\sqrt{\left(\genfrac{}{}{0ex}{}{n}{k}\right)}\frac{n^6{k}^{3/2}}{\sqrt{M}{ϵ}^2\delta }\right)$ queries to a quadratic oracle, together with $O\left(\frac{n^6{k}^{3/2}}{{ϵ}^2\delta }\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.