Essec\Faculty\Model\Contribution {#2220
  #_index: "academ_contributions"
  #_id: "15901"
  #_source: array:26 [
    "id" => "15901"
    "slug" => "15901-alleviating-the-quantum-big-m-problem"
    "yearMonth" => "2025-12"
    "year" => "2025"
    "title" => "Alleviating the quantum Big-M problem"
    "description" => "ALESSANDRONI, E., RAMOS-CALDERER, S., ROTH, I., TRAVERSI, E. et AOLITA, L. (2025). Alleviating the quantum Big-M problem. <i>npj Quantum Information</i>, 11(1), pp. Art. 125."
    "authors" => array:5 [
      0 => array:3 [
        "name" => "TRAVERSI Emiliano"
        "bid" => "B00820417"
        "slug" => "traversi-emiliano"
      ]
      1 => array:1 [
        "name" => "Alessandroni Edoardo"
      ]
      2 => array:1 [
        "name" => "Ramos-Calderer Sergi"
      ]
      3 => array:1 [
        "name" => "Roth Ingo"
      ]
      4 => array:1 [
        "name" => "Aolita Leandro"
      ]
    ]
    "ouvrage" => ""
    "keywords" => array:3 [
      0 => "Quantum Optimization"
      1 => "Big-M Problem"
      2 => "Combinatorial Optimization"
    ]
    "updatedAt" => "2025-09-03 10:35:04"
    "publicationUrl" => "https://doi.org/10.1038/s41534-025-01067-0"
    "publicationInfo" => array:3 [
      "pages" => "Art. 125"
      "volume" => "11"
      "number" => "1"
    ]
    "type" => array:2 [
      "fr" => "Articles"
      "en" => "Journal articles"
    ]
    "support_type" => array:2 [
      "fr" => "Revue scientifique"
      "en" => "Scientific journal"
    ]
    "countries" => array:2 [
      "fr" => null
      "en" => null
    ]
    "abstract" => array:2 [
      "fr" => "A major obstacle for quantum optimizers is the reformulation of constraints as a quadratic unconstrained binary optimization (QUBO). Current QUBO translators exaggerate the weight M of the penalty terms. Classically known as the “Big-M” problem, the issue becomes even more daunting for quantum solvers, since it affects the physical energy scale. We take a systematic, encompassing look at the quantum big-M problem, revealing NP-hardness in finding the optimal M and establishing bounds on the Hamiltonian spectral gap Δ as a function of the weight M, inversely related to the expected run-time of quantum solvers. We propose a practical translation algorithm, based on SDP relaxation, that outperforms previous methods in numerical benchmarks. Our algorithm gives values of Δ orders of magnitude greater, e.g. for portfolio optimization instances. Solving such instances with an adiabatic algorithm on 6-qubits of an IonQ device, we observe significant advantages in time to solution and average solution quality. Our findings are relevant to quantum and quantum-inspired solvers alike."
      "en" => "A major obstacle for quantum optimizers is the reformulation of constraints as a quadratic unconstrained binary optimization (QUBO). Current QUBO translators exaggerate the weight M of the penalty terms. Classically known as the “Big-M” problem, the issue becomes even more daunting for quantum solvers, since it affects the physical energy scale. We take a systematic, encompassing look at the quantum big-M problem, revealing NP-hardness in finding the optimal M and establishing bounds on the Hamiltonian spectral gap Δ as a function of the weight M, inversely related to the expected run-time of quantum solvers. We propose a practical translation algorithm, based on SDP relaxation, that outperforms previous methods in numerical benchmarks. Our algorithm gives values of Δ orders of magnitude greater, e.g. for portfolio optimization instances. Solving such instances with an adiabatic algorithm on 6-qubits of an IonQ device, we observe significant advantages in time to solution and average solution quality. Our findings are relevant to quantum and quantum-inspired solvers alike."
    ]
    "authors_fields" => array:2 [
      "fr" => "Systèmes d'Information, Data Analytics et Opérations"
      "en" => "Information Systems, Data Analytics and Operations"
    ]
    "indexedAt" => "2025-12-06T07:21:43.000Z"
    "docTitle" => "Alleviating the quantum Big-M problem"
    "docSurtitle" => "Journal articles"
    "authorNames" => "<a href="/cv/traversi-emiliano">TRAVERSI Emiliano</a>, Alessandroni Edoardo, Ramos-Calderer Sergi, Roth Ingo, Aolita Leandro"
    "docDescription" => "<span class="document-property-authors">TRAVERSI Emiliano, Alessandroni Edoardo, Ramos-Calderer Sergi, Roth Ingo, Aolita Leandro</span><br><span class="document-property-authors_fields">Information Systems, Data Analytics and Operations</span> | <span class="document-property-year">2025</span>"
    "keywordList" => "<a href="#">Quantum Optimization</a>, <a href="#">Big-M Problem</a>, <a href="#">Combinatorial Optimization</a>"
    "docPreview" => "<b>Alleviating the quantum Big-M problem</b><br><span>2025-12 | Journal articles </span>"
    "docType" => "research"
    "publicationLink" => "<a href="https://doi.org/10.1038/s41534-025-01067-0" target="_blank">Alleviating the quantum Big-M problem</a>"
  ]
  +lang: "en"
  +"_score": 8.714207
  +"_ignored": array:2 [
    0 => "abstract.en.keyword"
    1 => "abstract.fr.keyword"
  ]
  +"parent": null
}