Nutricati, Luca A;
Ghosh, Roopayan;
Feinstein, Natasha;
Bose, Sougato;
Warburton, PA;
(2025)
Enhancing the energy gap of random graph problems via XX-catalysts in quantum annealing.
Quantum Science and Technology
, 10
(4)
, Article 045010. 10.1088/2058-9565/adf2d5.
Preview |
Text
Warburton_Nutricati_2025_Quantum_Sci._Technol._10_045010.pdf Download (1MB) | Preview |
Abstract
One of the main challenges in solving combinatorial optimisation problems with quantum annealers is the emergence of extremely small energy gaps between the ground state and the first excited state of the annealing Hamiltonian. These small gaps may be symptoms of an underlying first-order phase transition, which, according to the adiabatic theorem, can significantly extend the required anneal time, making practical implementation effectively infeasible. In this paper we demonstrate that attaching an XX-catalyst on all the edges of a graph upon which a MWIS (Maximum Weighted Independent Set) problem is defined, significantly enhances the minimum energy gap. Remarkably, our analysis shows that the smaller the energy gap, the more effective the catalyst is in opening it. This result is based on a detailed statistical analysis performed on a large number of randomly generated MWIS problem instances on both Erdõs–Rényi and Barabáasi–Albert graphs. We perform the analysis using both stoquastic and non-stoquastic catalysts.
| Type: | Article |
|---|---|
| Title: | Enhancing the energy gap of random graph problems via XX-catalysts in quantum annealing |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1088/2058-9565/adf2d5 |
| Publisher version: | https://doi.org/10.1088/2058-9565/adf2d5 |
| Language: | English |
| Additional information: | Original content from this work may be used under the terms of the Creative Commons Attribution 4.0 license (https://creativecommons.org/licenses/by/4.0/). Any further distribution of this work must maintain attribution to the author(s) and the title of the work, journal citation and DOI. |
| Keywords: | quantum annealing, catalysts, enhancing energy gap, removing first-order phase transitions, minimum energy gap |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > London Centre for Nanotechnology |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10212552 |
Archive Staff Only
 |
View Item |
