{
  "id": "2510.01154",
  "version": "v1",
  "published": "2025-10-01T17:42:55.000Z",
  "updated": "2025-10-01T17:42:55.000Z",
  "title": "Advantage for Discrete Variational Quantum Algorithms in Circuit Recompilation",
  "authors": [
    "Oleksandr Kyriienko",
    "Chukwudubem Umeano",
    "Zoë Holmes"
  ],
  "comment": "9+5 pages, 11 figures",
  "categories": [
    "quant-ph",
    "cs.NE"
  ],
  "abstract": "The relative power of quantum algorithms, using an adaptive access to quantum devices, versus classical post-processing methods that rely only on an initial quantum data set, remains the subject of active debate. Here, we present evidence for an exponential separation between adaptive and non-adaptive strategies in a quantum circuit recompilation task. Our construction features compilation problems with loss landscapes for discrete optimization that are unimodal yet non-separable, a structure known in classical optimization to confer exponential advantages to adaptive search. Numerical experiments show that optimization can efficiently uncover hidden circuit structure operating in the regime of volume-law entanglement and high-magic, while non-adaptive approaches are seemingly limited to exhaustive search requiring exponential resources. These results indicate that adaptive access to quantum hardware provides a fundamental advantage.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2025-10-01T17:42:55.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "discrete variational quantum algorithms",
      "circuit recompilation",
      "search requiring exponential resources",
      "hidden circuit structure operating",
      "efficiently uncover hidden circuit structure"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 5,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}