Towards Exponential Quantum Improvements in Solving Cardinality-Constrained Binary Optimization
This work addresses a fundamental computational problem in machine learning, finance, and scientific computing, offering incremental improvements in quantum algorithms for constrained optimization.
The paper tackles cardinality-constrained binary optimization by introducing a Grover-based quantum algorithm that exploits the structure of the feasible subspace, achieving an exponential reduction in Grover iterations compared to unstructured search, with specific query complexities such as O(√(binom(n,k)/M)) for quadratic objectives.
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\}^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 $ε+ δ$ using at most $ {O}\left(\sqrt{\binom{n}{k}}\frac{n^{6}k^{3/2} }{ \sqrt{M}ε^2 δ}\right)$ queries to a quadratic oracle, together with ${O}\left(\frac{n^{6}k^{3/2}}{ε^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.