{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreih4rnbekw7i7o5yam5h3sozmxow6rmxq3nx5jnissqx6sb6kdnmpe",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mh7zi4pxurh2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.14744v1",
  "publishedAt": "2026-03-17T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Haomu Yuan",
    "Hanqing Wu",
    "Kuan-Cheng Chen",
    "Bin Cheng",
    "Crispin H. W. Barnes"
  ],
  "textContent": "**Authors:** Haomu Yuan, Hanqing Wu, Kuan-Cheng Chen, Bin Cheng, Crispin H. W. Barnes\n\nCardinality-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.",
  "title": "Towards Exponential Quantum Improvements in Solving Cardinality-Constrained Binary Optimization"
}