{"id":"arxiv/2603.14744","url":"https://arxiv.org/abs/2603.14744","tags":["quant-ph","cs.CC","math.OC","math.ST"],"score":0,"title":"Towards Exponential Quantum Improvements in Solving Cardinality-Constrained Binary Optimization","domain":"quant-ph","source":"arxiv","authors":["Haomu Yuan","Hanqing Wu","Kuan-Cheng Chen","Bin Cheng","Crispin H. W. Barnes"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-03-16","reactions":{}}